# GATE2009-36

2.1k views

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}$
in DS
edited

(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
9
Note:

Separate Chaining  = Open Hashing/Closed Addressing (i.e. each key has a linked list, hence no probing)

Closed Hashing/Open Addressing (single array shared, hence probing required)
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.

## Related questions

1
2.3k views
Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$ $\left\{14,13,12,10, 8\right\}$ $\left\{14,12,13,8,10\right\}$ $\left\{14,13,8,12,10\right\}$ $\left\{14,13,12,8,10\right\}$
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,13,16,10,8,12\right\}$ $\left\{25,14,16,13,10,8,12\right\}$ $\left\{25,14,12,13,10,8,16\right\}$
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$
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the ... is $\langle 0, 15, 31 \rangle$ $\langle 0, 16, 30 \rangle$ $\langle 0, 16, 31 \rangle$ $\langle 0, 17, 31 \rangle$