本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成22年度 秋期 応用情報技術者試験問題と解説

問6

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

a コード順に格納し b コードの使用頻度 c コードから一意に
  た探索表       順に格納した探索表  決まる場所に格納
                        した探索表
 コード  データ    コード  データ    コード  データ
┌───┬────┐ ┌───┬────┐ ┌───┬────┐
│120380│ …… │ │120381│ …… │ │   │    │
├───┼────┤ ├───┼────┤ ├───┼────┤
│120381│ …… │ │140140│ …… │ │120381│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│120520│ …… │ │120520│ …… │ │   │    │
├───┼────┤ ├───┼────┤ ├───┼────┤
│140140│ …… │ │120380│ …… │ │120520│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│   │    │ │   │    │ │140140│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│   │    │ │   │    │ │   │    │
├───┼────┤ ├───┼────┤ ├───┼────┤
│   │    │ │   │    │ │120380│ …… │
├───┼────┤ ├───┼────┤ ├───┼────┤
│   │    │ │   │    │ │   │    │
└───┴────┘ └───┴────┘ └───┴────┘

   ┌────┬───────┬───────┐
   │ a  │   b   │   c   │
 ┌─┼────┼───────┼───────┤
 │ア│2分探索│線形探索   │ハッシュ表探索│
 ├─┼────┼───────┼───────┤
 │イ│2分探索│ハッシュ表探索│線形探索   │
 ├─┼────┼───────┼───────┤
 │ウ│線形探索│2分探索   │ハッシュ表探索│
 ├─┼────┼───────┼───────┤
 │エ│線形探索│ハッシュ表探索│2分探索   │
 └─┴────┴───────┴───────┘


正解


解説

2分探索はキーにあたるコードが昇順に並んでいる場合に有効であり、その平均計算量はlog2Nである。
また、2分探索はキーが昇順に並んでいないと検索できないため、bやcの表には不向きである。

b表はコードが昇順に並んでいないため、線形探索が適しており、その平均計算量は (N+1)/2 である。

c表は空きがあるため、ハッシュ法によりキーから格納アドレスを求めるハッシュ表探索が有効である。計算の結果アドレスが重複する場合があるが、原則的に計算量は1である。

問5 目次 問7