A hash table of length 10 uses open addressing with hash function h(k)=k mod…
2018
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 shown below is obtained:
- 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 303 students.
Show answer & explanation
Correct answer: C
Approach:
Hash function: h(k) = k mod 10, table indices 0..9.
Compute base hashes for the keys involved:
42 → 2, 23 → 3, 34 → 4, 52 → 2, 46 → 6, 33 → 3
Insert the values in the order 46, 34, 42, 23, 52, 33 and track each insertion:
Insert 46: h(46)=6 → index 6 is empty, place 46 at index 6.
Insert 34: h(34)=4 → index 4 is empty, place 34 at index 4.
Insert 42: h(42)=2 → index 2 is empty, place 42 at index 2.
Insert 23: h(23)=3 → index 3 is empty, place 23 at index 3.
Insert 52: h(52)=2 → index 2 occupied (42), probe to 3 occupied (23), probe to 4 occupied (34), probe to 5 empty, place 52 at index 5.
Insert 33: h(33)=3 → indices 3,4,5,6 are occupied, probe to 7 empty, place 33 at index 7.
Final table (index:value):
0: -
1: -
2: 42
3: 23
4: 34
5: 52
6: 46
7: 33
8: -
9: -
Conclusion: The insertion order 46, 34, 42, 23, 52, 33 yields the final table shown above, so the option containing that sequence is the correct choice.