ITPEC FE Subject A April 2025 Question 7
ITPEC FE Subject A April 2025 — Question 7 of 60
Hash Table with Open Addressing & Linear Probing — determine insertion order from final state.
Given: hash table size 11, function h(k) = k mod 11, linear probing.
Final state: [2]=79, [3]=14, [4]=35, [5]=92.
Natural hash positions:
- 79 mod 11 = 2 → placed at 2 (home)
- 14 mod 11 = 3 → placed at 3 (home or probed)
- 35 mod 11 = 2 → placed at 4 (probed from 2)
- 92 mod 11 = 4 → placed at 5 (probed from 4)
Verify (a) 14, 79, 35, 92:
- 14 → slot 3 (empty) ✓
- 79 → slot 2 (empty) ✓
- 35 → slot 2 (taken) → 3 (taken) → 4 (empty) ✓
- 92 → slot 4 (taken) → 5 (empty) ✓
Result: [2]=79, [3]=14, [4]=35, [5]=92 — matches.
Why not others:
- (b) 79, 14, 92, 35 — 35 would land at slot 5, not 4
- (c) 79, 92, 35, 14 — 35 lands at 3, 14 probes to 5
- (d) 92, 79, 14, 35 — 92 goes to 4, then 35 probes past 4 to 5
Key rule: With linear probing, simulate each insertion step-by-step. An element at a non-home slot means its home (and all slots between) were already occupied at insertion time.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
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.