PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q9

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

What is clustering? Explain any three collision resolving scheme with example if applicable. What are the differences between hashing and binary tree search?

Solution

What is Clustering? In open-addressing hash tables, clustering is the tendency of colliding keys to form long contiguous runs of occupied slots (primary clustering in linear probing) or share identical probe chains (secondary clustering in quadratic probing), degrading average lookup time toward .

Three Collision Resolution Schemes (, ):

  1. Separate Chaining: Each bucket HT[i] holds a linked list of colliding keys (e.g., 12, 22 HT[2] -> 12 -> 22).
  2. Linear Probing: Probes sequentially (e.g., 12 at slot 2, 22 at (2+1)=3).
  3. Quadratic Probing: Probes (e.g., 12 at slot 2, 22 at (2+1)=3, 32 at (2+4)=6).

Hashing vs. Binary Search Tree (BST):

AspectHashingBinary Search Tree (BST)
Average Search Time (balanced) / (skewed)
OrderingUnordered; no range queries or sorted traversalSorted order; supports range queries, min/max, in-order
Memory EfficiencyExtra empty table slots needed for low load factorAllocates exact nodes needed
Answer:

Clustering is the growth of contiguous occupied probe runs in open addressing. Three collision resolution schemes are separate chaining, linear probing, and quadratic probing. Hashing gives average lookup without ordering, while BSTs give balanced lookup with sorted traversal and range queries.

All past exam questions for Data Structure and Algorithms