ACJC 2025 JC2 Computing Prelim Paper 1

ANGLO-CHINESE JUNIOR COLLEGE JC2 PRELIMINARY EXAMINATION Higher 2 COMPUTING 9569/01 Paper 1 Written 3 September 2025 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 7 printed pages and 1 blank page. [Turn Over

2 ANGLO-CHINESE JUNIOR COLLEGE 202 5 H2 COMPUTING 9569/01 1 In a sports club, the members have different ratings depending on whether they can meet certain performance criteria, namely:  Running 2.4 km in at most 12 min;  Doing at least 50 push ups in 1 min;  Doing at least 40 sit ups in 1 min. Members are ordinary members by default. If a member runs 2.4 km in more than 12 min, that member is still an ordinary member, regardless of how the member performs in in the other criteria. If the member runs 2.4 km in at most 12 min and meets one of the other criteria, that member is a silver member. If the member meets all three criteria, that member is a gold member. (i) Create a decision table to show these conditions and actions. [4] (ii) Simplify your decision table by removing redundancies from the decision table. [2] 2 A private school has two kinds of students, full -time students and part -time students. It uses object-oriented programming (OOP) to store data about the students. For both kinds of students, their name and date of birth are stored. For full -time students, their address and telephone number are stored. For part -time students, the list of classes they are taking is stored. Full-time students pay an annual school fee which is a constant amount. The school fee for part- time students is calculated based on the number of classes they are taking. (a) Draw a class diagram that shows the following in the school as described above:  The superclass;  Any subclasses;  Inheritance;  Attributes;  Appropriate methods. [6] (b) Give an example of inheritance in the class diagram in part (a). [1] (c) Explain where and how polymorphism is useful in this context. [2] The school needs to back up and archive data regularly. (d) (i) Explain why there is a need to back up data. [2] (ii) Explain why there is a need to archive data. [2]

3 ANGLO-CHINESE JUNIOR COLLEGE 202 5 H2 COMPUTING 9569/01 [Turn Over 3 The greatest common divisor (gcd) of two positive integers m and n is the largest integer that divides both m and n with a remainder of 0. The pseudo-code below shows an attempt to write an algorithm to find the gcd of m and n. 00 INPUT m, n 01 02 DECLARE d : INTEGER 03 d ← 0 04 05 FOR i ← 1 TO m: 06 IF m MOD i = 0 OR n MOD i = 0 THEN 07 d ← i 08 ENDIF 09 ENDFOR 10 11 OUTPUT d (a) State the output when the input values m = 21, n = 28 are given to the algorithm. [1] (b) Identify the line where there is a logic error and give the correct pseudo-code to find the gcd. [2] Euclid’s Algorithm is a method to determine the greatest common divisor of two positive integers m and n. The pseudo-code for a recursive implementation of Euclid’s Algorithm is given below. 00 FUNCTION gcd(m,n : INTEGERS) RETURNS INTEGER 01 02 IF m = n THEN 03 RETURN m 04 ELSE 05 IF m > n THEN 06 RETURN gcd(m-n, n) 07 ELSE 08 RETURN gcd(m, n-m) 09 ENDIF 10 ENDIF 11 12 ENDFUNCTION (c) State the features of the function gcd that make it recursive. [3] (d) Draw a trace diagram for the input values m = 21, n = 28. [3] (e) Explain what will happen to the recursion and execution of the recursive function gcd when m is positive and n is negative. [2] (f) Rewrite the function gcd in pseudo -code to carry out Euclid’s algorithm without using recursion. [3]

4 ANGLO-CHINESE JUNIOR COLLEGE 202 5 H2 COMPUTING 9569/01 4 A hash table is implemented inside an array of length 10. The hash table is intended to store the names and ages of people. Each record is to be stored as a tuple (name,age). The hash function is the number of characters in the name. In the event of a collision, a linear search for an empty entry would be carried out starting from the index of the collision, looping back to the start of the array if necessary. Copy the following array onto the answer sheet. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] (i) Add the records into the array as they are inserted in the following order. 1. ('Jacky', 22) 2. ('Sam', 18) 3. ('Joel', 20) 4. ('Bob', 21) 5. ('Justin', 19) [5] (ii) Describe how to look up Bob’s age in the hash table. [4] Suppose instead that the same records are to be stored in a binary search tree (BST), in order of age. The records are inserted into the BST in the same order as in part (i). (iii) Draw the resulting BST. [3] (iv) List the names in a post-order traversal of the BST. [2] (v) Explain how you would use the BST to determine who is the second oldest person. [3]

5 ANGLO-CHINESE JUNIOR COLLEGE 202 5 H2 COMPUTING 9569/01 [Turn Over 5 The pseudo-code for a bubble sort algorithm to sort an array of integers in increasing order is shown below. The indices in the array start from 1. 01 PROCEDURE BubbleSort(Arr : ARRAY OF INTEGER) 02 DECLARE N, Temp : INTEGERS 03 N ← LENGTH(Arr) 04 05 FOR i ← 1 TO N–1 06 FOR j ← 1 TO N–1 07 IF ... (A) ... THEN 08 Temp ← Arr[j+1] 09 Arr[j+1] ← ... (B) ... 10 Arr[j] ← ... (C) ... 11 ENDIF 12 ENDFOR 13 ENDFOR 14 ENDPROCEDURE (a) Write the correct pseudo-code for (A), (B), (C) in the algorithm above. [3] (b) State two ways in which the time complexity of the algorithm above can be improved. [3] (c) State the worst-case time-complexity of bubble sort. [1] In a merge sort algorithm, a helper function is needed to combine two sorted lists into one sorted list. The pseudo-code for the helper function is given below. The indices in both arrays start from 1. 01 FUNCTION Combine(Arr1, Arr2 : ARRAYS OF INTEGER) 02 DECLARE N1, N2, i, j : INTEGERS 03 N1 ← LENGTH(Arr1), N2 ← LENGTH(Arr2) 04 i ← 1, j ← 1 05 06 DECLARE Arr[1:(N1 + N2)] : ARRAY OF INTEGER 07 08 WHILE ... (D) ... 09 IF ... (E) ... THEN 10 Arr[i+j-1] ← Arr1[i] 11 i ← i+1 12 ELSE 13 Arr[i+j-1] ← Arr2[j] 14 j ← j+1 15 ENDIF 16 ENDWHILE 17 18 WHILE i+j-1 <= N1 + N2 19 IF ... (F) ... THEN 20 Arr[i+j-1] ← Arr1[i] 21 i ← i+1 22 ELSE 23 Arr[i+j-1] ← Arr2[j] 24 j ← j+1 25 ENDIF 26 ENDWHILE 27 28 RETURN Arr 29 ENDFUNCTION

6 ANGLO-CHINESE JUNIOR COLLEGE 202 5 H2 COMPUTING 9569/01 (d) Write the correct pseudo-code for (D), (E), (F) in the algorithm above. [3] (e) Write a function to perform merge sort, using the helper function above, in pseudo-code. [4] 6 A user on a website has to fill out a form to register for an account. The user needs to create a username and a password. The password needs to be at least 8 characters long and contain at least one uppercase letter, one lowercase letter, one digit, and one punctuation symbol. (a) State the difference between data validation and data verification. [2] (b) In this context, d