Engineering Questions with Answers - Multiple Choice Questions

# Hash Tables with Linear Probing MCQs

1 - Question

Which of the following problems occur due to linear probing? a) Primary collision b) Secondary collision c) Separate chaining d) Extendible hashing

2 - Question

How many probes are required on average for insertion and successful search? a) 4 and 10 b) 2 and 6 c) 2.5 and 1.5 d) 3.5 and 1.5
View Answer Answer: c Explanation: Using formula, the average number of probes required for insertion is 2.5 and for a successful search, it is 1.5.

3 - Question

What is the load factor for an open addressing technique? a) 1 b) 0.5 c) 1.5 d) 0

4 - Question

Which of the following is not a collision resolution strategy for open addressing? a) Linear probing b) Quadratic probing c) Double hashing d) Rehashing

5 - Question

In linear probing, the cost of an unsuccessful search can be used to compute the average cost of a successful search. a) True b) Answer: a Explanation: Using random collision resolution algorithm, the cost of an unsuccessful search can be used to compute the average cost of a successful search.
View Answer Answer: a Explanation: Using random collision resolution algorithm, the cost of an unsuccessful search can be used to compute the average cost of a successful search.

6 - Question

Which of the following is the correct function definition for linear probing? a) F(i)= 1 b) F(i)=i c) F(i)=i2 d) F(i)=i+1

7 - Question

___________ is not a theoretical problem but actually occurs in real implementations of probing. a) Hashing b) Clustering c) Rehashing d) Collision
View Answer Answer: b Explanation: Clustering is not a theoretical problem but it occurs in implementations of hashing. Rehashing is a kind of hashing.

8 - Question

What is the hash function used in linear probing? a) H(x)= key mod table size b) H(x)= (key+ F(i2)) mod table size c) H(x)= (key+ F(i)) mod table size d) H(x)= X mod 17
View Answer Answer: c Explanation: The hash function used in linear probing is defined to be H(x)= (key+ F(i)) mod table size where i=0,1,2,3,…,n.

9 - Question

Hashing can be used in online spelling checkers. a) True b) False
View Answer Answer: a Explanation: If misspelling detection is important, an entire dictionary can be pre-hashed and words can be checked in constant time.

10 - Question

In the following given hash table, use linear probing to find the location of 49.
 0 1 2 3 4 5 6 7 8 18 9 89
a) 7 b) 6 c) 2 d) 0
View Answer Answer: d Explanation: Initially, collision occurs while hashing 49 for the first time. Hence, after setting f(i)=1, the hashed location is found to be 0.

11 - Question

What is the formula to find the expected number of probes for an unsuccessful search in linear probing? a) 121+1(1−⅄) b) 121+1(1−⅄)2 c) 121+1(1+⅄) d) 121+1(1+⅄)(1−⅄)
View Answer Answer: b Explanation: The mathematical formula for calculating the number of probes for an unsuccessful search is 121+1(1−⅄)2. For insertion, it is 121+1(1−⅄).