基本情報技術者試験 - 令和6年12月修了 - 問5
十分な大きさの配列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;
}
function f(x) {
p = p+1;
A[p] = x;
return None;
}
function g() {
x=A[p];
p = p-1;
return x;
}
| ア | キュー |
|---|---|
| イ | スタック |
| ウ | ハッシュ |
| エ | ヒープ |
答え ： イ
分野 ： テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › データ構造
解説 ：
擬似的なプログラムコードで示された関数fとgが，どのようなデータ構造を実現しているかを読み解く問題です。
関数f(x)は，まず変数pの値を1増やし，その新しいpの位置の配列Aにxを格納します。つまりデータを追加するたびに，後ろへ後ろへと積み上げていく動きをします。一方，関数g()は，現在のpの位置にある配列Aの値を取り出し，その後でpの値を1減らします。つまり，最後に追加されたデータを最初に取り出す動きになっています。この「最後に入れたものを最初に取り出す」という性質は，「スタック」と呼ばれるデータ構造の特徴（LIFO：Last In First Out）そのものです。従って，正解は「イ」です。
「ア」の「キュー」は，逆に「最初に入れたものを最初に取り出す」（FIFO：First In First Out）性質を持つデータ構造で，このプログラムの動きとは一致しません。「ウ」の「ハッシュ」は，キーと呼ばれる値をもとに計算した位置にデータを格納する仕組みであり，今回のように単純にpを増減させるだけの操作とは異なります。「エ」の「ヒープ」は，木構造を使って親子関係を保ちながらデータを管理する構造で，こちらも単純な配列の末尾への出し入れとは異なる仕組みです。
分野 ： テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › データ構造
解説 ：
擬似的なプログラムコードで示された関数fとgが，どのようなデータ構造を実現しているかを読み解く問題です。
関数f(x)は，まず変数pの値を1増やし，その新しいpの位置の配列Aにxを格納します。つまりデータを追加するたびに，後ろへ後ろへと積み上げていく動きをします。一方，関数g()は，現在のpの位置にある配列Aの値を取り出し，その後でpの値を1減らします。つまり，最後に追加されたデータを最初に取り出す動きになっています。この「最後に入れたものを最初に取り出す」という性質は，「スタック」と呼ばれるデータ構造の特徴（LIFO：Last In First Out）そのものです。従って，正解は「イ」です。
「ア」の「キュー」は，逆に「最初に入れたものを最初に取り出す」（FIFO：First In First Out）性質を持つデータ構造で，このプログラムの動きとは一致しません。「ウ」の「ハッシュ」は，キーと呼ばれる値をもとに計算した位置にデータを格納する仕組みであり，今回のように単純にpを増減させるだけの操作とは異なります。「エ」の「ヒープ」は，木構造を使って親子関係を保ちながらデータを管理する構造で，こちらも単純な配列の末尾への出し入れとは異なる仕組みです。
共有ボタンをタップ