ITPEC FE Morning April 2023 Question 9
A five-digit number a1a2a3a4a5 needs to be stored in an array by means of hashing. When the hash function is mod (a1+a2+a3+a4+a5, 13) and the number is stored in the array element at the position corresponding to the calculated hash value, which of the following is the position where 54321 is stored in the array? Here, the value of mod (x, 13) is the remainder after dividing x by 13.
Explanation
2 — add the five digits, then take the remainder after dividing by 13.
- •Digits of 54321: 5, 4, 3, 2, 1
- •Sum: 5 + 4 + 3 + 2 + 1 = 15
- •Hash: mod(15, 13) = 2, because 15 = 13 × 1 + 2
So 54321 is stored in array element 2.
Answer (b)
Why not others:
- •(a) 1 — mod(14, 13): the sum of only four digits, 5 + 4 + 3 + 2 = 14, leaving out a5
- •(c) 7 — mod(54321, 13): applies the mod to the number itself instead of its digit sum, since 54321 = 13 × 4178 + 7
- •(d) 11 — would need a digit sum of 11 or 24, but the digits of 54321 add up to 15
Key rule: Apply a hash function exactly as defined: compute its argument first (here the digit sum), then reduce it modulo the table size.
Algorithm and Programming · AI-written, may contain errors
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.