Question

Data structure and Algorithm

A hash table of length 10 using open addressing with hash function h(k) = k mod 10, and linear probing has been created.

0
1
2	32
3	73
4	12
5	15
6	82
7	37
8	65
9	9

Now the item 12 needs to be deleted using “Deletion with repair’. What is the resultant hash table?

A)

0
1
2	32
3	73
4	15
5	82
6	37
7	65
8	9
9

B)

0
1
2	32
3	73
4	82
5	15
6
7	37
8	65
9	9

C) None of the options provided represent the hash table that would result.

D)

0
1
2	32
3	73
4	82
5	15
6	65
7	37
8
9	9

E)

0
1
2	32
3	73
4
5	15
6	82
7	37
8	65
9	9

Answer 1

The answer will be the option D

i.e

0
1
2	32
3	73
4	82
5	15
6	65
7	37
8
9	9

Because after deletion of '12' , if we search for 82 then ,

1) it first searches at index = (82%10) = 2 but it is occupied by '32'.

2) it then searches at index = ((82%10) +1)%10 = 3, it is also occupied by '73'.

3) similarly , it then searches at index = 4 and finds it empty . So the search will terminate saying that 82 is not present in table which is wrong. So, 82 must move to index = 4.

Searching for 65.

1) it first searches at index = (65%10) = 5 but it is occupied by ''15'.

2) it then searches at index = ((65%10) +1)%10 = 6 and finds it empty . So the search will terminate saying that 65 is not present in table which is wrong. So, 65 must move at index = 6.