2025 VJC H2 Computing Prelim Paper 1 Solutions

This document consists of 10 printed pages and 2 blank pages. © NYJC/TJC/VJC 2025 [Turn over VICTORIA JUNIOR COLLEGE JC 2 PRELIMINARY EXAMINATION Higher 2 COMPUTING [MARKING SCHEME] 9569/01 Paper 1 Written 17 September 2025 3 hours READ THESE INSTRUCTIONS FIRST An answer booklet will be provided with this 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.

2 9569/01/2025 1 A programmer is writing a program to manage and search for records. The records include phone numbers, which comprise 8 decimal digits. (a) Convert the phone number 62842281 to: (i) Hexadecimal representation [2] 62842281 = 3*16^6 + 11*16^5 + 14*16^4 + 14*16^3 + 5*16^2 + 10*16^1 + 9*16^0 [1] Or repeated division by 16 3BEE5A9 [1] (ii) ASCII value for each digit. ('0' has an ASCII value of 48 and '9' has an ASCII value of 57.) [2] Map each ASCII decimal character to ASCII value 54, 50, 56, 52, 50, 50, 56, 49 [1 mark for every 4 correct values] (b) The programmer’s supervisor suggests a binary search tree instead of a sorted array for managing phone numbers. Suggest two reasons for the supervisor’s advice. [2] BST has lower time complexity for adding items [1] BST maintains items in sorted order, whereas array may require re-sorting [1]

3 9569/01/2024 [Turn over 2 A recursive function countPaths is designed to find the number of different possible paths from the top-left corner to the bottom-right corner of a grid. The function can only move right or down at each step. For example, in a 2×2 grid, where row = 2 and col = 2, there are two possible paths from the top-left corner to the bottom-right corner of the grid: ● Right → Down ● Down → Right The function is defined as follows: 01 FUNCTION countPaths(row : INTEGER, col : INTEGER) RETURNS INTEGER 02 IF row = 1 OR col = 1 THEN 03 RETURN 1 04 ENDIF 05 RETURN countPaths(row - 1, col) + countPaths(row, col - 1) 06 ENDFUNCTION (a) An example of a trace tree diagram showing countPaths(2,2) is shown as follows: Use the above example to create a trace tree diagram for the recursive function call countPaths(3,2). [4] Correct root node showing countPaths(3,2) [1] Correct first level of recursive calls [1] Correct first level of return values [1] Correct final return calculation and value (2+1=3) [1] countPaths(2,2) countPaths(1,2) countPaths(2,1) Return 1 Return 1 Return 1+1=2

4 9569/01/2025 Note: Second level of recursive calls given in example (b) Explain how the base case in lines 02 to 03 prevents infinite recursion. [2] Explanation that base case is reached when either dimension becomes 1 [1] Explanation that this ensures termination by returning a value [1] When the function is called, it checks if either row or col is equal to 1. If this condition is met, the function returns 1, indicating that there is exactly one way to reach the destination when either dimension is reduced to 1. This means that the function will no longer call itself recursively, effectively terminating the recursion when it reaches this base case, thus preventing the function from running indefinitely countPaths(3,2) countPaths(2,2) countPaths(3,1) Return 1+1=2 Return 1 Return 2+1=3 Return 1 countPaths(2,1) Return 1 countPaths(1,2)

5 9569/01/2024 [Turn over (c) Write an iterative version of the original countPaths function. [5] Correct array/table initialization [1] Proper handling of edge cases [1] Correct nested loop structure [1] Correct cell value calculation [1] Return correct final value [1] FUNCTION countPathsIterative(row : INTEGER, col : INTEGER) RETURNS INTEGER DECLARE grid : ARRAY[1:row, 1:col] OF INTEGER // Initialize the first row and first column FOR i ← 1 TO row DO grid[i,1] ← 1 NEXT i FOR j ← 1 TO col DO grid[1,j] ← 1 NEXT j // Fill the rest of the paths matrix FOR i ← 2 TO row DO FOR j ← 2 TO col DO grid[i,j] ← grid[i – 1,j] + grid[i,j – 1] NEXT j NEXT i RETURN gird[row,col] ENDFUNCTION

6 9569/01/2025 3 A software company is developing a print server that handles print jobs from multiple users. Each print job has a job ID and number of pages. The system needs to handle both regular and priority print jobs. (a) The regular print jobs use a linear queue data structure. Explain why a linear queue would be appropriate for regular print jobs. [2] Definition of queue as FIFO structure [1] Explanation of appropriateness for print jobs (order preservation) [1] A queue is a First-In-First-Out (FIFO) data structure where elements are added at one end (rear) and removed from the other end (front). This is appropriate for print jobs as it ensures jobs are processed in the order they were submitted (effectively manage multiple print jobs without the risk of mixing them up), maintaining fairness in the printing system. (b) The company decides to implement the queue as a circular queue using a static array of size 5. State one difference between a linear queue and a circular queue. [2] ● Once a linear queue is full, no more print jobs can be added until all the queued jobs have been processed. [1] ● With a circular queue, print jobs can be added in positions from which the print job has been processed. [1] A linear queue stores print jobs sequentially and can become inefficient when it reaches capacity, as it cannot accept new print job until all the print jobs have been processed, potentially wasting space. In contrast, a circular queue wraps around and efficiently utilizes space by allowing a new print job to be added at the front if there is space due to dequeued job, thereby preventing wasted positions. (c) Draw a diagram showing the state of a circular queue after the following operations, showing the positions of front and rear pointers: 1. Enqueue jobs: 101, 102, 103, 104 2. Dequeue two jobs 3. Enqueue jobs: 105, 106 [3] Correct element placement [1] Correct front pointer position [1] Correct rear pointer position [1] [106] [ ] [103] [104] [105] ^Front (at index 2) [106] [ ] [103] [104] [105] ^Rear (at index 0 or index 1 if rear is pointing to next available slot) (d) Explain one disadvantage of using a circular queue instead of a linear queue for this implementation. [2] Valid disadvantage [1] Sufficient explanation in the context [1]

7 9569/01/2024 [Turn over A circular queue has a more complex implementation logic that requires additional calculations to handle the wraparound of the rear pointer and to determine when the queue is full. For example, when adding a new print job, the program needs to check if (rear + 1) mod size equals front to determine if the queue is full, rather than simply checking if rear has reached the end of the array as in a linear queue. This increased complexity makes the code more difficult to maintain and debug if issues arise with the print job system. (e) The print server keeps a history of completed print jobs in a stack data structure. (i) Explain how a stack data structure would be appropriate for implementing an "undo" feature that allows the system administrator to restore recently completed print jobs back to the queue. [2] Explanation of stack's LIFO nature being suitable for undo/history [1] Clear connection to how this benefits system administrator's restore operatio