探索表の構成法を例とともにa〜cに示す。
探索の平均計算量が最も小さい探索手法の組合せはどれか。
ここで、探索表のコードの空欄は表の空きを示す。
a コード順に格納した探索表 | b コードの使用頻度順に格納した探索表 | c コードから一意に決まる場所に格納した探索表 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
a | b | c | |
ア | 2分探索 | 線形探索 | ハッシュ表探索 |
イ | 2分探索 | ハッシュ表探索 | 線形探索 |
ウ | 線形探索 | 2分探索 | ハッシュ表探索 |
エ | 線形探索 | ハッシュ表探索 | 2分探索 |
答え ア
【解説】
a | 探索表のコードは昇順(小さい順)に整列(ソート)されているので、この探索表に対し探索の平均計算量が最も少ないのは2分探索である。 |
b | 探索表のコードのみに注目して並びを見ると、未整列のデータであるので、この探索表に対し探索の平均計算量が最も少ないのは線形探索である。 |
c | この探索表はハッシュ法で格納場所を決めて作成されているので、この探索表に対し探索の平均計算量が最も少ないのはハッシュ表探索である。 |
【キーワード】
・探索