1.9k views

A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ values into an empty hash table, the table is shown as below

 $0$ $1$ $2$ $42$ $3$ $23$ $4$ $34$ $5$ $52$ $6$ $46$ $7$ $33$ $8$ $9$

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

1. $46, 42, 34, 52, 23, 33$
2. $34, 42, 23, 52, 33, 46$
3. $46, 34, 42, 23, 52, 33$
4. $42, 46, 33, 23, 34, 52$
retagged | 1.9k views
+1

A)  46, 42, 34, 52, 23, 33

now...46,42,34....will be inserted without any problem...but 52 creates problem..if we use this sequence then 52 will check and it find 42  there in 3rd slot so ..there is collission so it will look for next slot..which empty...so 52 will be placed..in slot no.-3...so we won't get above table..for this sequence..

B)34, 42, 23, 52, 33, 46

34,42,23,52..will be placed without any problem...but 33 creates problem..if we use this sequence then 33 will check  .there is collission so it will look for next slot -3..which filled with 23 then next slot-4 which is also filled with 34...then next slot-5 which is also filled with 52..then next slot-6 which is free so..33 will be placed in 6..slot..which not the right input..coz in 6 slot..46 need to be placed..

D)42, 46, 33, 23, 34, 52

42,46, will be placed without any problem..33 creates problem...slot 3 is free and 33 will be placed in it..but in table in 3rd slot..23 is dere so..it is also wrong..

C)...it will b placed without ..any problem..

+1
thank u so much @tauhin_gangwar i understood now :)

Option (C)

$46, 34, 42, 23, 52, 33$

$46 -$ position $6$

$34$ position $4$

$42$ position $2$

$23$ position $3$

$52$ position $2 -$ collision next empty is $5$

$33$ position $3 -$ collision next empty is $7$

edited by
0
Analysed hash table and see that 33 has to come last.Remove options B and D.

In (A) 52 comes before 23, so that is irelevant.Remove (A).

Ans-(C)

answer = option C : solve by checking each option

taking each option and drawing hash table is not fastest approach

option elimination will be correct approach here

by looking at given hash table we draw following conclusion

1) 52 must come after 42 , hence sequence is 42 , 52

2)33 must come after 33 hence sequence is 23 ,33

3)52 must come after 23 & 34 . note that order between 23 and 34 does not matter

4)33 must come after 34 52 & 46 note that order between this three number does not matter

now check each option , you will find c is correct

1
2