令和7年度秋期プロジェクトマネージャ試験データベーススペシャリスト試験エンベデッドシステムスペシャリスト試験システム監査技術者試験情報処理安全確保支援士試験午前Ⅰ 問題【共通】問3

この問題は2025(R7)秋高度試験共通午前Iに出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

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

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

ア.

m+\frac{n}{m}

イ.

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

ウ.

\frac{n}{m}

エ.

\frac{n}{2m}

解答・解説を読む

正解: 選択肢イ

ブロック分割による線形探索の平均比較回数を求める問題です。
探索は「ブロックの特定」と「ブロック内の探索」の2段階で行われます。

ブロックの特定
- 全データ数 $n$ 、1ブロックのデータ数 $m$ なので、ブロックの総数は $\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}$ 回となります。

これら2段階の平均比較回数を合計すると、
$\left(\frac{n}{2m} + \frac{1}{2}\right) + \left(\frac{m}{2} + \frac{1}{2}\right) = \frac{m}{2} + \frac{n}{2m} + 1$
となります。
$m$ と $n$ が十分に大きい場合、定数項（ $+1$ ）の影響は微小となるため省略され、 $\frac{m}{2} + \frac{n}{2m}$ が平均比較回数を表す式となります。よって正解はイです。

各選択肢の解説

ア（ $m+\frac{n}{m}$ ）: 誤り。ブロック探索の最大回数 $\frac{n}{m}$ 回と、ブロック内探索の最大回数 $m$ 回を足し合わせた、最大比較回数（最悪の場合の回数）に近い式です。
イ（ $\frac{m}{2}+\frac{n}{2m}$ ）: 正解。ブロックの特定の平均比較回数と、ブロック内の平均比較回数の和です。
ウ（ $\frac{n}{m}$ ）: 誤り。ブロックの総数を表しており、ブロックを探索するための最大比較回数に相当します。ブロック内の探索回数が考慮されていません。
エ（ $\frac{n}{2m}$ ）: 誤り。ブロックを探索するための平均比較回数のみを表しており、ブロック内を探索する回数が考慮されていません。