令和7年度 秋期 午前 問6

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

解説

2 段の線形探索の平均を段ごとに足した式です。

この設問は、整列した表を m 個ずつのブロックに分けて 2 段の線形探索で目的のデータを探す方法について、平均比較回数を表す式を選ばせています。ですから見分けの軸は、ブロックを探す段と、選ばれたブロックの中を探す段の、それぞれの平均比較回数を出してから足しているかという一点だけです。まず、目的があるブロックを、各ブロックの最後尾のデータだけを見て線形に探します。ブロックの個数は n を m で割った値ですから、線形探索の平均比較回数はその半分、すなわち n を 2m で割った値になります。次に見つかったブロックの中を線形に探します。ブロックには m 個のデータが並んでいるので、平均比較回数はその半分、すなわち m を 2 で割った値になります。両方は独立に発生する段ですから、そのまま足し合わせて m を 2 で割った値と n を 2m で割った値の和が、この方式の平均比較回数を表します。

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

• アm ＋ n／m：m と n を m で割った値をそのまま足した式は、それぞれの段の最悪の比較回数を数えた形になっており、平均を求めるための 2 で割る操作が抜けています。設問が問うているのは平均であって最悪ではないため、平均の式としては合致しません。
• ウn／m：n を m で割っただけの式は、ブロックを絞り込む段の総ブロック数を並べたに過ぎず、平均の半分を取る操作も、絞り込んだ後にブロックの中を線形に探す段の比較回数も入っていません。2 段のうち片方の一部にとどまる式です。
• エn／（2m）：n を 2m で割っただけの式は、ブロックを探す段の平均比較回数だけを表したもので、絞り込んだ後にブロックの中を線形に探す段の平均比較回数が欠けています。2 段の合計ではなく、前半の段だけを取り出した式です。