アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20130127 実施分 問6
表探索におけるハッシュ法の特徴はどれか。
- ア 2 分木を用いる方法の一種である。
- イ 格納場所の衝突が発生しない方法である。
- ウ キーの関数値によって格納場所を決める。
- エ 探索に要する時間は表全体の大きさにほぼ比例する。
出典：基本情報技術者試験 科目A免除 修了試験 20130127 実施分 問6
答えと解説を見る
正解：ウ
覚える知識
ハッシュ法の特徴(キーの関数値で格納位置決定)
ハッシュ法は、キーの関数値を格納場所(アドレス)として直接求める探索方法である。
この問題で必要なこと
ハッシュ法はキーにハッシュ関数を適用した値で格納位置を決める探索法で、探索時間は表の大きさにほぼ依存しない。衝突は起こりうる。
ひっかけ
「衝突が発生しない」は誤り。「表の大きさに比例」は線形探索の特徴。「2分木」は2分探索木の特徴。
この知識の出題：本試験系 1 回・免除試験 9 回（公開問題での観測値）