基本情報技術者 2009年 春期 午前（科目A） 問05

関数呼び出しのためのスタック【午前解説】

正解の理由

解法ステップ

1. 問題の要件を抽出：戻り番地や処理途中データの「一時保存」および復帰の順序が重要か確認する。
2. 操作特性を照合：復帰は「最後に呼んだものから戻る」→ LIFO が必要。
3. 選択肢の特性を見る：スタック＝LIFO、キュー＝FIFO、2分探索木＝順序探索向け、双方向連結リスト＝汎用的だがそのままではLIFOを保証しない。
4. 最適解を選択：LIFO を満たすスタックを選ぶ。

選択肢別の誤答解説

• ア: 2分探索木
  • 説明：要素の高速検索や順序付き処理に適するが、復帰順序（LIFO）を自然に表現できないため不適切です。
• イ: キュー
  • 説明：FIFO（First In First Out）であり、最初に入れたものから取り出されるため関数の戻り順序に合いません。
• ウ: スタック
  • 説明：正解。LIFO の性質が戻り番地や活性化レコードの管理に一致し、push/pop により正しく復帰できるため適切です。
• エ: 双方向連結リスト
  • 説明：任意位置の挿入・削除が可能で実装の基礎になりますが、単体で「呼び出しの逆順で取り出す」性質を保証するわけではありません。スタックの実装に使うことはできますが、回答としては「スタック」が正しい選択です。

よくある誤解

• キュー（FIFO）でよいと考える誤解：呼び出しは「最後に呼んだものから戻る」ため FIFO のキューでは順序が逆転してしまいます。
• 双方向連結リストなら問題ないと思う誤解：連結リスト自体は任意の順序の挿入・削除が可能ですが、問題はLIFOの性質であり、連結リストを使うならスタックとして使う設計（push/pop）にする必要があります。
• 2分探索木を使えば高速に探索できるから適切だと考える誤解：探索用途には向きますが、呼び出し戻り処理の順序管理という要求には不適切です。

補足コラム

• コールスタックと活性化レコード：関数ごとに活性化レコード（戻り番地、局所変数、引数、保存レジスタなど）をスタック上に積み、関数終了時にそのレコードを取り出して復帰します。
• 実装上の注意：スタックは配列（固定容量）や連結リスト（動的容量）で実装可能。配列実装は高速だが容量制限があり、連結リストはメモリ確保が必要でオーバーヘッドがあります。
• スタックオーバーフロー：再帰深度が大きすぎるとスタック領域を使い果たし例外（スタックオーバーフロー）が発生します。テストや設計時に再帰深度を考慮してください。
• CPUとハードウェア：多くのCPU はハードウェア的にスタックポインタ命令を持ち、関数呼び出し命令（CALL/RET 等）でスタックを利用します。

FAQ