探索表の構成法を例とともにａ〜ｃに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。
ａ コード順に格納し ｂ コードの使用頻度 ｃ コードから一意に
た探索表 順に格納した探索表 決まる場所に格納し
た探索表
コード データ コード データ コード データ
┌───┬────┐ ┌───┬────┐ ┌───┬────┐
│120380│ …… │ │120381│ …… │ │ │ │
├───┼────┤ ├───┼────┤ ├───┼────┤
│120381│ …… │ │140140│ …… │ │120381│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│120520│ …… │ │120520│ …… │ │ │ │
├───┼────┤ ├───┼────┤ ├───┼────┤
│140140│ …… │ │120380│ …… │ │120520│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│ │ │ │ │ │ │140140│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│ │ │ │ │ │ │ │ │
├───┼────┤ ├───┼────┤ ├───┼────┤
│ │ │ │ │ │ │120380│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│ │ │ │ │ │ │ │ │
└───┴────┘ └───┴────┘ └───┴────┘
┌────┬───────┬───────┐
│ ａ │ ｂ │ ｃ │
┌─┼────┼───────┼───────┤
│ア│２分探索│線形探索 │ハッシュ表探索│
├─┼────┼───────┼───────┤
│イ│２分探索│ハッシュ表探索│線形探索 │
├─┼────┼───────┼───────┤
│ウ│線形探索│２分探索 │ハッシュ表探索│
├─┼────┼───────┼───────┤
│エ│線形探索│ハッシュ表探索│２分探索 │
└─┴────┴───────┴───────┘
ア
2分探索はキーにあたるコードが昇順に並んでいる場合に有効であり、その平均計算量はlog2Ｎである。
また、2分探索はキーが昇順に並んでいないと検索できないため、ｂやｃの表には不向きである。
ｂ表はコードが昇順に並んでいないため、線形探索が適しており、その平均計算量は (Ｎ＋1)／2 である。
ｃ表は空きがあるため、ハッシュ法によりキーから格納アドレスを求めるハッシュ表探索が
有効である。計算の結果アドレスが重複する場合があるが、原則的に計算量は1である。
| 問２ | 目次 | 問４ |