Hash Tables with Quadratic Probing Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hash Tables with Quadratic Probing”.

1. 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.
advertisement

2. 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. 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.
advertisement
advertisement

4. 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. 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.
advertisement

6. 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. 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.
advertisement

8. 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. 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.
advertisement

10. 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.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter