基本情報技術者試験 2002年度 = 平成14年度・春期 午前 問15

 探索に要する平均比較回数が最も少ないものはどれか。

 ア  2分探索木を用いた探索
 イ  衝突の確率が無視できるほど小さいハッシュ表を用いた探索
 ウ  整列済みの配列を用いた2分探索
 エ  重複登録のないリストを用いた線形探索

解答

 イ

解説

 データ数をnとすると、それぞれの平均比較回数は次のようになります。

  2分探索木を用いた探索   log 2n 
  衝突の確率が無視できるほど小さいハッシュ表を用いた探索   1 
  整列済みの配列を用いた2分探索   log 2n 
  重複登録のないリストを用いた線形探索   n / 2 

 ハッシュ法は、キー値に対して何らかの変換関数を適用することによって、そのデータを格納する配列の添字を求める手法です。衝突が発生しない限り、キー値から直接添字を求められるため、比較の回数は1回だけとなります。


BohYoh.comトップページへ