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

Explanation: Quadratic probing comes under open addressing scheme to resolve collisions in hash tables.

2 - Question

a) True
b) False

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

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

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

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

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?
b) Linear probing
c) Double hashing
d) Separate chaining

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?
b) Linear probing
c) Double hashing
d) Rehashing

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

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