平成24年度 春期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム十分な大きさの配列 A と初期値が0の変数 p に対して，関数 f(x) と g() が次のとおり定義されている。配列 A と変数 p は，関数 f(x) と g() だけでアクセス可能である。これらの関数が操作するデータ構造はどれか。 function f(x) { p = p + 1; A[p] = x; return None; } function g() { x = A[p]; p = p - 1; return x; }
出典：平成24年度 春期 基本情報技術者試験 午前 問6
- アキュー
- イスタック
- ウハッシュ
- エヒープ
正解：イ
解説
f(x) は変数 p をインクリメントしてから配列 A の位置 p に値 x を格納する処理，g() は配列 A の位置 p から値を取り出してから p をデクリメントする処理です。p は最後に格納した位置（先頭）を指すポインタとして働き，直近に f で入れた値を g が取り出す，後入れ先出し（LIFO）の構造になっています。これはスタックの push（f）と pop（g）そのものです。
選択肢ごとの解説
- ア誤り。キューは先入れ先出し（FIFO）ですが，この関数は直近に入れた値から取り出す後入れ先出しの動作をしています。
- イ正しい。f は p を進めてから値を格納する push，g は値を取り出してから p を戻す pop の動作であり，後入れ先出しのスタックです。
- ウ誤り。ハッシュはキー計算によって格納位置を決める構造ですが，ここでは単に p を増減しているだけでキー計算はありません。
- エ誤り。ヒープは親子関係を保った木構造で最大値・最小値を効率よく取り出す構造ですが，この関数にはそのような順序関係の維持がありません。