GATE CS 2014 Set 1 Q40 — Arrays, Stacks and Queues

To find the maximum, minimum, and average chain lengths, we map each key to its corresponding slot in the hash table of size $9$ using the hash function $h(k) = k \bmod 9$.

Let's compute the slot index for each key in the order of insertion:

• $h(5) = 5 \bmod 9 = 5$
• $h(28) = 28 \bmod 9 = 1$
• $h(19) = 19 \bmod 9 = 1$
• $h(15) = 15 \bmod 9 = 6$
• $h(20) = 20 \bmod 9 = 2$
• $h(33) = 33 \bmod 9 = 6$
• $h(12) = 12 \bmod 9 = 3$
• $h(17) = 17 \bmod 9 = 8$
• $h(10) = 10 \bmod 9 = 1$

Now, we group the keys into their respective slots (chains):

• Slot 0: Empty (Chain length = $0$)
• Slot 1: $28 \to 19 \to 10$ (Chain length = $3$)
• Slot 2: $20$ (Chain length = $1$)
• Slot 3: $12$ (Chain length = $1$)
• Slot 4: Empty (Chain length = $0$)
• Slot 5: $5$ (Chain length = $1$)
• Slot 6: $15 \to 33$ (Chain length = $2$)
• Slot 7: Empty (Chain length = $0$)
• Slot 8: $17$ (Chain length = $1$)

From the slot distribution, we can determine the required metrics:

1. Maximum chain length: The longest chain is at Slot 1, which has a length of $\mathbf{3}$.
2. Minimum chain length: Slots 0, 4, and 7 are empty, so the minimum chain length is $\mathbf{0}$.
3. Average chain length: $$\text{Average} = \frac{\text{Total number of keys}}{\text{Total number of slots}} = \frac{9}{9} = \mathbf{1}$$

Thus, the maximum, minimum, and average chain lengths are $3, 0,$ and $1$ respectively.