The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty…
2009
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
- A.
Index
Values
0
1
2
2
3
23
4
5
15
6
7
8
18
9
- B.
Index
Values
0
1
2
12
3
13
4
5
5
6
7
8
18
9
- C.
Index
Values
0
1
2
12
3
13
4
2
5
3
6
23
7
5
8
18
9
15
- D.
Index
Values
0
1
2
12, 2
3
13, 3, 23
4
5
5, 15
6
7
8
18
9
Attempted by 167 students.
Show answer & explanation
Correct answer: C
Solution: Use h(k) = k mod 10 and linear probing to insert keys in the given order.
Insert 12: h(12) = 2 -> place 12 at index 2.
Insert 18: h(18) = 8 -> place 18 at index 8.
Insert 13: h(13) = 3 -> place 13 at index 3.
Insert 2: h(2) = 2 -> index 2 occupied by 12, probe to index 3 (occupied), probe to index 4 (empty) -> place 2 at index 4.
Insert 3: h(3) = 3 -> indices 3 and 4 are occupied, probe to index 5 (empty) -> place 3 at index 5.
Insert 23: h(23) = 3 -> indices 3,4,5 occupied, probe to index 6 (empty) -> place 23 at index 6.
Insert 5: h(5) = 5 -> index 5 occupied, probe to index 6 occupied, probe to index 7 (empty) -> place 5 at index 7.
Insert 15: h(15) = 5 -> indices 5,6,7,8 checked; index 8 is occupied, probe to index 9 (empty) -> place 15 at index 9.
Final table (index: value):
0: empty
1: empty
2: 12
3: 13
4: 2
5: 3
6: 23
7: 5
8: 18
9: 15
A video solution is available for this question — log in and enroll to watch it.