修了試験 2014-07-27実施分 基本情報技術者試験 問5

解説

正解は2です。 f(x)はpを1増やしてからA[p]にxを書き込み、g()はA[p]を読み出してからpを1減らします。 pは常に最後に書き込んだ位置を指すので、最後に入れたデータが最初に取り出されます。 これは後入れ先出し（LIFO：Last In First Out）の動作です。 【選択肢別解説】 1：× キューは先に入れたデータを先に取り出す先入れ先出し（FIFO）の構造です。 実現には取り出し位置と格納位置の2つのポインタが必要ですが、本問はp1つで同じ端から出し入れしています。 2：○ f(x)がプッシュ（積む操作）、g()がポップ（取り出す操作）に当たります。 同じ位置pで格納と取出しを行うLIFOの構造なので、スタックです。 3：× ハッシュはキーからハッシュ関数で格納位置を計算する方式です。 本問の関数は格納位置をpの増減だけで決めており、キーから位置を計算していません。 4：× ヒープは親の値が子の値以上（または以下）という条件を満たす木構造です。 本問には値の大小比較や要素の入替えがないので、ヒープではありません。 【ポイント】 スタックはLIFO、キューはFIFOです。 「ポインタ1つで同じ端から出し入れ」ならスタックと覚えましょう。