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

Uncategorized

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

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

Explanation: The function used in linear probing is defined as, F(i)=I where i=0,1,2,3….,n.

2. ___________ is not a theoretical problem but actually occurs in real implementations of probing.
A) Hashing
B) Clustering
C) Rehashing
D) Collision

Explanation: Clustering is not a theoretical problem, but it does occur in hashing implementations. A form of hashing is rehashing.

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

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.

4. Hashing can be used in online spelling checkers.
A) True
B) False

Explanation: If misspelling detection is critical, an entire dictionary can be pre-hash and words tested in real time.

5. In the following given hash table, use linear probing to find the location of 49.

0
1
2
3
4
5
6
7
818
989

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

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.

6. What is the formula to find the expected number of probes for an unsuccessful search in linear probing?
A) 121+1(1−⅄)
B) 121+1(1−⅄)2
C) 121+1(1+⅄)
D) 121+1(1+⅄)(1−⅄)

Explanation: The mathematical formula for calculating the number of probes for an unsuccessful search is 121+1(1−⅄)2. For insertion, it is 121+1(1−⅄).

7. Which of the following problems occur due to linear probing?
A) Primary collision
B) Secondary collision
C) Separate chaining
D) Extendible hashing

Explanation: The linear probing technique causes the primary collision. A quadratic probing technique is used to solve it.

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

Explanation: The average number of probes needed for insertion is 2.5, and the average number of probes required for a successful search is 1.5, according to the formula.

9. What is the load factor for an open addressing technique?
A) 1
B) 0.5
C) 1.5
D) 0

Explanation: An open addressing technique should have a load factor of 0.5. The load factor for the separate chaining technique is 1.

10. Which of the following is not a collision resolution strategy for open addressing?
A) Linear probing
B) Quadratic probing
C) Double hashing
D) Rehashing

Explanation: Collision resolution techniques for open addressing include linear probing, quadratic probing, and double hashing, while rehashing is a different technique.

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

Explanation: The cost of an unsuccessful search can be used to calculate the average cost of a successful search using the random collision resolution algorithm.

Linear probing is a method of resolving collisions in hash tables, which are data structures for storing a list of key–value pairs and retrieving the value associated with a given key. Other hash functions, such as MurmurHash, may also produce good results in practise. Hash tables are a type of data structure that can be implemented in two ways: linear and non-linear. They’re frequently implemented using a linear data structure. As the hash table fills up, double hashing, like all other types of open addressing, becomes linear.

Leave a Reply

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