Q21GATE 2007MCQ

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that '-' denotes an empty location in the table.

🚀 Solve in Practice Mode

📖 Explanation

The hash table size is $M=7$ and the hash function is $h(x) = (3x + 4) \pmod 7$ . Closed hashing implies linear probing for collision resolution.

Insert 1: $h(1) = (3 \times 1 + 4) \pmod 7 = 7 \pmod 7 = 0$ .
Table: [1, -, -, -, -, -, -]
Insert 3: $h(3) = (3 \times 3 + 4) \pmod 7 = 13 \pmod 7 = 6$ .
Table: [1, -, -, -, -, -, 3]
Insert 8: $h(8) = (3 \times 8 + 4) \pmod 7 = 28 \pmod 7 = 0$ . Index 0 is occupied by 1.
Probe 1: $(0+1) \pmod 7 = 1$ . Index 1 is empty. Insert 8 at index 1.
Table: [1, 8, -, -, -, -, 3]
Insert 10: $h(10) = (3 \times 10 + 4) \pmod 7 = 34 \pmod 7 = 6$ . Index 6 is occupied by 3.
Probe 1: $(6+1) \pmod 7 = 0$ . Index 0 is occupied by 1.
Probe 2: $(0+1) \pmod 7 = 1$ . Index 1 is occupied by 8.
Probe 3: $(1+1) \pmod 7 = 2$ . Index 2 is empty. Insert 10 at index 2.
Final table: [1, 8, 10, -, -, -, 3]

Q23GATE 2005MCQ

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?

🚀 Solve in Practice Mode

📖 Explanation

The hash function is $h(k) = k \pmod{10}$ .
Inserting 43: $h(43) = 3$ (Index 3); 165: $h(165) = 5$ (Index 5); 62: $h(62) = 2$ (Index 2).
Inserting 123: $h(123) = 3$ . Index 3 is occupied, so linear probe to index 4.
Inserting 142: $h(142) = 2$ . Indices 2, 3, 4, and 5 are occupied (by 62, 43, 123, and 165 respectively).
The next available slot via linear probing is index 6, where 142 is inserted.

Q24GATE 2004MCQ

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to the same value ii) 1471, 6171 has to the same value iii) All elements hash to the same value iv) Each element hashes to a different value

🚀 Solve in Practice Mode

📖 Explanation

The hash function $h(x) = x \mod 10$ returns the last digit of each number in the set.
Calculating the hashes: $4322 \to 2$ , $1334 \to 4$ , $1471 \to 1$ , $9679 \to 9$ , $1989 \to 9$ , $6171 \to 1$ , $6173 \to 3$ , $4199 \to 9$ .
Grouping the results: Hash $1 = \{1471, 6171\}$ and Hash $9 = \{9679, 1989, 4199\}$ .
Statement i is true as $9679, 1989,$ and $4199$ all hash to $9$ .
Statement ii is true as $1471$ and $6171$ both hash to $1$ .
Since there are multiple hash values (not iii) and collisions exist (not iv), only i and ii are true.

Q25MCQ

An advantage of chained hash table (external hashing) over the open addressing scheme is

🚀 Solve in Practice Mode

Q26MCQ

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

\begin{array}{|l|l|} \hline 0 & \text { S7 } \\ \hline 1 & \text { S1 } \\ \hline 2 & \\ \hline 3 & \text { S4 } \\ \hline 4 & \text { S2 } \\ \hline 5 & \text { } \\ \hline 6 & \text { S5 } \\ \hline 7 & \\ \hline 8 & \text { S6 } \\ \hline 9 & \text { S3 } \\ \hline \end{array}

🚀 Solve in Practice Mode

📖 Explanation

To search for an item not present in a hash table using linear probing, one must probe the sequence starting from the hash index until an empty slot is encountered. The empty slots in the given table are at indices $2, 5$ , and $7$ .

We analyze the linear probing chains (clusters) of occupied slots:

Cluster 1: indices $\{8, 9, 0, 1\}$ leading to the empty slot $2$ .
Cluster 2: indices $\{3, 4\}$ leading to the empty slot $5$ .
Cluster 3: index $\{6\}$ leading to the empty slot $7$ .

If an item hashes to index $8$ , we compare the key against the contents of slots $8, 9, 0, 1$ , and finally confirm the absence at index $2$ . This requires $5$ comparisons ( $4$ key comparisons + $1$ empty slot check). Other starting positions result in fewer comparisons. Thus, the maximum number of comparisons needed is $5$ .