【基本情報技術者試験平成14年春期午前】問題・解説・解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成14年春期基本情報技術者午前問15

問15　　 探索に要する平均比較回数

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

ア　２分探索木を用いた探索

イ　衝突の確率が無視できるほど小さいハッシュ表を用いた探索

ウ　整列済みの配列を用いた２分探索

エ　重複登録のないリストを用いた線形探索

解説

ア：２分探索木を用いた探索の平均比較回数は、log₂n になる。

イ：衝突の確率がほとんどないハッシュ表を用いた探索の平均比較回数は１回である

ウ：整列済みの配列を用いた２分探索の平均比較回数は、log₂n になる。

エ：重複登録のないリストを用いた線形探索の平均比較回数は、n／2 になる。