探索表と探索手法
出典: 平成30年度 秋期 応用情報技術者試験 午前 問8 (IPA)
探索表の構成法を例とともに a～c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
- a コード順に格納した探索表
- b コードの使用頻度順に格納した探索表
- c コードから一意に決まる場所に格納した探索表
図は左から a，b，c の探索表です。
- ア a: 2 分探索，b: 線形探索，c: ハッシュ表探索
- イ a: 2 分探索，b: ハッシュ表探索，c: 線形探索
- ウ a: 線形探索，b: 2 分探索，c: ハッシュ表探索
- エ a: 線形探索，b: ハッシュ表探索，c: 2 分探索
正解と解説を見る
正解: ア
- ア: a は 2 分探索、b は線形探索、c はハッシュ表探索が最も適しているので正しい組合せです。
- イ: b は使用頻度順でコードの順に並んでいないのでハッシュ表探索は使えず、c は空きがあるので線形探索では効率が悪いです。
- ウ: a はコード順に並んでいるので 2 分探索が適しています。b は並びがコード順でないので 2 分探索は使えません。
- エ: c は整列されていないので 2 分探索は使えません。コードから場所を計算するハッシュ表探索が適しています。
ポイント
- a (コード順に並んだ表): 整列されているので、真ん中と比べて範囲を半分にしていく 2 分探索 が使えます。
- b (使用頻度順に並んだ表): よく使うものが先頭にあるので、先頭から順に調べる 線形探索 が速く見つかります。
- c (コードから決まる場所に格納した表): コードから格納場所を計算する ハッシュ表探索 を使います。