Engineering Questions with Answers - Multiple Choice Questions

Home » MCQs » Chemical Engineering » Hash Tables with Linear Probing MCQ’s

# Hash Tables with Linear Probing MCQ’s

Which of the following problems occur due to linear probing?

a) Primary collision

b) Secondary collision

c) Separate chaining

d) Extendible hashing

**
View Answer**

Answer: a

Explanation: Primary collision occurs due to linear probing technique. It is overcome using a quadratic probing technique.

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

**
View Answer**

Answer: c

Explanation: Using formula, the average number of probes required for insertion is 2.5 and for a successful search, it is 1.5.

What is the load factor for an open addressing technique?

a) 1

b) 0.5

c) 1.5

d) 0

**
View Answer**

Answer: b

Explanation: The load factor for an open addressing technique should be 0.5. For separate chaining technique, the load factor is 1.

Which of the following is not a collision resolution strategy for open addressing?

a) Linear probing

b) Quadratic probing

c) Double hashing

d) Rehashing

**
View Answer**

Answer: d

Explanation: Linear probing, quadratic probing and double hashing are all collision resolution strategies for open addressing whereas rehashing is a different technique.

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

**
View Answer**

Answer: a

Explanation: Using random collision resolution algorithm, the cost of an unsuccessful search can be used to compute the average cost of a successful search.

Which of the following is the correct function definition for linear probing?

a) F(i)= 1

b) F(i)=i

c) F(i)=i^{2}

d) F(i)=i+1

**
View Answer**

Answer: b

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

_________ is not a theoretical problem but actually occurs in real implementations of probing.

a) Hashing

b) Clustering

c) Rehashing

d) Collision

**
View Answer**

Answer: b

Explanation: Clustering is not a theoretical problem but it occurs in implementations of hashing. Rehashing is a kind of hashing.

What is the hash function used in linear probing?

a) H(x)= key mod table size

b) H(x)= (key+ F(i^{2})) mod table size

c) H(x)= (key+ F(i)) mod table size

d) H(x)= X mod 17

**
View Answer**

Answer: c

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.

Hashing can be used in online spelling checkers.

a) True

b) False

**
View Answer**

Answer: a

Explanation: If misspelling detection is important, an entire dictionary can be pre-hashed and words can be checked in constant time.

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

0 | |

1 | |

2 | |

3 | |

4 | |

5 | |

6 | |

7 | |

8 | 18 |

9 | 89 |

a) 7

b) 6

c) 2

d) 0

**
View Answer**

Answer: d

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.

What is the formula to find the expected number of probes for an unsuccessful search in linear probing?

a) \(\frac{1}{2} \frac{1+1}{(1-⅄)}\)

b) \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\)

c) \(\frac{1}{2}\frac{1+1}{(1+⅄)}\)

d) \(\frac{1}{2}\frac{1+1}{(1+⅄)(1-⅄)}\)

**
View Answer**

Answer: b

Explanation: The mathematical formula for calculating the number of probes for an unsuccessful search is \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\). For insertion, it is \(\frac{1}{2} \frac{1+1}{(1-⅄)}\).