A hash table of length 10 uses open addressing with hash function h(k)=k mod…

2026

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

  1. A.

    46, 42, 34, 52, 23, 33

  2. B.

    34, 42, 23, 52, 33, 46

  3. C.

    46, 34, 42, 23, 52, 33

  4. D.

    42, 46, 33, 23, 34, 52

Attempted by 4 students.

Show answer & explanation

Correct answer: C

Concept: In open addressing with linear probing, inserting a key k into a table of size m using hash function h(k) works as follows — compute the home slot h(k); if that slot is already occupied, check the next slots in cyclic order, h(k)+1, h(k)+2, … (each taken mod m), until the first empty slot is found, and place the key there. Because each insertion must skip past whatever earlier insertions have already filled, the same set of keys can settle into different final slots depending on the order in which they are inserted.

Application: apply h(k) = k mod 10 to the insertion order 46, 34, 42, 23, 52, 33:

  1. Insert 46: h(46) = 6. Index 6 is empty, so 46 is placed at index 6.

  2. Insert 34: h(34) = 4. Index 4 is empty, so 34 is placed at index 4.

  3. Insert 42: h(42) = 2. Index 2 is empty, so 42 is placed at index 2.

  4. Insert 23: h(23) = 3. Index 3 is empty, so 23 is placed at index 3.

  5. Insert 52: h(52) = 2. Index 2 is occupied by 42; probing index 3 (occupied by 23) and index 4 (occupied by 34), index 5 is empty, so 52 is placed at index 5.

  6. Insert 33: h(33) = 3. Index 3 is occupied by 23; probing index 4 (occupied by 34), index 5 (occupied by 52), and index 6 (occupied by 46), index 7 is empty, so 33 is placed at index 7.

This reproduces the given table exactly: index 2 holds 42, index 3 holds 23, index 4 holds 34, index 5 holds 52, index 6 holds 46, and index 7 holds 33.

Cross-check: swapping just the relative order of two keys already breaks the match. Inserting 52 before 23 (keeping the rest of the order the same) sends 52 to index 3, probing past only the key at index 2, and pushes 23 on to index 5 — the reverse of the given table. Likewise, inserting 33 before 46 forces 33 into index 6 and pushes 46 to index 7, again the reverse of the table shown. Among the given choices, only the order 46, 34, 42, 23, 52, 33 reproduces every slot of the table.

Explore the full course: Coding For Placement