ITPEC FE Subject A April 2025 Question 7
A hash table of size 11 uses open addressing with hash function h(k)=k mod 11, and linear probing. The table shown below is created after inserting 4 values into an initially empty hash table. Which of the following is the sequence that represents a possible order in which the key values were inserted into the table?
Explanation
14, 79, 35, 92 — the only order in which linear probing leaves every key in the slot shown.
Home slots: 79 mod 11 = 2, 14 mod 11 = 3, 35 mod 11 = 2, 92 mod 11 = 4. 79 and 14 sit at home. 35 sits in slot 4, so slots 2 and 3 were already full when it arrived. 92 sits in slot 5, so slot 4 already held 35.
Tracing (a):
- •14 goes to slot 3
- •79 goes to slot 2
- •35: slot 2 full, slot 3 full, so slot 4
- •92: slot 4 full, so slot 5
Answer (a)
Why not others:
- •(b) 79, 14, 92, 35 — 92 arrives before 35 and takes its home slot 4, so 35 probes on to slot 5
- •(c) 79, 92, 35, 14 — 35 arrives before 14 and takes slot 3, so 14 probes past slots 3 and 4 to slot 5
- •(d) 92, 79, 14, 35 — 92 comes first and takes slot 4, again pushing 35 to slot 5
Key rule: A key found away from its home slot must have been inserted after every key that sits between its home slot and its actual slot.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.