edited by
7,258 views
32 votes
32 votes

The keys $12, 18, 13, 2, 3, 23, 5$ and $15$ are inserted into an initially empty hash table of length $10$ using open addressing with hash function $h(k) = k \mod 10$ and linear probing. What is the resultant hash table?

  1. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 2  \\\hline 3 & 23 \\\hline 4 &  \\\hline 5 & 15 \\\hline 6 &   \\\hline 7 &  \\\hline 8 & 18 \\\hline 9 &  \\\hline  \end{array}$ 
  2. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 12  \\\hline 3 & 13 \\\hline 4 &  \\\hline 5 & 5 \\\hline 6 &   \\\hline 7 &  \\\hline 8 & 18 \\\hline 9 &  \\\hline  \end{array}$
  3. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 12  \\\hline 3 & 13 \\\hline 4 & 2 \\\hline 5 & 3 \\\hline 6 & 23   \\\hline 7 & 5  \\\hline 8 & 18 \\\hline 9 & 15  \\\hline  \end{array}$
  4. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 2,12   \\\hline 3 & 13,3,23  \\\hline 4 &  \\\hline 5 & 5,15   \\\hline 6 &   \\\hline 7 &  \\\hline 8 & 18 \\\hline 9 &  \\\hline  \end{array}$
edited by

2 Answers

Best answer
35 votes
35 votes

(C) is the correct option ..directly from the definition of linear probing. In linear probing, when a hashed location is already filled, locations are linearly probed until a free one is found. 

http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture16/sld015.htm

edited by
12 votes
12 votes
Here A & B options are incorrect, this is obvious. We are inserting 8 keys but only 4 are present. Hash is data structure for storing data, we don't loose data in Hash.

D is incorrect because it looks like chaining .

Using Linear Probing we get hash table of C. In linear probing, when a hashed location is already filled, locations are linearly probed until a free one is found.
Answer:

Related questions

24 votes
24 votes
3 answers
1
39 votes
39 votes
5 answers
2
Kathleen asked Sep 22, 2014
43,284 views
What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$.$2$$3$$4$$5$
23 votes
23 votes
3 answers
3
Kathleen asked Sep 22, 2014
13,641 views
Consider a binary max-heap implemented using an array.Which one of the following array represents a binary max-heap?$\left\{25,12,16,13,10,8,14\right\}$ $\left\{25,14,...