Engineering Questions with Answers - Multiple Choice Questions
Hash Tables with Quadratic Probing Multiple Choice MCQ
1 - Question
Which of the following schemes does quadratic probing come under?
a) rehashing
b) extended hashing
c) separate chaining
d) open addressing
View Answer
Answer: d
Explanation: Quadratic probing comes under open addressing scheme to resolve collisions in hash tables.
2 - Question
Quadratic probing overcomes primary collision.
a) True
b) False
View Answer
Answer: a
Explanation: Quadratic probing can overcome primary collision that occurs in linear probing but a secondary collision occurs in quadratic probing.
3 - Question
What kind of deletion is implemented by hashing using open addressing?
a) active deletion
b) standard deletion
c) lazy deletion
d) no deletion
View Answer
Answer: c
Explanation: Standard deletion cannot be performed in an open addressing hash table, because the cells might have caused collision. Hence, the hash tables implement lazy deletion.
4 - Question
In quadratic probing, if the table size is prime, a new element cannot be inserted if the table is half full.
a) True
b) False
View Answer
Answer: b
Explanation: In quadratic probing, if the table size is prime, we can insert a new element even though table is exactly half filled. We can’t insert element if table size is more than half filled.
5 - Question
Which of the following is the correct function definition for quadratic probing?
a) F(i)=i2
b) F(i)=i
c) F(i)=i+1
d) F(i)=i2+1
View Answer
Answer: a
Explanation: The function of quadratic probing is defined as F(i)=i2. The function of linear probing is defined as F(i)=i.
6 - Question
How many constraints are to be met to successfully implement quadratic probing?
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: b
Explanation: 2 requirements are to be met with respect to table size. The table size should be a prime number and the table size should not be more than half full.
7 - Question
Which among the following is the best technique to handle collision?
a) Quadratic probing
b) Linear probing
c) Double hashing
d) Separate chaining
View Answer
Answer: a
Explanation: Quadratic probing handles primary collision occurring in the linear probing method. Although secondary collision occurs in quadratic probing, it can be removed by extra multiplications and divisions.
8 - Question
Which of the following techniques offer better cache performance?
a) Quadratic probing
b) Linear probing
c) Double hashing
d) Rehashing
View Answer
Answer: b
Explanation: Linear probing offers better cache performance than quadratic probing and also it preserves locality of reference.
9 - Question
What is the formula used in quadratic probing?
a) Hash key = key mod table size
b) Hash key=(hash(x)+F(i)) mod table size
c) Hash key=(hash(x)+F(i2)) mod table size
d) H(x) = x mod 17
View Answer
Answer: c
Explanation: Hash key=(hash(x)+F(i2)) mod table size is the formula for quadratic probing. Hash key = (hash(x)+F(i)) mod table size is the formula for linear probing.
10 - Question
For the given hash table, in what location will the element 58 be hashed using quadratic probing?
| 0 | 49 |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | 18 |
| 9 | 89 |
a) 1
b) 2
c) 7
d) 6
View Answer
Answer: b
Explanation: Initially, 58 collides at position 8. Another collision occurs one cell away. Hence, F(i2)=4. Using quadratic probing formula, the location is obtained as 2.