IPA過去問ドリル

平成22年度 秋期 応用情報技術者試験 午前 問6

テクノロジ／アルゴリズム

探索表の構成法を例とともにa～cに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。 a　コード順に格納した探索表（例：120380，120381，120520，140140の順に格納） b　コードの使用頻度順に格納した探索表（例：120381，140140，120520，120380の順に格納） c　コードから一意に決まる場所に格納した探索表（例：120381，120520，140140，120380がそれぞれ一意に決まる位置に格納され，空きがある） （注：本サイトでは原問題の表を文字表記に変換しています）

出典：平成22年度 秋期 応用情報技術者試験 午前 問6

正解：ア

解説

aのコード順に格納した探索表は2分探索に適し，bの使用頻度順に格納した探索表は先頭から順に探すことで頻出データほど早く見つかる線形探索に適します。cのコードから一意に決まる場所に格納した探索表は，コードから直接格納位置を計算するハッシュ表探索に適しており，この組合せが最も平均計算量が小さくなります。

選択肢ごとの解説

  • ア正しい。a（コード順）は2分探索，b（使用頻度順）は線形探索，c（一意に決まる場所）はハッシュ表探索の組合せが，それぞれの構成法に対して平均計算量が最も小さくなります。
  • イ誤り。bの使用頻度順に格納した探索表にハッシュ表探索を適用しても，格納位置とコードの対応関係を利用できず効率的ではありません。
  • ウ誤り。aのコード順に格納した探索表に線形探索を適用するのは，2分探索が使える構成を生かしていません。
  • エ誤り。aに線形探索，cに2分探索を割り当てても，それぞれの構成法の特性（順序性やハッシュ化）を生かせず，平均計算量は最小になりません。
応用情報技術者の過去問を演習モードで解く