SC情報処理安全確保支援士試験 午前Ⅰ
令和7年度秋期 情報処理安全確保支援士 午前Ⅰ 問3
問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。
問題
選択肢
- アm+n/m
- イm/2+n/(2m)
- ウn/m
- エn/(2m)
解き方のヒントを見る
線形探索と平均値
探索位置ごとの比較回数の数え方と、出現頻度を使った平均の求め方を準備しましょう。
この問題で問われていること
小さな配列で線形探索を試し、比較回数の記録から平均を求める手順を確認できますか。
線形探索と平均値
小さな配列で線形探索を試し、比較回数の記録から平均を求める手順を確認できますか。
確認ポイント
- 線形探索で先頭・途中・末尾のデータを探す場合、それぞれどの比較まで数えるか確認できますか。
- 探索対象を全データに一つずつ替えたとき、比較回数の一覧から平均を求められますか。
- 同じ大きさのグループに分けた小さな表で、各グループとグループ内の各位置が探索対象になる頻度を数えられますか。 連続する整数の平均の求め方を調べ、項数が多い場合に端の項の扱いがどの程度影響するか確認できますか。
正解と解説を見る
正解
イ
解説
問3の正解は「イ」です。探索は,ブロックを特定する段階と,そのブロック内で目的のデータを探す段階に分かれる。ブロックは n/m 個あり,線形探索の平均比較回数は探索対象数のおよそ半分として評価するので,第1段階は約 n/(2m) 回,第2段階は約 m/2 回となる。したがって,合計は m/2 + n/(2m) です。設問の条件に従い,細かな定数項を省いた近似で考える。
正答
正答はイです。線形探索は先頭から順に比較し、目的の要素が見つかった時点で終わるため、見つかる位置が一様に分布していれば平均比較回数は要素数のおよそ半分になる。第1段階はブロックが n/m 個あるので、ブロックを特定する平均比較回数は約 (n/m)/2 = n/(2m) 回です。第2段階はブロック内の m 個を線形探索するので、平均は約 m/2 回です。両段階は続けて行われるため、合計は n/(2m) + m/2 = m/2 + n/(2m) となり、イが正しい。
誤答の理由
ア:両段階を最後まで探索した場合の比較回数に相当し、平均を表していない。ウ:n/m はブロックの総数であり、探索に要する比較回数の平均ではありません。ブロック内の比較も含まれていない。エ:第1段階(ブロックの特定)の平均しか表しておらず、ブロック内の線形探索に必要な約 m/2 回が抜けている。
整理
線形探索の平均比較回数は要素数の約半分であり、多段階の探索では段階ごとの平均を足す。m/2 + n/(2m) は m = √n のとき最小になる(相加平均と相乗平均の関係より)。
選択肢ア
誤り。ブロック数 n/m とブロック内のデータ数 m をそのまま加えており,両段階を最後まで探索する場合の比較回数に相当する。平均比較回数を表していない。
選択肢イ(正解)
正しい。ブロック数は n/m なので,ブロックを特定する平均比較回数は約 n/(2m)。ブロック内の探索には平均で約 m/2 回の比較が必要となり,両者を加えた式になる。
選択肢ウ
誤り。これはブロックの総数を表す。ブロックを特定する探索の平均を考慮しておらず,ブロック内を探索する比較回数も含まれていない。
選択肢エ
誤り。ブロックを特定するための平均比較回数に相当するが,その後のブロック内の線形探索に必要な比較回数が含まれていない。
学習のポイント
小さな配列で線形探索を試し、比較回数の記録から平均を求める手順を確認できますか。
解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。
出典:独立行政法人 情報処理推進機構(IPA)令和7年度秋期 情報処理安全確保支援士試験 午前Ⅰ 問3(公式資料:問題冊子(PDF) / 解答例)
関連する過去問一覧
IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針