Page 120 - Data Structures Handout_Neat

9.9 Exercise

Essay Questions

1. Define hashing and explain its motivation compared to linear and binary search.
2. What are the properties of a good hash function?

3. Explain the difference between chaining and open addressing for collision resolution.

4. Implement a hash table in C++ using the division method and demonstrate insertion and

searching.

5. Implement linear probing and compare its performance with chaining.
6. Discuss real-world applications of hashing (e.g., database indexing, caching, password

storage).

Multiple Choice Questions (MCQ)
Q1. What is the main motivation behind using hashing?

a) To sort data efficiently

b) To achieve constant-time average case searching

c) To reduce memory usage compared to arrays

d) To replace binary search trees
Q2. Which of the following is a property of a good hash function?

a) Produces many collisions b) Distributes keys uniformly across the table

c) Depends only on the size of the table d) Always produces prime numbers
Q3. In the division method of hashing, the hash function is usually defined as:

a) ( ) = × b) ( ) =

c) ( ) = / d) ( ) =
Q4. Which collision resolution technique uses linked lists?

a) Linear probing b) Quadratic probing
c) Chaining d) Double hashing

Q5. What is the load factor in a hash table?

a) Ratio of table size to number of elements b) Ratio of number of elements to table size
c) Number of collisions per insertion d) Number of buckets in the table

Q6. Which of the following collision resolution techniques can suffer from clustering?

a) Chaining b) Linear probing

c) Quadratic probing d) Double hashing

120