基本情報技術者試験
2002年度 ＝ 平成14年度・春期
午前
問15
探索に要する平均比較回数が最も少ないものはどれか。
ア
２分探索木を用いた探索
イ
衝突の確率が無視できるほど小さいハッシュ表を用いた探索
ウ
整列済みの配列を用いた２分探索
エ
重複登録のないリストを用いた線形探索
解答
イ
解説
データ数を
n
とすると、それぞれの平均比較回数は次のようになります。
ア
２分探索木を用いた探索
log
2
n
イ
衝突の確率が無視できるほど小さいハッシュ表を用いた探索
1
ウ
整列済みの配列を用いた２分探索
log
2
n
エ
重複登録のないリストを用いた線形探索
n
/ 2
ハッシュ法
は、キー値に対して何らかの変換関数を適用することによって、そのデータを格納する配列の添字を求める手法です。衝突が発生しない限り、キー値から直接添字を求められるため、比較の回数は1回だけとなります。
