Searching & Hashing

Phase 2 Checkpoint: 15 questions on searching and hashing.

⏱️

15 questions · 23 marks · 40 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.

Q1NAT1 markProbes

B = [3, 8, 15, 21, 27, 34, 40, 46, 52, 60, 71]. Probes to find 60?

Numerical answer: ________

Q2NAT1 markMax probes

Maximum probes of binary search on 2,000 sorted elements?

Numerical answer: ________

Q3MCQ1 markInvariant

The loop invariant of binary search is:

• (A) A[mid] = x
• (B) lo < hi
• (C) hi − lo is even
• (D) if x is in A, it lies in A[lo..hi]

Q4NAT2 marksFirst occurrence

A = [5, 5, 5, 6, 6, 9, 9, 9, 9, 11]. Using first and last occurrence searches, how many times does 9 occur?

Numerical answer: ________

Q5MCQ1 markLower bound

Searching a sorted array with comparisons needs Ω(log n) because:

• (A) the array may contain duplicates
• (B) memory access is slow
• (C) hashing is faster
• (D) a binary decision tree with n leaves has height at least log n

Q6NAT1 markDivision hash

h(k) = k mod 17. Slot of 200?

Numerical answer: ________

Q7NAT2 marksChaining

m = 7, h(k) = k mod 7, chaining. Keys 15, 11, 27, 8, 12, 19, 23, 40. Length of the longest chain?

Numerical answer: ________

Q8NAT1 markLoad factor

A chained table has 128 slots and 32 keys. α = ?

Numerical answer: ________

Q9NAT2 marksLinear probing

m = 10, h(k) = k mod 10, linear probing. Insert 22, 32, 42, 9, 19, 29. Slot of 29?

Numerical answer: ________

Q10NAT2 marksQuadratic probing

m = 11, h(k) = k mod 11, quadratic probing h + i². Insert 3, 14, 25. Slot of 25?

Numerical answer: ________

Q11NAT2 marksDouble hashing

m = 11, h₁(k) = k mod 11, h₂(k) = 1 + (k mod 10). Keys 10, 22, 31, 4, 15, 28, 17, 88, 59. Slot of 59?

Numerical answer: ________

Q12MCQ1 markClustering

Which method suffers from secondary clustering?

• (A) Linear probing
• (B) Quadratic probing
• (C) Chaining
• (D) Double hashing

Q13NAT2 marksExpected probes

Open addressing, uniform hashing, 75 keys in 100 slots. Expected probes for an unsuccessful search?

Numerical answer: ________

Q14NAT2 marksProbability

Simple uniform hashing into 50 slots, 2 keys. Probability they collide?

Numerical answer: ________

Q15MSQ2 marksHashing facts

Which are true?

• (A) Chaining's expected search cost is Θ(1 + α).
• (B) Linear probing performs worse than uniform hashing predicts.
• (C) Open-addressing unsuccessful search costs grow as 1/(1 − α).
• (D) A good hash function makes the worst case O(1).