基本情報技術者試験のサンプル問題（科目B）を解いてみよう。
今回のテーマは、「ビンソート（バケットソート）のアルゴリズム」である。
正解：ア
本問は、ビンソート（binSort）/（バケットソート）を使った整列処理の理解を問う問題である。
ビンソート（バケットソート） の処理概要
このプログラムは、配列 bins を使って、値 n を bins[n] に格納することで整列を行う。
つまり、値がそのままインデックスになるという特徴がある。
- 重複があると、同じインデックスに上書きされてしまう
- 未定義の値が残る可能性がある
- 値の重複がない場合、昇順に整列された配列が得られる
各選択肢をトレースしよう
ア {2, 6, 3, 1, 4, 5}
| 値 | bins[値] に代入 | bins の状態 |
|---|---|---|
| 2 | bins[2] = 2 | { , 2, , , , } |
| 6 | bins[6] = 6 | { , 2, , , , 6} |
| 3 | bins[3] = 3 | { , 2, 3, , , 6} |
| 1 | bins[1] = 1 | {1, 2, 3, , , 6} |
| 4 | bins[4] = 4 | {1, 2, 3, 4, , 6} |
| 5 | bins[5] = 5 | {1, 2, 3, 4, 5, 6} ✅ |
➡️ 重複なし・未定義なし → 正しく昇順に整列される
イ {3, 1, 4, 4, 5, 2}
| 値 | bins[値] に代入 | bins の状態 |
|---|---|---|
| 3 | bins[3] = 3 | { , , 3, , , } |
| 1 | bins[1] = 1 | {1, , 3, , , } |
| 4 | bins[4] = 4 | {1, , 3, 4, , } |
| 4 | bins[4] = 4 | 上書き（変化なし） |
| 5 | bins[5] = 5 | {1, , 3, 4, 5, } |
| 2 | bins[2] = 2 | {1, 2, 3, 4, 5, } ❌ |
➡️ 「4」が重複 → bins[6] が未定義 → 不完全な整列
ウ {4, 2, 1, 5, 6, 2}
| 値 | bins[値] に代入 | |
|---|---|---|
| 4 | bins[4] = 4 | |
| 2 | bins[2] = 2 | |
| 1 | bins[1] = 1 | |
| 5 | bins[5] = 5 | |
| 6 | bins[6] = 6 | |
| 2 | bins[2] = 2 | 上書き ❌ |
➡️ 「2」が重複 → bins[3] が未定義 → 不完全な整列
エ {5, 3, 4, 3, 2, 6}
| 値 | bins[値] に代入 | |
|---|---|---|
| 5 | bins[5] = 5 | |
| 3 | bins[3] = 3 | |
| 4 | bins[4] = 4 | |
| 3 | bins[3] = 3 | 上書き ❌ |
| 2 | bins[2] = 2 | |
| 6 | bins[6] = 6 |
➡️ 「3」が重複 → bins[1] が未定義 → 不完全な整列
まとめ
- 正しく整列されるのは「ア」である。
- 他の選択肢は重複によって未定義の要素が残るため不正解となる。
コメント