平成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;
}- アキュー
- イスタック
- ウハッシュ
- エヒープ
答えと解説を見る
✓ これが正解イスタック
解説
最後に置いたものを最初に取り出す積み上げ式です。
二つの関数の動きを順に追います。値を入れる側は、位置を示す変数を1増やしてから、その位置に値を書き込みます。値を取り出す側は、いま位置が指しているところから値を読み、そのあと位置を1減らします。つまり書き込みも読み出しも、常に同じ一点、それも直前に置いたばかりのところで起きます。四つ入れてから続けて取り出すと、四番目、三番目、二番目、一番目の順に戻ってきます。この後入れ先出しのふるまいがスタックです。判定の軸は、返ってくる値がいちばん新しいものか、いちばん古いものか、それとも値の大小や鍵によって決まるのかという三点です。
ほかの選択肢はなぜ違うのか
- アキュー：先に入れたものから順に出ていく構造です。入り口と出口を別々に動かす目印が必要ですが、この定義には位置を示す変数が一つしかなく、両端を別々に扱えません。
- ウハッシュ：しまう場所を鍵から計算して決める仕組みです。この定義には鍵に当たる手がかりも、場所を割り出すための計算も現れず、置く位置は呼ばれた回数だけで決まっています。
- エヒープ：値の大小関係を保ちながら木の形に並べる構造です。この定義のどこにも値どうしを比べる処理がなく、並べ替えも起きないので、大小の順序は保たれません。
この問題の用語
- ハッシュハッシュ関数で作られた値そのもの。元に戻せないので、中身を見せずに同じかどうかだけを確かめるのに使えます。
出典：平成24年度 春期 基本情報技術者試験 午前 問6（改変：原典の図表をテキストに書き起こした）
同じ用語が出る問題
- 令和5年度 科目B 問4：ハッシュに関する問題（ハッシュ）
- 平成31年度 春期 午前 問18：理想的なハッシュ法の説明（ハッシュ）
- 平成30年度 春期 午前 問7：表探索におけるハッシュ法の特徴（ハッシュ）
- 平成29年度 春期 午前 問27：ソートマージ結合法に関する記述（ハッシュ）
- 平成27年度 秋期 午前 問26：キー値に関する問題（ハッシュ）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）