平成22年度 秋期 応用情報技術者試験 午前 問6

• a: コード順に格納した探索表
  コードが昇順に整列しているので，2分探索が使えます（平均計算量 O(log n)）。

• b: コードの使用頻度順に格納した探索表
  コード順には並んでいないので2分探索は使えません。使用頻度の高いものが先頭にあるので，先頭から順に調べる線形探索が有効です。

• c: コードから一意に決まる場所に格納した探索表
  コードから計算（ハッシュ関数）で格納位置を求める方式なので，ハッシュ表探索です（平均計算量 O(1)）。

• ア: a 2分探索，b 線形探索，c ハッシュ表探索
  正しい。上記の組合せと一致します。

• イ: a 2分探索，b ハッシュ表探索，c 線形探索
  誤り。b は格納位置がコードから決まらないのでハッシュ表探索はできず，c に線形探索を使うのは非効率です。

• ウ: a 線形探索，b 2分探索，c ハッシュ表探索
  誤り。b はコード順に整列していないので2分探索は使えません。また a は2分探索の方が効率的です。

• エ: a 線形探索，b ハッシュ表探索，c 2分探索
  誤り。b にハッシュ表探索，c に2分探索は使えません。

答え

ア: a 2分探索，b 線形探索，c ハッシュ表探索