Skip to content
GATETECH
Official PYQ · 2010Q52Arrays, Stacks and QueuesMCQ1 mark

GATE CS 2010 Q52 — Arrays, Stacks and Queues

Explain with AI

A hash table of length 1010 uses open addressing with hash function h(k)=kmod  10h(k) = k \mod 10, and linear probing. After inserting 66 values into an empty hash table, the table is shown as below

0124232343455264673389\begin{array}{|l|l|}\hline \text{0} & \text{} \\ \hline \text{1} & \text{} \\ \hline \text{2} & \text{42} \\ \hline \text{3} & \text{23} \\ \hline \text{4} & \text{34} \\ \hline \text{5} & \text{52} \\ \hline \text{6} & \text{46} \\ \hline \text{7} & \text{33} \\ \hline \text{8} & \text{} \\ \hline \text{9} & \text{} \\ \hline \end{array}

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

Choose one option
View worked solution

Answer: C

To find the correct insertion order, let us first compute the primary hash value h(k)=k mod 10h(k) = k \bmod 10 for each key:

  • h(42)=2h(42) = 2
  • h(23)=3h(23) = 3
  • h(34)=4h(34) = 4
  • h(52)=2h(52) = 2
  • h(46)=6h(46) = 6
  • h(33)=3h(33) = 3

Now, we trace the insertion sequence given in Option C (46,34,42,23,52,3346, 34, 42, 23, 52, 33):

  1. Insert 46: h(46)=6h(46) = 6. Index 6 is empty, so 46 is placed at index 6.
  2. Insert 34: h(34)=4h(34) = 4. Index 4 is empty, so 34 is placed at index 4.
  3. Insert 42: h(42)=2h(42) = 2. Index 2 is empty, so 42 is placed at index 2.
  4. Insert 23: h(23)=3h(23) = 3. Index 3 is empty, so 23 is placed at index 3.
  5. Insert 52: h(52)=2h(52) = 2. Index 2 is occupied (by 42). Probing sequentially: index 3 is occupied (by 23), index 4 is occupied (by 34), index 5 is empty. So, 52 is placed at index 5.
  6. Insert 33: h(33)=3h(33) = 3. Index 3 is occupied (by 23). Probing sequentially: indices 4, 5, and 6 are occupied. Index 7 is empty, so 33 is placed at index 7.

This sequence perfectly matches the final state of the hash table. Other options fail; for example, in Option A, inserting 52 before 23 would place 52 at index 3, which contradicts the final table.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Arrays, Stacks and Queues questions