ITPEC FE Subject B October 2024 Question 13

Hash Table with Linear Probing — insert a key-data pair using open addressing with wrap-around.

hashTable is a 1-based array of 1000 elements, each initially {undefined}. Each occupied slot stores {key, data}. hashFunction(key) returns (key mod size) + 1.

insertData finds the first free slot starting from the hash index using linear probing:

• •Blank A (while condition): The loop must continue while the current slot is occupied. A slot is occupied when hashTable[index][1] ≠ undefined. Once an undefined slot is found, the loop exits and the data is written.
• •Blank B (when `index = size`): When the index reaches the end of the array (size = 1000), it must wrap around to the beginning: index ← 1.

Why not others:
- (a) ≠ key checks for a duplicate key, not for a free slot — wrong purpose
- (b, d, f, h) index ← index - 1 moves backward — linear probing moves forward with wrap-around
- (c, g) = key / = undefined reverses the loop logic — the loop would exit immediately on a free slot before writing

Key rule: Linear probing loops while the slot is occupied (≠ undefined) and wraps to index 1 when the end of the array is reached.

AI-generated — may contain errors