Engineering Questions with Answers - Multiple Choice Questions
Hash Tables with Linear Probing MCQ’s
1 - Question
Which of the following problems occur due to linear probing?
a) Primary collision
b) Secondary collision
c) Separate chaining
d) Extendible hashing
View Answer
Answer: a
Explanation: Primary collision occurs due to linear probing technique. It is overcome using a quadratic probing technique.
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
View Answer
Answer: b
Explanation: The load factor for an open addressing technique should be 0.5. For separate chaining technique, the load factor is 1.
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
View Answer
Answer: d
Explanation: Linear probing, quadratic probing and double hashing are all collision resolution strategies for open addressing whereas rehashing is a different technique.
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) False
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
View Answer
Answer: b
Explanation: The function used in linear probing is defined as, F(i)=I where i=0,1,2,3….,n.
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) \(\frac{1}{2} \frac{1+1}{(1-⅄)}\)
b) \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\)
c) \(\frac{1}{2}\frac{1+1}{(1+⅄)}\)
d) \(\frac{1}{2}\frac{1+1}{(1+⅄)(1-⅄)}\)
View Answer
Answer: b
Explanation: The mathematical formula for calculating the number of probes for an unsuccessful search is \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\). For insertion, it is \(\frac{1}{2} \frac{1+1}{(1-⅄)}\).