ITPEC FE Morning April 2018 Question 17

Topic: Algorithm and Programming

In a direct organization file that has a range of storage addresses one (1) through six (6), the data is stored under the conditions below. Which of the following is the key value of the data that is stored in address one (1)?

[Conditions](1)Data is stored in the order of key values three (3), four (4), eight (8), 13, 14, and 18.(2)The storage address is the value that is the remainder obtained by dividing the key value of data by five (5) and then adding one (1) to it.(3)If the storage address is already occupied, the data is stored in the next address. This process is repeated until the data is stored. The next address of the last address is the first address.(4)In the initial status, nothing is stored in the file.

Explanation

13 — it hashes to address 4 and, with 4, 5 and 6 already taken, wraps round to address 1.

Address = (key mod 5) + 1, and a collision moves to the next address, from 6 back to 1:

KeyHome addressProbedStored at
3444
4555
844, 5, 66
1344, 5, 6, 11
1455, 6, 1, 22
1844, 5, 6, 1, 2, 33

Answer (b)

Why not others:

  • •(a) 8 — collides at 4 and 5 but finds address 6 free, so it never wraps round
  • •(c) 14 — reaches address 1 after 13 has taken it and moves on to 2; it would land at 1 only if the + 1 were dropped from the formula, which shifts every home address down by one
  • •(d) 18 — the last key in, it ends at 3; dividing by the table size 6 instead of 5 would put it at 1

Key rule: With open addressing, insert keys strictly in the given order and keep probing, wrapping from the last address to the first, so earlier keys decide where later ones end up.

Algorithm and Programming · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.