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

探索表の構成法を例とともにa〜cに示す。
探索の平均計算量が最も小さい探索手法の組合せはどれか。
ここで、探索表のコードの空欄は表の空きを示す。

a コード順に格納した探索表 b コードの使用頻度順に格納した探索表 c コードから一意に決まる場所に格納した探索表
コード データ
120380
120381
120520
140140








コード データ
120381
140140
120520
120380








コード データ


120381


120520
140140


120380



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


答え ア


解説

a  探索表のコードは昇順(小さい順)に整列(ソート)されているので、この探索表に対し探索の平均計算量が最も少ないのは2分探索である。
b  探索表のコードのみに注目して並びを見ると、未整列のデータであるので、この探索表に対し探索の平均計算量が最も少ないのは線形探索である。
c  この探索表はハッシュ法で格納場所を決めて作成されているので、この探索表に対し探索の平均計算量が最も少ないのはハッシュ表探索である。


キーワード
・探索

キーワードの解説
  • 探索
    この問題での『探索』はデータの中から、目的のデータを探し出す方法である。
    探索方法(アルゴリズム)には、問題の2分探索線形探索ハッシュ探索以外にもあるが、この3つのアルゴリズムを把握しておけば十分である。
    どの探索方法を使うかはデータが整列されているか、整列されている場合はどういった整列方法を行ったかで変わってくる。

もっと、「探索」について調べてみよう。

戻る 一覧へ 次へ