IPA FE Subject B 2023 Question 4

Topic: Array Manipulation

A question IPA Japan published in 令和５年度 基本情報技術者試験 科目B 公開問題 問4, translated into English. ITPEC is based on the same exams.

From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array index starts at 1.

The function add stores the positive integer value specified by the argument in the global integer-type array hashArray. It returns true if the value has been stored, and returns false if the value could not be stored. Here, which element of hashArray the integer value should be stored in is determined by using the functions calcHash1 and calcHash2.
The procedure test calls the function add to store positive integers in hashArray. The content of hashArray immediately after the processing of the procedure test has finished is blank.

[Program]
global: integer []: hashArray
○ boolean: add(integer: value)
integer: i ← calcHash1(value)
if (hashArray[i] = -1)
hashArray[i] ← value
return true
else
i ← calcHash2(value)
if (hashArray[i] = -1)
hashArray[i] ← value
return true
endif
endif
return false
○ integer: calcHash1(integer: value)
return (value mod the number of elements in hashArray) + 1
○ integer: calcHash2(integer: value)
return ((value + 3) mod the number of elements in hashArray) + 1
○ test()
hashArray ← {5 elements of -1}
add(3)
add(18)
add(11)

Answer group

Explanation

{−1, 18, −1, 3, 11} — each value goes to the element calcHash1 gives, and only if that one is taken to the element calcHash2 gives.

hashArray has 5 elements, so calcHash1 returns (value mod 5) + 1 and calcHash2 returns ((value + 3) mod 5) + 1. The three calls, in order:

CallcalcHash1calcHash2Stored in
add(3)4, freenot calledelement 4
add(18)4, taken by 321 mod 5 + 1 = 2, freeelement 2
add(11)2, taken by 1814 mod 5 + 1 = 5, freeelement 5

All three calls return true. Elements 1 and 3 keep −1, so hashArray is {−1, 18, −1, 3, 11}.

Answer (d)

Why not others:

  • •(a) — the result if 18 were added before 3: 18 would take element 4 and 3 would go to element 2 by calcHash2
  • •(b) — skips calcHash2: 18 is then refused, and 11 takes the still-free element 2
  • •(c) — overwrites on a collision: 18 replaces 3 in element 4, and 11 lands in element 2 by calcHash1
  • •(e) — puts 11 in the element after its taken one, as linear probing would, instead of element 5 from calcHash2

Key rule: In double hashing the second hash is computed from the value itself, only when the first position is taken, so trace the insertions in call order: earlier values decide which positions later ones find taken.

Array Manipulation · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.