UGC NET CSE | October 2022 | Part 1 | Question: 12

Question

Consider the hash table of size $11$ that uses open addressing with linear probing. Let $h(k)=k$ $\text{mod}$ $11$ be the hash function. A sequence of records with keys $43, 36, 92, 87. 11 . 47. 11, 13, 14$ is inserted into an initially empty hash table, the bins of which are indexed from $0$ to $10$. What is the index of the bin into which the last record is inserted?

• A. $8$
• B. $7$ 
• C. $10$
• D. $4$

Answer 1

Keys are 43,36,92,87,11,47,11,13,14.
h(1) = 43 % 11 = 10
h(2) = 36 % 11 = 3
h(3) = 92 % 11 = 4
h(4) = 87 % 11 = 10
Now, collision occurs due to index places is same.
The element is allotted next nearest place that is 0 index.
h(4) = 87 % 11 = 0
h(5) = 11 % 11 = 0
Now, collision occurs due to index places is same.
The element is allotted next nearest place that is 1 index.
h(5) = 11 % 11 = 1
h(6) = 47 % 11 = 3
Now, collision occurs due to index places is same.
The element is allotted next nearest place that is 4 index.
index 4 is already allotted to h(3).
The element is allotted next nearest place that is 5 index.
Get Started
h(6) = 47 % 11 = 5
h(7) = 11 % 11 = 0
Now, collision occurs due to index places is same.
The element is allotted next nearest place that is 1 index.
index 1 is already allotted to h(5).
The element is allotted next nearest place that is 2 index.
h(7) = 11 % 11 = 2
h(8) = 13 % 11 = 2
Now, collision occurs due to index places is same.
The element is allotted next nearest place that is 3 index.
index 3 is already allotted to h(2).
The element is allotted next nearest place that is 4 index.
index 4 is already allotted to h(3).
The element is allotted next nearest place that is 5 index.
index 5 is already allotted to h(6).
The element is allotted next nearest place that is 6 index.
h(8) = 13 % 11 = 6
h(9) = 14 % 11 = 3
Now, collision occurs due to index places is same.
The element is allotted next nearest place that is 4 index.
index 4 is already allotted to h(3).
The element is allotted next nearest place that is 5 index.
index 5 is already allotted to h(3).
The element is allotted next nearest place that is 6 index.
index 6 is already allotted to h(8).
The element is allotted next nearest place that is 7 index.
h(9) = 14 % 11 = 7.