データ構造 (全53問中27問目)
No.27
十分な大きさの配列Aと初期値が0の変数pに対して，関数ƒ(x)とg()が次のとおり定義されている。配列Aと変数pは，関数ƒ(x)とg()だけでアクセス可能である。これらの関数が操作するデータ構造はどれか。
function ƒ(x) {
p＝p＋1;
A[p]＝x;
return None;
}
function g() {
x＝A[p];
p＝p－1;
return x;
}
p＝p＋1;
A[p]＝x;
return None;
}
function g() {
x＝A[p];
p＝p－1;
return x;
}
出典：平成24年春期 問6
- キュー
- スタック
- ハッシュ
- ヒープ
- [出題歴]
- 基本情報技術者 H19秋期 問13
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
イ
解説
4つの選択肢の用語の意味を簡単に確認しておきます。
ƒ(x)を実行したときには配列の末尾に要素が追加され、g()を実行したときには配列の末尾の要素が返されます。「配列の最後にデータを追加する」および「最後に追加されたデータを取り出す」という2つの操作を合わせると、後入れ先出しのデータ構造を実現することができます。
したがって、後入れ先出し(LIFO)のデータ構造である「スタック」が正解です。
- キュー
- 先入れ先出し(FIFO)のデータ構造
- スタック
- 後入れ先出し(LIFO)のデータ構造
- ハッシュ
- 任意のデータから一意に求めた固定長のデータ
- ヒープ
- 親の値は子の値以上という制約で構成された木構造
ƒ(x)を実行したときには配列の末尾に要素が追加され、g()を実行したときには配列の末尾の要素が返されます。「配列の最後にデータを追加する」および「最後に追加されたデータを取り出す」という2つの操作を合わせると、後入れ先出しのデータ構造を実現することができます。
したがって、後入れ先出し(LIFO)のデータ構造である「スタック」が正解です。