2025 ASRJC H2 Computing Prelim Theory Paper (Solutions)

Question 1 [8 marks] Below shows a pseudocode of insertion sort with blanks. PROCEDURE InsertionSort(A : ARRAY[0 : N - 1] OF INTEGER) // using 0-indexing FOR i ← ……(1)…… TO ……(2)…… temp ← A[i] j ← ……(3)…… WHILE j >= 0 AND temp < ……(4)…… ……(5)…… ← A[j] j ← ……(6)…… ENDWHILE ……(7)…… ← temp NEXT i ENDPROCEDURE Write your answer for each blank (1) through (7) clearly. [3] State the worst-case time complexity of insertion sort and briefly explain what that implies. [2] Insertion sort is effective for small arrays due to its simplicity and low overhead. However, for larger arrays, more efficient algorithms such as merge sort are preferred. Describe how merge sort works and state its time complexity. [3] Answers: (a) (1) 1, (2) N – 1, (3) i – 1, (4) A[j], (5) A[j + 1], (6) j – 1, (7) A[j + 1] (b) Worst-case time complexity: O(n2) For large datasets, the number of operations required for insertion sort grows quadratically with input size. (c) Merge sort is a divide-and-conquer algorithm that sorts an array by recursively breaking it down and then combining them in sorted order. - Divide the array in half repeatedly until each subarray contains only one element. - Combine adjacent subarrays back together in sorted order. Continue this process until the entire sorted array is constructed. Time complexity: O(n log n) Question 2 [15 marks] (a) State what is meant by data integrity. [1] Sonars Service Centre handles repairs of their proprietary Sonars audio products. When customers bring equipment for repair, technicians would need to enter the product serial number into the system. Each serial number consists of 10 digits, where the last digit is a check digit calculated using this algorithm: 1. In the first pass, multiply each of the first 9 digits of the serial number by weights: 9, 8, 7, 6, 5, 4, 3, 2, 1 respectively (e.g. position 1 gets weight 9). Sum these products to obtain subtotal. 2. In the second pass, using the same 9 digits of the serial number, multiply each digit by the sum of its own value and its position number (e.g. if the first digit is 5, we get a product of 5 x (5 + 1) = 30 for that digit). Sum these products to obtain another subtotal. 3. Add the two subtotals from the two passes to obtain a combined total.

4. Divide the combined total by 13 to obtain the remainder. Subtract the remainder from 13 to derive the check digit. (b) (i) It is given that 284736197X is a valid serial number, where X represents the check digit. Calculate the value of X, showing your workings. [3] (ii) Briefly explain why check digit alone is insufficient to ensure data integrity. [1] (iii) Describe two data verification methods that can be used when manually entering serial numbers into the system. [2] When a Sonars amplifier system arrives for diagnosis, the technician checks for these symptoms: ● whether the p