令和7年度秋期応用情報技術者試験午前問6

この問題は2025(R7)秋応用情報技術者午前に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

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

ア.

m + \frac{n}{m}

イ.

\frac{m}{2} + \frac{n}{2m}

ウ.

\frac{n}{m}

エ.

\frac{n}{2m}

解答・解説を読む

正解: 選択肢イ

データの総数 $n$ 、ブロックの要素数 $m$ とすると、ブロックの数は $\frac{n}{m}$ 個となります。

目的のデータを探すための手順は以下の2段階に分かれます。

ブロックの探索
$\frac{n}{m}$ 個のブロックの最後尾のデータに対して線形探索を行います。要素数 $k$ のデータを線形探索するときの平均比較回数は $\frac{k+1}{2}$ となります。したがって、ブロック探索の平均比較回数は $\frac{\frac{n}{m}+1}{2} = \frac{n}{2m} + \frac{1}{2}$ 回となります。
ブロック内の探索
特定したブロックの中にある $m$ 個のデータに対して線形探索を行います。同様に、このときの平均比較回数は $\frac{m+1}{2} = \frac{m}{2} + \frac{1}{2}$ 回となります。

全体の平均比較回数はこれらを足し合わせたものになります。
$\left(\frac{n}{2m} + \frac{1}{2}\right) + \left(\frac{m}{2} + \frac{1}{2}\right) = \frac{n}{2m} + \frac{m}{2} + 1$

ここで問題文より「 $m$ は十分に大きく」という条件があるため、定数項の $1$ を無視（近似）すると、平均比較回数は $\frac{m}{2} + \frac{n}{2m}$ となります。よって正解は「イ」です。

各選択肢の解説

ア： $m + \frac{n}{m}$ は、ブロック探索とブロック内探索の 最大比較回数 （最も運が悪かった場合の回数）を足し合わせた近似式です。
イ：正解です。平均比較回数の近似式を表しています。
ウ： $\frac{n}{m}$ は、ブロック探索における 最大比較回数 を表しています。ブロック内の探索回数が考慮されていません。
エ： $\frac{n}{2m}$ は、ブロック探索における 平均比較回数 の近似式を表しています。ブロック内の探索回数が考慮されていません。