ITPEC FE Subject B October 2024 Question 13

Topic: Array Manipulation

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array indexes start at 1.

Hashing in data structures is a fundamental concept used for efficient data retrieval and storage mechanisms. A program storing a key-data pairs in an array by transforming keys into array indexes using a hash function exists. A collision occurs when two keys hash to the same index in the array representing the hash table. A common method handling collisions, the probing mechanism (checking for an available element), is used in the function. The procedure insertData inserts a pair of key and data, if the element in the array is {undefined}. Assumptions are made that no data with the same key is stored, and that at least one element in the array hashTable is {undefined} when the procedure insertData is called. The function hashFunction takes a key as input and returns a hash value.

[Program]
global: integer [][]: hashTable ← {Elements comprising 1000 {undefined}}
global: integer: size ← 1000
○ integer: hashFunction(integer: key)
return (key mod size) + 1
○ insertData(integer: key, integer: data)
integer: index
index ← hashFunction(key)
while (A)
if (index = size)
B
else
index ← index + 1
endif
endwhile
hashTable[index] ← {key, data}

Answer group

OptionAB

Explanation

A: hashTable[index][1] ≠ undefined, B: index ← 1 — linear probing: keep moving while the slot is taken, and wrap from the last slot to the first.

hashFunction gives a home slot from 1 to 1000. If that slot already holds a pair, there is a collision and the next slot is tried. So the while loop must repeat as long as the current slot is occupied, that is, its key field is not undefined, and stop at the first empty slot, where the pair is written.

Inside the loop, index + 1 steps forward, but at index = size (1000) there is no next element, so probing continues from the start of the array: index ← 1. Because at least one slot is guaranteed to be empty, the loop always ends.

Example: keys 5 and 1005 both hash to slot 6. Key 5 is stored in slot 6; for key 1005 slot 6 is occupied, so it goes on to slot 7.

Answer (e)

Why not others:

  • •(a) and (b) — ≠ key: no slot ever holds this key (duplicates are ruled out), so the test is always true and the loop never stops, not even on an empty slot
  • •(c) and (d) — = key is never true, so the loop never runs and the pair is written at the home slot, overwriting the stored pair on a collision
  • •(g) and (h) — = undefined is backwards: the loop leaves an empty slot and stops on an occupied one, overwriting stored data
  • •(f) — the loop test is right, but index ← index - 1 at slot 1000 goes back to 999, and the next step returns to 1000; slots 1 to 998 are never reached, so the loop can run forever (the same B is wrong in (b), (d) and (h))

Key rule: Open addressing probes while the slot is occupied and treats the table as circular, wrapping from the last index to the first.

Array Manipulation · 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.