PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q7

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

Insert 2, 3, 9, 6, 11, 13, 7, 12 in a hash table using modulo division method with 2*k+3 as hash function. Resolve collision using double hashing. Take second hash function as 3*k+1.

Solution

Choosing Table Size : The problem does not state the table size , so following the exam instruction ("Assume suitable data if necessary"), we choose prime table size (standard for double hashing with 8 keys so that and every probe sequence visits all 11 slots; note that fails on key 7 because enters an odd-index cycle).

Hash functions:

Step-by-Step Insertion Trace:

Final Hash Table ():

Index012345678910
Key———11612132739
Answer:

Assuming prime table size with and (fallback if ), the final hash table is: [—, —, —, 11, 6, 12, 13, 2, 7, 3, 9] (indices 0..10).

All past exam questions for Data Structure and Algorithms