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