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

 相異なるn 個のデータが昇順に整列された表がある。この表を1ブロックm 個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、目的のデータの存在するブロックを探し出す。次に当該ブロック内を線形探索して目的のデータを探し出す。このときの平均探索回数はどれか。ここで、mnとし、目的のデータは必ず表の中に存在するものとする。

     ア ─    

      イ ───     2

        ウ  + ─       

       エ ─ + ──    2  2


解答

 エ

解説

 x 個のデータからの線形探索に要する平均探索回数は、x / 2回すなわちデータ数の半分です。
 本問では、m 個のデータから線形探索を行い、さらにn / m 個のデータから線形探索を行うことなります。したがって、平均探索回数はm / 2 + n / 2m となります。


BohYoh.comトップページへ