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

問6

探索表の構成法を例とともに a~c に示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで,探索表のコードの空欄は表の空きを示す。
06.png/image-size:417×234
  • 06a.png/image-size:272×115

            
  • [出題歴]
  • 応用情報技術者 H25春期 問5
  • 応用情報技術者 H30秋期 問8
  • ソフトウェア開発技術者 H17秋期 問14
  • ソフトウェア開発技術者 H19秋期 問11

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

[a コード順に格納した探索表]
探索表はコード順に整列済みなので、線形探索または2分探索を使用可能です。各探索法の平均探索回数は、線形探索が (N+1)/2 回、2分探索法が [log2N] 回ですので、探索表の要素数が同じならば平均探索回数は2分探索のほうが少なくて済みます。したがってa表には2分探索が適切です。(※[n]はnを超えない最大の整数を表します)

[b コードの使用頻度順に格納した探索表]
使用頻度が高いデータほど探索表の先頭のほうに位置していることになります。線形探索では探索表の先頭から順番に探索していくので、このような探索表に対しては効率的に探索できます。
2分探索法は、データが整列されていないと使えないという制限がありますし、この表はハッシュ法に対応していないので、b表に対しては線形探索が唯一使用できる方法となります。

[c コードから一意に決まる場所に格納した探索表]
ハッシュ法は、探索データのキー値から、そのデータの格納場所(アドレス)を直接計算する方法で、(シノニムが発生しなければ)1回の計算で一意に目的のデータにたどりつけます。
1回の探索でいいので、このc表に対して最も計算量が少なくなる探索法はハッシュ表探索です。

したがって、a=2分探索b=線形探索c=ハッシュ表探索の組合せが正解です。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop