UGC NET Computer Science July 2018 - II | Question 23

Question 23

---

A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?

Options:

1. (1) 3
2. (2) 4
3. (3) 5
4. (4) 6

Answer : (3) 5

Explanation Question 23

Given:
Hash table has indexed from 0 to 6.
keys are 44, 45, 79, 55, 91, 18, 63
h(key)=key mod 7  ( h(key) value is in range of 0-6 inclusive)

Solution:

Table after inserting 44, 45
h(key)= key mod 7
h(44) = 44 mod 7 = 2
h(45) = 45 mod 7 = 3
44 is placed position 2 and 45 is placed at position 3.

0	1	2	3	4	5	6
-	-	44	45	-	-	-

Table after inserting 79
h(79) = 79 mod 7 = 2
but 2 is already filled by 44, linear probing is applied but 3 is also filled by 45.
To apply linear probing, we check for the next unoccupied position in the table.
So, 79 will occupy 4.

0	1	2	3	4	5	6
-	-	44	45	79	-	-

Table after inserting 55, 91
h(55) = 55 mod 7 = 6
h(91) = 91 mod 7 = 0
55 is placed position 6 and 91 is placed at position 0.

0	1	2	3	4	5	6
91	-	44	45	79	-	55

Table after inserting 18
h(18) = 18 mod 7 = 4
but 4 is occupied by 79 so, it will occupy 5.

0	1	2	3	4	5	6
91	-	44	45	79	18	55

Table after inserting 63
h(63) = 63 mod 7 = 0.
0 is also occupied so, it will occupy 1.

0	1	2	3	4	5	6
91	63	44	45	79	18	55

So, option (3) is correct.

Previous	Next
UGC NET CS 2018 July - II Question 22	UGC NET CS 2018 July - II Question 24