Consider a hash table of size 11 that uses open addressing with linear…
2008
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys
43 36 92 87 11 4 71 13 14
is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?
- A.
3
- B.
4
- C.
6
- D.
7
Attempted by 159 students.
Show answer & explanation
Correct answer: D
Final answer: index 7.
Explanation: use h(k) = k mod 11 and linear probing to resolve collisions. Process the keys in order:
Insert 43: h(43)=10 -> place at index 10.
Insert 36: h(36)=3 -> place at index 3.
Insert 92: h(92)=4 -> place at index 4.
Insert 87: h(87)=10 -> index 10 occupied, probe to 0 -> place at index 0.
Insert 11: h(11)=0 -> index 0 occupied, probe to 1 -> place at index 1.
Insert 4: h(4)=4 -> index 4 occupied, probe to 5 -> place at index 5.
Insert 71: h(71)=5 -> index 5 occupied, probe to 6 -> place at index 6.
Insert 13: h(13)=2 -> place at index 2.
Insert 14: h(14)=3 -> index 3 occupied, probe to 4 (occupied), 5 (occupied), 6 (occupied), 7 is free -> place at index 7.
Therefore the last record (key 14) is inserted into bin index 7.
A video solution is available for this question — log in and enroll to watch it.