平成25年度 春期
応用情報技術者試験問題と解答
問5
探索表の構成法を例とともに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である。

EXCEL VBAのご相談なら ファーストマクロ 



問4 目次 問6
ファーストマクロ TOPページ