基本情報 平成21年度 秋期 問5：テクノロジ系に関する問題

答えは c「スタック」 です。

関数を呼び出すと、「呼び出し元に戻る住所（戻り番地）」と「今やってる途中のデータ」を一旦どこかに置いておく必要があります。

スタックは「お皿の山」の構造で、一番上に置いて、一番上から取る（後入れ先出し=LIFO）。関数Aが関数Bを呼んで、関数BがCを呼んで…と入れ子で進むとき、戻る順番がちょうど逆順（C→B→A）になるので、スタックが完璧にフィットします。

👉 覚え方：「関数の出入りはスタック」。CPUにも専用のスタックポインタという機械があるくらい標準的な使い方です。

ほかの選択肢：a 2分探索木=データを検索する木構造／b キュー=順番待ちの列（先入れ先出し）／d 双方向連結リスト=両向きにたどれるリスト。

なぜこれが正解か

正解は c。関数呼出しの戻り番地・引数・ローカル変数は「最後に呼ばれたものが最初に戻る」順序で扱う必要があり、これはスタック（LIFO: Last In First Out）の特性そのもの。実際、CPUはスタックポインタ（SP）レジスタで管理されるコールスタックを用い、関数のCALL命令でpush、RET命令でpopして戻り番地を取り出す。

各選択肢の解説

• a 2分探索木：データの検索・整列向けで、呼出し管理には用途不一致。
• b キュー：FIFO（先入れ先出し）。順番待ち（ジョブスケジューリング、印刷キュー）向け。
• d 双方向連結リスト：双方向走査可能なリスト構造。汎用だが呼出し管理用ではない。

覚え方・ひっかけ注意

LIFO=スタック=関数呼出し、Undo、FIFO=キュー=順番待ち、メッセージングの対比は頻出。再帰関数の動作もスタックで理解する（再帰深度=スタック消費）。

理論的背景

コールスタック（Call Stack）はプロセスのメモリ空間内に確保される連続領域で、関数呼出しごとにスタックフレーム（Activation Record）が積まれる。各フレームは (1) 引数、(2) 戻り番地、(3) 前フレームのフレームポインタ、(4) ローカル変数、を含む。x86-64ではRSP（Stack Pointer）とRBP（Base Pointer）で管理し、関数プロローグ/エピローグで標準的に確保・解放する。スタックは高位アドレス→低位アドレスに伸び、ヒープと逆方向に成長する設計が一般的（Linuxユーザ空間）。

実務での使われ方

スタックオーバーフローは無限再帰や巨大ローカル配列で発生し、プロセスが強制終了する。セキュリティ的にはスタックバッファオーバーフロー攻撃の温床で、対策としてStack Canary（戻り番地直前に検査値を置く）、ASLR（Address Space Layout Randomization）、DEP/NX bit（実行禁止ビット）、Shadow Stack（Intel CET）が現代CPUに実装されている。GoやErlangの軽量スレッド（ゴルーチン、プロセス）は可変サイズスタックで省メモリ多重化を実現。

試験での位置づけ

FE科目Aではデータ構造の用途識別、スタックトレース問題が頻出。応用情報・基本情報の午後では再帰関数の呼出し履歴、スタック深度計算、末尾再帰最適化が問われる。情報処理安全確保支援士ではバッファオーバーフロー攻撃と対策（CWE-120/121/122）が必出。

選択肢の発展補足

スタック関連の発展概念：逆ポーランド記法（RPN）評価（電卓、Forth、JVMバイトコード）／継続（Continuation）＝スタック状態をオブジェクト化して保存・復元、Scheme/Rubyで利用／コルーチン＝スタックを切替えて協調的マルチタスク／Async/Await＝コンパイラがスタックを継続オブジェクトに変換（state machine変換）。ヒープとの対比：ヒープは動的確保・解放順任意・断片化リスクあり、スタックは自動管理・LIFO限定・高速。GC（ガベージコレクション）はヒープ管理の話で、世代別GC・トライカラーマーキングは関連深い。