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

問 8
応用情報技術者試験 2018年(平成30年度)秋期 午前

探索表の構成法を例とともに a〜c に示す。最も適した探索手法の組合せはどれか。ここで,探索表のコードの空欄は表の空きを示す。

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

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

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

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

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

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

正解は「ア」です。

  • a はコードの値の順に格納された表なので,中央の値と比較して探索範囲を半分に絞り込む 2 分探索が最も適しています。
  • b はコード順ではなく使用頻度の高い順に格納されているため,2 分探索は使えません。先頭から順に調べる線形探索が適しています(頻度の高いものが先頭にあるので平均比較回数を減らせます)。
  • c はコードから格納場所が一意に決まるので,ハッシュ表探索が適しています。

よって a=2 分探索,b=線形探索,c=ハッシュ表探索の「ア」が正解です。

関連問題

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