2023 ACJC P1 Question Paper

ANGLO-CHINESE JUNIOR COLLEGE JC2 PRELIMINARY EXAMINATION Higher 2 COMPUTING 9569/01 Paper 1 Written 24 August 2023 3 hours READ THESE INSTRUCTIONS FIRST An answer booklet will be provided with the question paper. You should follow the instructions on the front cover of the answer booklet. If you need additional answer paper ask the invigilator for a continuation booklet. Answer all questions. Approved calculators are allowed. The number of marks is given in brackets [ ] at the end of each question or part question. The total number of marks for this paper is 100. __________________________________________________________________________________ This document consists of 6 printed pages and 1 blank page. [Turn Over

2 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/01 1 Planetary bodies can be classified as planets, dwarf planets, or small solar system bodies. To qualify as a planet, the body must be in orbit around the sun, have sufficient mass to be spherical, and have cleared the neighbourhood around its orbit. A smaller spherical body that orbits around the sun, but have not cleared the neighbourhood around its orbit is classified as a dwarf planet. Pluto is an example of a dwarf planet. Finally, all other planetary bodies in orbit around the sun are collectively classified as small solar system bodies. Create a simplified decision table to show the conditions and actions for classifying planetary bodies. [5] 2 (a) Unicode and ASCII are two different character encoding standards. Explain why characters need to be encoded. [2] (b) Explain one similarity and one difference between Unicode and ASCII. [2] (c) Convert 125 from denary to hexadecimal. Show your working. [2] 3 A country’s transport authority would like to use Object Oriented Programming (OOP) to model the vehicles in the country. All vehicles in the country have the following data recorded: • Registration code • Engine size • Date of registration The age of a vehicle can be calculated with the following equation: age = current date – registration date The amount of taxes required for a vehicle is determined by the engine size Commercial vehicles have the following data recorded: • Company type • Vehicle purpose The amount of taxes required for a commercial vehicle is determined by the company type and engine size of the commercial vehicle. Emergency vehicles have the following data recorded: • Vehicle type • Last servicing date (a) Draw a class diagram that shows the following for the data in the game described above: • The superclass; • Any subclasses; • Inheritance; • Properties; • Appropriate methods. [8] (b) Explain the purpose of inheritance using examples from this situation. [3] (c) Explain the purpose of making the attributes of an object private. [2] (d) The transport authority decided that emergency vehicles should not be taxed. Suggest a change to the class diagram to enable this and explain why it works. [2]

3 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/01 [Turn Over 4 (a) The pseudo-code for a sorting algorithm is shown below. The indices in the list start from 1. 01 INPUT MyList 02 MaxIndex ← LENGTH(MyList) 03 04 FOR i ← 1 TO (MaxIndex - 1) 05 MinVal ← 999 06 MinValIndex ← 0 07 08 FOR j ← i TO MaxIndex 09 IF MyList[j] < MinVal 10 THEN 11 MinVal ← MyList[j] 12 MinValIndex ← j 13 ENDIF 14 ENDFOR 15 16 Temp ← MyList[i] 17 MyList[i] ← MinVal 18 MyList[MinValIndex] ← Temp 19 ENDFOR (i) Using the list [8,5,7,1,4,2] as input, write down the list after each pass of the FOR loop from lines 04 to 19. [5] (ii) State the time complexity of this algorithm. [1] (iii) State a list of positive integers that is an erroneous test case for this algorithm. [1] (iv) Explain how the algorithm can be modified so that logic errors of the type seen in (iii) do not occur. [2] (b) Bubble sort and merge sort are two sorting algorithms. (i) State one advantage of bubble sort over merge sort. [1] (ii) State one advantage of merge sort over bubble sort. [1] (iii) Merge sort is a recursive algorithm. State two characteristics of a recursive sorting algorithm. [2]

4 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/01 5 The following algorithm’s input is a binary tree. It also makes use of two stacks which are initially empty. Stage 1 1. Push the root of the tree into Stack 1. 2. Repeat the following steps until Stack 1 is empty: a. Pop from Stack 1. This will give a node Node. b. If Node has a left child, push the left child of Node into Stack 1. c. If Node has a right child, push the right child of Node into Stack 1. d. Push Node into Stack 2. Stage 2 1. Repeat the following steps until Stack 2 is empty: a. Pop from Stack 2 and output the data of the node that was just popped. Use the following tree as input for the algorithm. (a) Write down the full contents of Stack 1 and Stack 2 at the end of each pass of the Repeat loop in Stage 1. [6] (b) Write down the output that the algorithm has produced in Stage 2. [1] State whether this is a pre-, post- or in-order traversal of the tree. [1] (c) Explain whether it is possible to reconstruct the tree if the only knowledge you have is the output in Stage 2, and the type of traversal that it represents. [1] A B C E D F G

5 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/01 [Turn Over 6 A linked list is implemented inside an array as shown below. Data Pointer [0] "ADA" None FreeListPointer = 4 [1] "" None LinkedListPointer = 2 [2] "BOB" 3 [3] "EVE" 5 [4] "" 1 [5] "PUP" 0 The following steps are carried out in order: 1. A node whose data is "SUS" is added at the head of the linked list. 2. The node at the end of the linked list is deleted. 3. The node whose data is "EVE" is deleted. (a) Write down the full contents of the array, as well as the values of FreeListPointer and LinkedListPointer. [6] (b) Explain why it is not suitable to perform a binary search to look for a particular data value. [1] (c) Suppose the array is very large but the linked list contains only a few items. Describe how a linear search can be carried out to look for a particular data value. [4] 7 A music record store uses an SQL database to record information about their records and customers. • Each album is recorded by an artiste, and is given a genre and price. • When a customer buys an album, the date and time of the purchase are recorded. Since there is more than one cashier, two customers may purchase records at the same time. The following set of tables represents a first attempt at constructing the database. Albums: AlbumID AlbumName Artiste Genre Price K01 Circle One Whitepink K-pop 35.00 K02 Why You Like That Whitepink K-pop 35.00 K03 Everyday Strife Hotplay Rock 30.00 K04 Most Stories Hotplay Rock 32.00 K05 Ocean Pies Billy Eyelash Pop 40.00 K06 Good Guy Billy Eyelash Pop 35.00 Purchases: CustomerID CustomerName Customer PhoneNo AlbumID Datetime Quantity 0001 Roy Tan 94682222 K03 2022-08-22 17:35 1 0001 Roy Tan 94682222 K04 2022-08-22 17:35 1 0002 Sharifah 93459898 K03 2022-08-22 17:35 1 0001 Roy Tan 94682222 K04 2022-09-01 17:35 2 0003 Jane Lee 92255582 K01 2022-09-01 18:21 1 0003 Jane Lee 92255582 K02 2022-09-01 18:21 1

6 ANGLO-CHINESE JUNIOR COLLEGE 2023 H2 COMPUTING 9569/01 (a) Explain which table(s) in the above database is not in third normal form (3NF). [2] (b) Normalize the table(s) in (a) to third normal form (3NF). Draw the Entity-Relationship (E-R) diagram to show the tables in 3NF and the relationships between them. [3] (c) A