第2種情報処理技術者試験 1995年度 = 平成7年度・秋期 午前 問14

 探索法に関する記述のうち、誤っているものはどれか。

 ア  2分探索法を利用する場合、データは整列されている必要がある。
 イ  100件分のデータを2分探索法で探索する場合、最大でも7回の比較によって目的のデータが探索できる。
 ウ  線形探索法では、データが整列されていても比較回数が少なくなるとは限らない。
 エ  データが10件以内ならば、2分探索法より線形探索法のほうが平均比較回数は少ない。
 オ  データの件数を100件から1,000件に増やすと、線形探索法では平均比較回数が10倍に増えるが、2分探索法では2倍以下である。

解答

 エ

解説

●2分探索法は、整列済みの配列の中央に位置する要素と等しいか/大きいか/小さいかの判断を行い、探索すべき範囲を半分ずつに絞り込んでいく探索法であり、探索に要する平均比較回数はlog2nです。
●線形探索法は、配列の先頭から順に比較を行っていく探索法であり、探索に要する平均比較回数はn / 2です。
 したがって、データが10件以内ならば、2分探索法より線形探索法のほうが平均比較回数は多くなります。


BohYoh.comトップページへ