The following keys 22, 28, 23, 12 and 13 are inserted into initially empty…
2021
The following keys 22, 28, 23, 12 and 13 are inserted into initially empty hash table of length 9 using open addressing with hash function h(k)=k mod 9 and linear probing. At what index key 13 is inserted?
- A.
4
- B.
5
- C.
6
- D.
7
Attempted by 259 students.
Show answer & explanation
Correct answer: C
To determine where key 13 is inserted, we use the hash function h(k) = k mod 9 and linear probing for collision resolution.
Step 1: Insert key 22. h(22) = 22 mod 9 = 4. Insert at index 4.
Step 2: Insert key 28. h(28) = 28 mod 9 = 1. Insert at index 1.
Step 3: Insert key 23. h(23) = 23 mod 9 = 5. Insert at index 5.
Step 4: Insert key 12. h(12) = 12 mod 9 = 3. Insert at index 3.
Step 5: Insert key 13. h(13) = 13 mod 9 = 4. Index 4 is occupied by key 22, so we probe linearly: index 5 is occupied by key 23, index 6 is free. Insert key 13 at index 6.