情報処理安全確保支援士試験の公開問題
2025 秋 午前I 問03
このページはIPA Advancedが運営する非公式の学習用ページです。IPAとの提携・公認を示すものではありません。
問題文
異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分に大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
選択肢
- ア: \(m + \frac{n}{m}\)
- イ: \(\frac{m}{2} + \frac{n}{2m}\)
- ウ: \(\frac{n}{m}\)
- エ: \(\frac{n}{2m}\)
解説の要点
添付の公式解答表では，問3の正答は「イ」。探索は，ブロックを特定する段階と，そのブロック内で目的のデータを探す段階に分かれる。ブロックは n/m 個あり，線形探索の平均比較回数は探索対象数のおよそ半分として評価するので，第1段階は約 n/(2m) 回，第2段階は約 m/2 回となる。したがって，合計は m/2 + n/(2m) です。設問の条件に従い，細かな定数項を省いた近似で考える。
小さな配列で線形探索を試し、比較回数の記録から平均を求める手順を確認できますか。
関連する問題一覧
公式出典
訂正・編集方針
解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。