問題プレビューID: 427c34cb応用情報技術者試験 2010年(平成22年度)秋期 午前

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

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

a コード順に格納した探索表

コードデータ
120380……
120381……
120520……
140140……
  
  
  

b コードの使用頻度順に格納した探索表

コードデータ
120381……
140140……
120520……
120380……
  
  
  

c コードから一意に決まる場所に格納した探索表

コードデータ
  
120381……
  
120520……
140140……
  
120380……
解説

正解は「ア」です。

探索表の構成法と,それぞれに適した探索手法の組合せを考えます。

  • a(コード順に格納):コードの大小順に整列されているので 2 分探索が使え,平均計算量は O(log⁡n)O(\log n) と小さくなります。
  • b(使用頻度順に格納):使用頻度の高いコードが先頭にあるほど,先頭から順に調べる線形探索で早く見つかるため,平均計算量が小さくなります。
  • c(コードから一意に決まる場所に格納):ハッシュ表探索が使え,平均計算量はほぼ O(1)O(1) と最も小さくなります。

したがって,a=2 分探索,b=線形探索,c=ハッシュ表探索の組合せである「ア」が正解です。

関連問題

本文が同じ・似ている問題を表示しています