Consider the following sequence of insertions performed on P:
1, 13, 22, 15, 11, 24
Which of the following positions in the hash table is/are empty after these insertions are performed?
Correct : c
Hash function h(x) = (x+7) mod 11. Linear probing on collision. Tracing each insertion:
Insert 1: h(1) = 8 mod 11 = 8. Position 8 is empty → placed at 8.
Insert 13: h(13) = 20 mod 11 = 9. Position 9 is empty → placed at 9.
Insert 22: h(22) = 29 mod 11 = 7. Position 7 is empty → placed at 7.
Insert 15: h(15) = 22 mod 11 = 0. Position 0 is empty → placed at 0.
Insert 11: h(11) = 18 mod 11 = 7. Position 7 is occupied (22). Probe 8 — occupied (1). Probe 9 — occupied (13). Probe 10 — empty → placed at 10.
Insert 24: h(24) = 31 mod 11 = 9. Position 9 is occupied (13). Probe 10 — occupied (11). Probe 0 — occupied (15). Probe 1 — empty → placed at 1.
Final state: positions 0(15), 1(24), 7(22), 8(1), 9(13), 10(11) are occupied. Positions 2, 3, 4, 5, 6 are empty. Among the options, position 2 is empty while positions 0, 1 and 10 are all occupied.
Correct answer: C — Position 2 is empty.
Similar Questions
Total Unique Visitors