平成30年 秋期 応用情報技術者 午前 問8
探索表の構成法を例とともに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つのアルゴリズムを把握しておけば十分である。
どの探索方法を使うかはデータが整列されているか、整列されている場合はどういった整列方法を行ったかで変わってくる。
もっと、「探索」について調べてみよう。
戻る
一覧へ
次へ