基本情報技術者試験「キューの応用」の問題
先入れ先出し(FIFO)のデータ構造を用いるのが最も適切な処理はどれか。
ア直前に行った操作を取り消すため、最後に実行した操作から順に元に戻していく処理
イ数式中の開き括弧を一時保持し、閉じ括弧が来たら直近の開き括弧と対応づける処理
ウ深さ優先で経路を探索し、行き止まりで最後に分岐した地点まで戻ってやり直す処理
エ複数の利用者から届いた印刷要求を受付順に保持し、先に届いた要求から順に出力する処理
正解
エ．複数の利用者から届いた印刷要求を受付順に保持し、先に届いた要求から順に出力する処理
プリントスプールは複数の印刷要求を受け付けた順に待たせ、先に届いたものから順に出力する。これは先入れ先出しそのものでありキューが適するため正しい。
?選択肢ごとの解説
ア ×最後の操作から順に元に戻すアンドゥは後入れ先出し(LIFO)であり、キューではなくスタックが適する場面である。
イ ×直近の開き括弧と対応づける括弧の整合判定はLIFOであり、スタックを用いる処理でFIFOには当てはまらない。
ウ ×行き止まりで最後の分岐へ戻る深さ優先探索のバックトラックはLIFOの挙動であり、スタックが対応しキューではない。
エ ○プリントスプールは複数の印刷要求を受け付けた順に待たせ、先に届いたものから順に出力する。これは先入れ先出しそのものでありキューが適するため正しい。
✎くわしく
キューは最初に入れた要素を最初に取り出すFIFO構造で、到着順の公平な処理に向く。印刷スプール、タスク待ち行列、幅優先探索などが典型例である。逆順・入れ子のスタック用途と取り違えないことが核心である。
✓本番での押さえどころ
試験のコツ
『受付順・到着順に処理』ならキュー(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-a3-0124