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

Uncategorized

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

1. How many constraints are to be met to successfully implement quadratic probing?
A) 1
B) 2
C) 3
D) 4

Explanation: In terms of table size, there are two conditions that must be met. The table size should be a prime number, and no more than half of the table should be occupied.

2. Which among the following is the best technique to handle collision?
A) Quadratic probing
B) Linear probing
C) Double hashing
D) Separate chaining

Explanation: The primary collision that occurs in the linear probing process is handled by quadratic probing. Secondary collision does occur in quadratic probing, but it can be avoided by performing additional multiplications and divisions.

3. Which of the following techniques offer better cache performance?
A) Quadratic probing
B) Linear probing
C) Double hashing
D) Rehashing

Explanation: Linear probing outperforms quadratic probing in terms of cache efficiency while still preserving locality of reference.

4. 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: The formula for quadratic probing is hash key=(hash(x)+F(i2)) mod table size. The formula for linear probing is hash key = (hash(x)+F(i) mod table size.

5. For the given hash table, in what location will the element 58 be hashed using quadratic probing?

049
1
2
3
4
5
6
7
818
989

A) 1
B) 2
C) 7
D) 6

Explanation: 58 collides with spot 8 at first. One cell down, another collision occurs. As a result, F(i2)=4. The position is calculated using the quadratic probing formula as 2.

6. Which of the following schemes does quadratic probing come under?
A) rehashing
B) extended hashing
C) separate chaining
D) open addressing

Explanation: To fix collisions in hash tables, quadratic probing falls under the free addressing scheme.

7. Quadratic probing overcomes primary collision.
A) True
B) False

Explanation: Quadratic probing can solve the primary collision that occurs in linear probing, but it also causes a secondary collision.

8. What kind of deletion is implemented by hashing using open addressing?
A) active deletion
B) standard deletion
C) lazy deletion
D) no deletion

Explanation: In an open addressing hash table, standard deletion is not possible because the cells might have collided. As a result, hash tables use lazy deletion.

9. 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: If the table size is prime, we can insert a new element even if the table is exactly half full in quadratic probing. If the table size is more than half full, we won’t be able to insert an element.

10. 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: F(i)=i2 is the description of the quadratic probing function. The linear probing function is defined as F(i)=i.

When the hash function maps a key into a cell that is already occupied by another key, a hash collision occurs. Linear probing is a technique for resolving collisions that involves inserting the new key into the next empty cell after the collision. In computer programming, quadratic probing is an open addressing scheme for resolving hash collisions in hash tables. Quadratic probing works by adding successive values of an arbitrary quadratic polynomial to the original hash index until an open slot is found.

Leave a Reply

Your email address will not be published. Required fields are marked *