応用情報技術者試験 応用情報技術者試験 平成30年度秋期 午前 問8: 探索表の構成法を例とともに a ～ c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。 a コード順に格納した探索表

問題本文

探索表の構成法を例とともに a ～ c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。 a コード順に格納した探索表 b コードの使用頻度順に格納した探索表 c コードから一意に決まる場所に格納した探索表

選択肢

• ア.a：2 分探索 b：線形探索 c：ハッシュ表探索
• イ.a：2 分探索 b：ハッシュ表探索 c：線形探索
• ウ.a：線形探索 b：2 分探索 c：ハッシュ表探索
• エ.a：線形探索 b：ハッシュ表探索 c：2 分探索

正解

ア. a：2 分探索 b：線形探索 c：ハッシュ表探索

解説

各探索手法は格納のされ方によって得意・不得意が決まる。aはコード順（昇順）に整列済みなので、中央と比較して範囲を半分ずつ絞れる2分探索が最適。bは使用頻度が高いコードを先頭付近に置いているので、先頭から順に調べる線形探索なら高頻度のものを少ない比較回数で見つけられる。cはコードから格納位置を一意に算出して（途中に空きを作って）配置しており、ハッシュ関数で位置を計算して取り出すハッシュ表探索が最適。よって a:2分探索・b:線形探索・c:ハッシュ表探索の組合せであるアが正解。