IPA FE Subject B sample Question 11
A question IPA Japan published in 基本情報技術者試験 科目B サンプル問題 問11, 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.
When the function binSort is called as binSort(blank), the array of the return value contains no undefined elements, and its values are arranged in ascending order.
Answer group
Explanation
{2, 6, 3, 1, 4, 5} — each value is stored at the index equal to itself, so every index from 1 to n must receive exactly one value.
bins has n elements, all undefined at first, and the loop puts data[i] into bins[data[i]]. A value v therefore lands in slot v. The result has no undefined element only if every slot 1 to n is filled, that is, only if data holds each of the numbers 1 to n once. Then bins is simply {1, 2, …, n}, in ascending order.
All four options have six elements, so n = 6. Option (a) holds 1, 2, 3, 4, 5, 6 once each, and bins becomes {1, 2, 3, 4, 5, 6}.
Answer (a)
Why not others:
- •(b) — 4 appears twice and 6 is missing, so
bins[6]stays undefined: {1, 2, 3, 4, 5, undefined} - •(c) — 2 appears twice and 3 is missing, so
bins[3]stays undefined - •(d) — 3 appears twice and 1 is missing, so
bins[1]stays undefined
Key rule: Bin sort places each value at the slot named by its key; it works without gaps only when the keys are exactly 1 to n with no repeats, and a duplicate key overwrites a slot while another stays empty.
Sorting · AI-written, may contain errors
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.