The GATE Grind

GATE 2014 CS (CS1) – Question 50

Programming and Data Structures · Hashing · 2 marks · Multiple choice

A 9-slot hash table uses h(k) = k mod 9 and chaining. Keys 5,28,19,15,20,33,12,17,10 are inserted in that order. Find maximum, minimum and average chain lengths respectively.

  1. 3, 0, 1
  2. 3, 3, 3
  3. 4, 0, 1
  4. 3, 0, 2

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 3, 0, 1

Explanation

Remainders modulo9 are5,1,1,6,2,6,3,8,1. Bucket1 has three keys, the largest chain; buckets0,4,7 are empty. Nine total keys across nine buckets give mean1. Thus **3,0,1,A**.