2025 ASRJC H2 Computing Prelim Theory P1

1 [Turn over COMPUTING 9569/01 Paper 1 Written 22 August 2025 (Friday) 8 – 11 am 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. This document consists of 6 printed pages and 2 blank pages. Anderson Serangoon Junior College ANDERSON SERANGOON JUNIOR COLLEGE JC2 Preliminary Examination 2025 Higher 2

2 1 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 (a) Write your answer for each blank (1) through (7) clearly. [3] (b) State the worst-case time complexity of insertion sort and briefly explain what that implies. [2] (c) 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] 2 (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]

3 [Turn over When a Sonars amplifier system arrives for diagnosis, the technician checks for these symptoms: • whether the power LED is OFF • whether the audio output is abnormal • whether the amplifier is overheating The following describes the actions the technician would take: If the power LED is off, check the power supply and fuse only regardless of other symptoms. If the power LED is on and the audio output is abnormal (but not overheating), test the input connections. If the amplifier is overheating, clean the ventilation system and fans. If the audio is abnormal and the amplifier is overheating, also check the output transistors, as they may be faulty. If none of the 3 symptoms are present, perform a routine check. It is desired to draw a decision table for the above information. (c) (i) Explain what a decision table is. [2] (ii) Create a complete decision table based on the description above. [4] (iii) Show a simplified decision table without redundancies. [2] 3 Harley Thorman Corporation is developing an inventory management system for its electronic products using Object-Oriented Programming (OOP). The main types of electronic devices that the corporation sells are display devices, audio devices and computing devices. Display devices include televisions, computer monitors and screen projectors. Audio devices include speaker systems and headphones. Computing devices include desktops, laptops and tablets. (a) Draw a class diagram for this system showing classes and their inheritance relationships. Do not include any attributes or methods in the diagram. [3] (b) Explain why inheritance is an important feature in OOP . [1] (c) Suggest which class each of the following attributes should be placed in, explaining your choice: • CPU model • product serial number. [3] (d) Suggest a possible private method that one might include in the OOP system, explaining why keeping it private would be reasonable. [2] There are different types of TV display technologies, each with distinct features. LCD TVs use liquid crystal displays with backlighting, while LED TVs use LED backlighting for better energy efficiency. OLED TVs use organic light-emitting diodes that allow pixels to turn completely off, providing superior contrast ratios. QLED TVs use quantum dot technology to enhance brightness and colour accuracy. What distinguishes them is the panel technology type, which results in differences in display characteristics such as contrast ratio, peak brightness and colour gamut coverage. (e) Suggest how the OOP system should be updated to accommodate these different TV display technologies, justifying the approach chosen. [2] (f) Explain what is meant by polymorphism in OOP. [1]

4 4 You are given the following sequence of words (which represent different generative AI platforms): perplexity, claude, gemini, deepseek, chatgpt, copilot, qwen, ernie (a) These words are inserted one by one into an empty binary search tree (BST) in the given order, with nodes arranged based on lexicographical (alphabetical) order. Draw the complete BST after insertion. [2] (b) List the nodes visited in pre-order and post-order traversals. [2] (c) What property does the in-order traversal have for the BST? [1] (d) If we replace the word ‘perplexity’ with ‘grok’ in the insertion sequence while maintaining the same order of insertions, will the resulting BST structure be different? Explain your reasoning without reconstructing the BST. [2] (e) Write, in pseudocode, a recursive function Search(root, target) to perform a binary tree search for the value target. It should return a boolean indicating whether the target value is present in the tree. [4] (f) Write, in pseudocode, a recursive function CountNodes(root) that returns the total number of nodes present in the BST. [3] (g) For the case where many words need to be stored, explain the advantage of using a binary search tree compared to a sorted linked list. [2] 5 Refer to the following recursive function P: 01 02 03 04 05 06 07 08 09 10 11 12 FUNCTION P(x : REAL, a : INTEGER) RETURNS REAL IF a = 0 or a = 1 THEN RETURN x ENDIF IF a MOD 2 = 0 THEN r = P(x, a / 2) RETURN r * r ELSE RETURN x * P(x, a - 1) ENDIF ENDFUNCTION (a) With reference to relevant line numbers in the pseudocode, explain the three features seen here that make P a recursive function. [3] The author of the function intends for it to work for all non-negative integer values of a. (b) Identify the intended purpose of this function. [2] (c) Upon testing, the author realises that there is a logic error in the code. Identify this error and state how the existing code should be cor