University:
California State University, Northridge
Course:
COMP 182 | Data Structures and Program Design and Lab
Academic year:

2022
Views:

19

Pages:

8
Author:

NyiH

Question 1 What is the hash function used in linear probing? H(x)= key mod table size H(x)= (key+ F(12)) mod table size H(x)= (key+F(i)) mod table size H(x)= X mod 17 Question 2 is not a theoretical problem but actually occurs in real implementations of probing. Hashing Clustering Rehashing Collision Question 3 Which of the following problems occur due to linear probing? Primary collision Secondary collision Separate chaining Extendible hashing Question 4 What is the load factor for an open addressing technique? 1 0.5 1.5 00 Question 5 Which of the following is not a collision resolution strategy for open addressing? Linear probing Quadratic probing Double hashing Rehashing Question 6 Which of the following schemes does quadratic probing come under? rehashing extended hashing separate chaining open addressing Question 7 What is the formula used in quadratic probing? Hash key = key mod table size Hash key=(hash(x)+F(i)) mod table size Hash key=(hash(x)+F(i2)) mod table size H(x)=x mod 17 Question 8 Which of the following techniques offer better cache performance? Quadratic probing Linear probing Double hashing Rehashing Question 9 Which of the following is the correct function definition for quadratic probing? F(i)=12 F(i)=i F(i)=i+1 F(i)=i2+1 Question 10 What is the hash function used in Double Hashing? (h1(k) -i*h2(k))mod m h1(k) +h2(k) (h1(k)+i*h2(k))mod m (h1(k)+h2(k))mod m Question 11 On what value does the probe sequence depend on? c1 k c2 m Question 12 Which technique has the greatest number of probe sequences? Linear probing Quadratic probing Double hashing Closed hashing Question 13 When is it appropriate to use direct addressing? When the array is comparatively large When the universe U of keys is reasonably small When the universe U of keys is reasonably large When the array is comparatively small Question 14 What is the search complexity in direct addressing? O(n) O(logn) O(nlogn) O(1) Question 15 What is the advantage of using a dynamic set in direct addressing? It saves time It saves space It saves both time and space It reduces code complexity