基本情報技術者試験「キュー」の問題
整数を格納したキュー（先頭から取り出す FIFO）がある。次の手続は、キューの要素が1個になるまで「先頭の2つを取り出し、その和を末尾に追加する」ことを繰り返し、最後に残った値を返す。初期状態でキューに先頭から順に 40, 70, 20, 90 が入っているとき、手続 fold() の戻り値はどれか。
○整数型: fold()
整数型: a, b
while (キューの要素数 > 1)
a ← dequeue()
b ← dequeue()
enqueue(a + b)
endwhile
return dequeue()ア220
イ110
ウ90
エ330
正解
ア．220
FIFOで先頭2要素 a,b を取り出し a+b を末尾に追加する操作は、キュー内の総和を変えずに要素数を1ずつ減らす。要素が1個になるまで繰り返すと、最後に残る値は初期要素の総和 40+70+20+90=220 となる。
?選択肢ごとの解説
ア ○FIFOで先頭2要素 a,b を取り出し a+b を末尾に追加する操作は、キュー内の総和を変えずに要素数を1ずつ減らす。要素が1個になるまで繰り返すと、最後に残る値は初期要素の総和 40+70+20+90=220 となる。
イ ×110 は最初の1回で計算した和（40+70）にすぎず、処理を途中で止めた誤り。残りの要素を畳み込んでいない。
ウ ×90 は初期キューの末尾要素をそのまま答えたもので、手続を実行していない。
エ ×330 は和の計算過程で要素を重複して加算するなど、取り出し順を取り違えた誤り。総和は220を超えない。
✎くわしく
本手続は二項演算（加算）でキューを左から畳み込む reduce の典型例である。加算は結合的なので、ペアにする順序が変わっても最終結果は総和で一定になる点が本質である。
✓本番での押さえどころ
試験のコツ
「2つ取り出して和を戻す」を見たら、まず不変条件『総和は保存される』に気づくと、逐次トレースせずに総和=220と即答できる。
覚え方
要素数が毎回1ずつ減り、加算で畳まれる→最後の1個は全部の合計、と覚える。
よくある誤り
FIFOではなくLIFO（スタック)的に末尾から取り出すと勘違いする、または最初の和だけで答えを確定してしまうミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0030