問題プレビューID: f11b6662基本情報技術者試験 午前免除試験 2021年7月25日

問 9
基本情報技術者試験 午前免除試験 2021年7月25日

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

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

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

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

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

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

コードデータ
  
120381⋯⋯⋯⋯
  
120520⋯⋯⋯⋯
140140⋯⋯⋯⋯
  
120380⋯⋯⋯⋯
  
Label

a

b

c

ア

2 分探索

線形探索

ハッシュ表探索

イ

2 分探索

ハッシュ表探索

線形探索

ウ

線形探索

2 分探索

ハッシュ表探索

エ

線形探索

ハッシュ表探索

2 分探索

解説

正解は「ア」です。

  • a: コードの値の順(昇順)に格納されているので,中央の要素と比較して探索範囲を半分に絞り込む 2 分探索が適しています。
  • b: 使用頻度の高い順に格納されているので,先頭から順に調べる線形探索が適しています。よく使うデータほど早く見つかります。
  • c: コードの値から格納場所が一意に決まるように配置されているので,ハッシュ関数で格納場所を計算するハッシュ表探索が適しています。

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

  • イ・ウ・エ: いずれも a 〜 c と探索手法の対応が入れ替わっており,誤りです。

関連問題

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