2024 ASR H2 Computing Prelim P1 Qns

ASRJC 2024 [Turn over COMPUTING 9569/01 Paper 1 (Written) 11 September 2024 (Wednesday) 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 writing 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 0 blank page. Anderson Serangoon Junior College ANDERSON SERANGOON JUNIOR COLLEGE JC2 Preliminary Examination 2024 Higher 2

2 ASRJC 2024 1 A gym's membership management system uses Object Oriented Programming (OOP) in its design. The gym offers three types of membership: Basic, Pro and Family. For every gym member, its member ID, name, mobile number and membership start date need to be stored. The system should also allow for the annual renewal of membership. Basic members are only allowed non-peak hours gym usage daily. There are no restricted hours for Pro and Family memberships. Pro members are entitled to 10 complimentary training sessions with a qualified personal trainer of choice. For Family members, up to three family members' names can be stored. Basic members will be charged a monthly fee, while Pro members will be charged 1.3 times this rate. Each Family member will be charged 1.5 times this rate, with each additional family member being charged 0.5 times this rate. Membership fees are charged via a calculate_fee() method at the start of each membership cycle. (a) For the Basic base class, explain how encapsulation can be achieved. [2] (b) Explain the rationale of creating the Pro and Family subclasses. [2] (c) How does this class relationship demonstrate polymorphism? [3] (d) Draw a class diagram for this system showing the base class and the derived classes, including relevant attributes and methods necessary for the system to function. [6] (e) The gym business owner wishes to launch a referral promotion for members to refer their friends to join the gym. Each successful referral will extend an existing member's current membership validity period by one month. Describe the necessary change(s) that can be made to the class diagram to accommodate this updated requirement. [2] 2 ABC School has the following workflow for teachers to apply for vacation leave.

3 ASRJC 2024 [Turn over Note: ● Each teacher has a reporting supervisor ● HRP (Human Resource Portal) is an online platform for teachers to access services such as leave application (a) Convert the workflow to a decision table, showing all possible conditions and actions. [3] (b) Simplify your decision table in (a) by removing redundancies. [2] (c) Translate the decision table to pseudocode using appropriate variables. [4] 3 The Fibonacci sequence is a series of numbers in which each number is the sum of the two previous numbers: 1, 1, 2, 3, 5, 8, … (a) Draw a program flowchart to iteratively compute the nth Fibonacci number, n > 0. [3] (b) The following pseudocode shows an algorithm to iteratively compute the nth Fibonacci number: 01 FUNCTION fibonacci_iterative(n) 02 IF n <= 2 03 return n 04 ENDIF 05 a = 1 06 b = 1 07 FOR i FROM 2 TO n 08 temp = a + b 09 a = b 10 b = temp 11 ENDFOR 12 RETURN b 13 ENDFUNCTION Identify (specify line numbers) and rectify two logic errors with the above algorithm. [4] (c) Produce the pseudocode for a fibonacci_recursive(n) algorithm to determine the nth Fibonacci number recursively. [3] (d) Why is recursive Fibonacci less efficient than iterative Fibonacci for large n? [2] (e) Suggest a way to overcome the issue identified in (d). [3] 4 (a) What advantage does binary search and merge sort have in common compared to linear search and bubble sort? [3] (b) For a small dataset which is almost sorted, explain if quick sort is a suitable sorting algorithm. If not, suggest and justify a suitable sorting algorithm. [3] (c) For a large dataset with duplicates, explain if quick sort is a suitable algorithm. If not, suggest and justify a suitable sorting algorithm. [3] (d) Explain why the efficiency of merge sort is O(n lg n). [4]

4 ASRJC 2024 (e) For the purpose of illustration, using the integers 1 to 15 inclusive and each only once (i.e. no duplicates), give and explain a best case dataset scenario for quick sort if the middle element is selected as the pivot. For example, for integers 1 to 5 inclusive and no duplicates, a worst case dataset scenario for quicksort is [5, 4, 3, 2, 1] if the first element is selected as the pivot because the pivot will always have maximum number of elements in the left array and minimum number or no elements in the right array, resulting in the maximum number of recursive calls and worst case efficiency of quadratic time complexity O(n2). [3] 5 Every year, there is a large number of people balloting for a fixed and limited number of National Day Parade (NDP) tickets. For NDP2024, successful applicants were notified via email. While official figures are not disclosed, about or more than 15,000 spectators were reported by mainstream media. Moving forward, to prevent the problems of bounced emails and phishing, the organising committee would like to provide a web service to allow applicants to check their application status online. While there is no perfect data structure, after careful consideration, the organising committee is contemplating the use of a hash table to store successful applicants' identification and their status. (a) Justify why a hash table would be a suitable data structure in this context. [3] (b) What would be a suitable hash table size and why? [2] (c) To handle collision resolution, the developer decides to implement quadratic probing. What problem does quadratic probing address? [2] (d) Devise an algorithm to perform hash table search using quadratic probing collision resolution strategy. [5] (e) Compare and contrast the advantages and disadvantages of using an array over a hash table to store successful applicants’ identification and ballot status information. [3] 6 A theatre has an existing computer system that stores customer bookings in a spreadsheet. The following are some sample entries recorded: CustomerName Email ShowName ShowTime Duration Seats Amount Amil Bin Osman amilbo@email.com Miss Saigon 2024-08-30 1930 160 F09 $128.00 Bridgette