Question:medium

Consider a hash table \( P[0,1,\ldots,10] \) that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is \( h(x) = (x+7) \bmod 11 \).
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?

Show Hint

Simulate each insertion in order, computing h(x) = (x+7) mod 11, and moving to the next slot (wrapping past index 10 back to 0) whenever there is a collision.
Updated On: Jul 22, 2026
  • 0
  • 10
  • 2
  • 1
Show Solution

The Correct Option is C

Solution and Explanation

Method: Precompute the home slot for every key first, then simulate the insertions using that table.
Home slots using \( h(x) = (x+7) \bmod 11 \): h(1)=8, h(13)=9, h(22)=7, h(15)=0, h(11)=7, h(24)=9.
Insert in order 1, 13, 22, 15, 11, 24, filling the first free slot from each key's home slot, wrapping from 10 to 0:
1 to home 8, free, placed at 8.
13 to home 9, free, placed at 9.
22 to home 7, free, placed at 7.
15 to home 0, free, placed at 0.
11 to home 7 (taken); check 8 (taken), 9 (taken), 10 (free), placed at 10.
24 to home 9 (taken); check 10 (taken), 0 (taken, wrap-around), 1 (free), placed at 1.
Final occupancy: 0=15, 1=24, 2=empty, 3=empty, 4=empty, 5=empty, 6=empty, 7=22, 8=1, 9=13, 10=11.
Matching against the four given positions: 0 is filled, 10 is filled, 2 is empty, 1 is filled. Only position 2 remains empty among the listed choices.
\[ \boxed{\text{Option (C)}} \]
Was this answer helpful?
0

Questions Asked in GATE CS exam