2025 TJC H2 Computing Prelim Paper 1 Solutions

© TJC 2025 [Turn over 1 An ISBN is an International Standard Book Number and is a unique identifier for each book. Each ISBN consists of 13 digits, which is made up of 5 elements with each element being separated by spaces or hyphens. Three of the five elements may be of varying length: • Prefix element – currently this can only be either 978 or 979. It is always 3 digits in length • Registration group element – this identifies the country, geographical region, or language area participating in the ISBN system. This element may be between 1 and 5 digits in length • Registrant element - this identifies the publisher or imprint. This may be up to 7 digits in length • Publication element – this identifies the edition and format of a specific title. This may be up to 6 digits in length • Check digit – this is always the final single digit that mathematically validates the rest of the number. It is calculated using a Modulus 10 system with alternate weights of 1 and 3. An example of an ISBN with check digit 5 is shown below: (a) Describe a purpose of the check digit in an ISBN. [2] Detect common input errors such as transcription error and transposition error [1], which helps to maintain data accuracy in book identification systems [1] (b) Suggest another suitable validation technique for ISBN. [1] Length check – check that ISBN consists of 13 digits [OR] Format check – check that each of the elements fulfil the criteria specified A school library system needs to store and search for information about books using their unique ISBNs. New books are added into the library inventory and damaged or older books are condemned from time to time. The developers propose the use of a hash table to store and retrieve the book records. (c) Explain how the library system would use a hash function and a hash table to store and search for books by their ISBNs. [3] Each ISBN will be processed by the same hash function to generate an index/key [1], which corresponds to the position in the hash table where the book record will be stored [1]. When searching for a book using its ISBN, it uses the same hash function to generate the index/key to locate the record directly. [1] 978 - 92 - 95055 - 02 - 5 Prefix Registration group Registrant Publication Check digit

2 9569/01/2025 (d) Give three features of an effective hashing algorithm. [3] Any of the following 3: 1. The function should reduce the chances of different keys producing the same hash (collisions). This avoids clustering and reduces the chance of collisions, which keeps lookup, insert, and delete operations efficient (close to O(1)). 2. Equal probability of generating the indices or the indices generated are spread evenly across all the full range of the indices of the table. (Uniform Distribution) 3. The same input must always produce the same hash value. This ensures that a key can be found reliably each time it is accessed. (Deterministic) 4. Quick computation of the hash address. (e) Explain the meaning of a collision in this context. [2] A collision occurs when elements in a hash table share the same hash value. When this occurs, the book record cannot be stored in that space and an alternative space has to be sought out to store that book record. [1] When searching for a book record, and another book record is found, it does not mean that the search item is not in the table. [1] A collision resolution algorithm is used to continue searching for the item at other locations before a conclusion is made. (f) Describe one method that can be used to handle the consequence of a collision. [2] Linear probing is a method to deal with collision. [1] This is done by probing sequentially the next space or using an interval (e.g. check every 3rd slot) until an empty slot is found. [1] [OR] Chaining can also be used to handle the consequence of a collision. In chaining, records are stored in a node of one of the many linked lists. Each array item of the hash table will store the address of one linked list. Whenever a key of a record gets hashed to an address where another record has already been hashed to, the new record will be added to the end of the list that its hashed address points to. Students on an internship with the library ask their developer mentors why the book records, ordered by their ISBNs, were not stored in a linked list instead. (g) Describe one disadvantage of storing and searching the records ordered by ISBNs using a linked list. [2] Locating a book will require traversing through the linked list starting from the head of the linked list, which is slow process of O(n) time complexity [1] This affects not just the searching process, but also the insertion and deletion process to maintain the order of the records by ISBN [1]

3 9569/01/2025 [Turn over 2 A program implements a Merge Sort algorithm to order values into ascending order. The contents of an array are shown: 12 10 5 1 24 9 6 (a) Explain how a Merge Sort algorithm will sort the data in the array into ascending order. [3] Divide the array into smaller subarray until each subarray has only one element [1] Merge the subarrays back together in the correct (sorted) order. [1] Illustrate using the array given [1] (b) Using Big-O notation, state the worst-case time complexity of Merge Sort. [1] O(log n) (c) The Merge Sort algorithm uses recursion. (i) State three features of a successful recursive function. [3] - A recursive algorithm must call itself, recursively. - Has a base case or terminating condition where the function stops calling itself - A recursive algorithm must change its state and move toward the base case (ii) State the purpose of the given pseudocode function: FUNCTION iterative (string1) left = 1 right = LENGTH(string1) WHILE left < right IF string1[left] <> string1[right] RETURN FALSE END IF left = left + 1 right = right - 1 END WHILE RETURN TRUE END FUNCTION [1] This function checks whether string1 is a palindrome. (iii) Rewrite the pseudocode function in (c)(ii) using recursion. [3] FUNCTION recursive(string1) IF LENGTH(string1) <= 1 [Base case: 1] RETURN TRUE END IF IF string1[1] <> string1[LENGTH(string1)] [1]

4 9569/01/2025 RETURN FALSE END IF RETURN recursive(SUBSTRING(string1, 2, LENGTH(string1) - 2)) [1] END FUNCTION

5 9569/01/2025 [Turn over 3 A software company is writing a program for a vehicle hire business. Both cars and vans are available for hire. For all vehicles, the data that will be stored include: Vehicle Registration Number (VRN) Total distance travelled (km) Date hired Date of return Cost per day Availability for hire For cars, the additional data stored include: Fuel type (petrol, diesel, electric, hybrid) For vans, the additional data stored include: Maximum load (kg) The odometer in the vehicle displays the total distance the vehicle has travelled since manufacture. When a vehicle is hired: ● total distance travelled is set to the odometer's value ● date hired is set to the current date ● date of return is set to the date the vehicle is expected to be returned ● availability for hire is set to FALSE. When a vehicle is returned: ● hire cost is returned as the cost per day multiplied by the number of days the vehicle was hired ● total distance travelled is set to the odometer value ● date of return is set to the current date ● availability for hire is set to TRUE. Object-oriented programming will be used to model this situation. (a) Draw a class diagram that shows the following for the situation described above. ● the superclass ● any subclasses ● inheritance ● properties ● appropriate methods. [8] (b) Explain ho