平成24年度 春期 午前 問9

✓ これが正解イm／2＋n／（2m）

解説

各段の平均は個数の半分で、その和になります。

探索が二段になっていますので、段ごとに平均比較回数を出して足します。線形探索の平均比較回数は、目的のものが必ず含まれているとき、調べる対象の個数の半分になります。一段目は各ブロックの最後尾だけを順に見ますから、調べる対象はブロックの個数で、これは全体の件数をブロックの大きさで割った数です。その半分が一段目の平均になります。二段目は見つけたブロックの中を順に見ますので、調べる対象はブロックの大きさそのもので、その半分が二段目の平均です。二つを足した式が求める答えです。具体的な数で確かめると、全体が一万件でブロックが百件なら、一段目も二段目も平均五十回で合計百回になり、式に当てはめた値と一致します。目的のデータが必ずあるという断りは、見つからない場合を考えなくてよいという意味です。

ほかの選択肢はなぜ違うのか

• アm＋n／m：ブロックの個数とブロックの大きさをそのまま足した形で、どちらの段についても半分にする操作が抜けています。設問が問うているのは平均であって、最後まで調べた場合の回数ではありません。
• ウn／m：ブロックの個数そのもので、一段目を最後まで調べた場合に相当します。半分にする操作も、見つけたブロックの中を調べる二段目の回数も含まれていません。
• エn／（2m）：一段目の平均だけを表した式です。目的のデータが入っているブロックを見つけたあと、その中を順に調べる分の比較回数が加えられていませんので、二段目が抜け落ちています。