Fig. 1 shows a hash table used by a bike-hire service. A bike number is converted to an array position using bikeNumber MOD 10. The displayed table has a co...
Question 1 Report
Fig. 1 shows a hash table used by a bike-hire service. A bike number is converted to an array position using bikeNumber MOD 10. The displayed table has a collision at position 3, so each square contains a linked list of records. The program must find a hire record quickly when a rider reports that a bicycle has been returned. The table size is fixed during one day of operation.
(a) Explain why bike number 423 is stored at index 3. [1]
(b) When bike number 733 is entered, explain how separate chaining handles the collision. [2]
A meteorology station receives temperature messages from 40 remote sensors. The main program stores the latest reading for each sensor in an array, using the sensor number as the index. Sensor 17 sends a new reading of 21.6 degrees C. The programmer chooses direct array access because the latest value is needed immediately for a warning calculation, rather than searching through all sensor records.
(a) Explain the array element updated by the new message. [1]
(b) When sensor 17 sends another value, explain why the existing element can be overwritten. [2]
(c) Explain one reason why this array is less suitable for storing an unknown number of fault reports. [1]
Answer Details
Hash table
(a) The hash calculation is \(423 \bmod 10 = 3\), so bike number 423 is stored at index 3. [1]
(b) Bike 733 also gives index 3, so separate chaining adds a new record to the linked list at index 3. The existing records are not overwritten; a pointer links the new record into that chain. [2]
Direct array access
(a) The new reading is stored in array element, or index, 17. The sensor number is used directly as the pointer. [1]
(b) The existing value for sensor 17 can be overwritten because only the latest reading is required. The new reading replaces the older reading for the same sensor. [2]
(c) An array has a fixed capacity. It is less suitable where the number of fault reports is unknown because the number of reports could exceed the allocated size. [1]
Download The App On Google Playstore
Everything you need to excel in your exams
