GATE CS 2009 Q36 — Arrays, Stacks and Queues

To find the resultant hash table, we insert the keys one by one into an initially empty hash table of size $10$ (with indices $0$ to $9$) using the hash function $h(k) = k \bmod 10$ and linear probing to resolve collisions.

Let's trace the insertion of each key step-by-step:

1. Insert 12:
   $h(12) = 12 \bmod 10 = 2$. Slot $2$ is empty. Insert 12 at slot $2$.
2. Insert 18:
   $h(18) = 18 \bmod 10 = 8$. Slot $8$ is empty. Insert 18 at slot $8$.
3. Insert 13:
   $h(13) = 13 \bmod 10 = 3$. Slot $3$ is empty. Insert 13 at slot $3$.
4. Insert 2:
   $h(2) = 2 \bmod 10 = 2$. Slot $2$ is occupied by $12$.
   Probe slot $3$: occupied by $13$.
   Probe slot $4$: empty. Insert 2 at slot $4$.
5. Insert 3:
   $h(3) = 3 \bmod 10 = 3$. Slot $3$ is occupied by $13$.
   Probe slot $4$: occupied by $2$.
   Probe slot $5$: empty. Insert 3 at slot $5$.
6. Insert 23:
   $h(23) = 23 \bmod 10 = 3$. Slot $3$ is occupied.
   Probe slot $4$: occupied.
   Probe slot $5$: occupied.
   Probe slot $6$: empty. Insert 23 at slot $6$.
7. Insert 5:
   $h(5) = 5 \bmod 10 = 5$. Slot $5$ is occupied.
   Probe slot $6$: occupied.
   Probe slot $7$: empty. Insert 5 at slot $7$.
8. Insert 15:
   $h(15) = 15 \bmod 10 = 5$. Slot $5$ is occupied.
   Probe slot $6$: occupied.
   Probe slot $7$: occupied.
   Probe slot $8$: occupied by $18$.
   Probe slot $9$: empty. Insert 15 at slot $9$.

The final state of the hash table is:

This matches the table given in Option C.