A hash table of length 10 uses open addressing with hash function h(k)=k mod…
2010
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below
\(\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}\)
How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
- A.
46, 42, 34, 52, 23, 33
- B.
34, 42, 23, 52, 33, 46
- C.
46, 34, 42, 23, 52, 33
- D.
42, 46, 33, 23, 34, 52
Attempted by 78 students.
Show answer & explanation
Correct answer: C
Hash function: h(k) = k mod 10. Linear probing resolves collisions by probing the next slot (wrapping around) until an empty slot is found.
Home positions:
46 → 6
42 → 2
34 → 4
23 → 3
52 → 2
33 → 3
Key constraints:
46 must be inserted before any key that probes to 6 (only 46 hashes to 6).
42 must be inserted before 52 (both hash to 2, and 42 must be placed before 52 can probe to 5).
23 must be inserted before 33 (both hash to 3, and 23 must be placed before 33 can probe to 7).
34 must be inserted before 52 (34 hashes to 4, and 52 probes to 4 before 5).
33 must be inserted before 46 (33 probes to 6, so 6 must be empty when 33 is inserted).
Valid insertion sequences must satisfy these constraints. The number of valid permutations is the number of topological orderings of the dependency graph. The constraints form a partial order. The keys 46, 42, 34, 23, 52, 33 must be ordered such that:
46 before 33 (since 33 probes to 6)
42 before 52 (since 52 probes to 2,3,4,5)
23 before 33 (since 33 probes to 3,4,5,6,7)
34 before 52 (since 52 probes to 4)
The number of valid sequences is 4. The valid sequences are those where 46 is inserted before 33, 42 before 52, 23 before 33, and 34 before 52. The total number of valid permutations is 4.