edited by
6,581 views
23 votes
23 votes

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

$$\begin{array}{|l|l|}\hline \text{0}  &  \text{} \\ \hline \text{1} & \text{} \\\hline  \text{2} & \text{42} \\ \hline  \text{3} & \text{23} \\\hline   \text{4} & \text{34} \\\hline   \text{5} & \text{52} \\\hline   \text{6} & \text{46} \\\hline   \text{7} & \text{33} \\\hline   \text{8} & \text{} \\\hline   \text{9} & \text{} \\\hline   \end{array}$$

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$
edited by

3 Answers

Best answer
25 votes
25 votes

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
2 votes
2 votes
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
Answer:

Related questions

73 votes
73 votes
10 answers
1
go_editor asked Apr 21, 2016
26,928 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...
57 votes
57 votes
12 answers
3
go_editor asked Sep 29, 2014
16,072 views
In a binary tree with $n$ nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree ...