令和7年度秋期 プロジェクトマネージャ 午前Ⅰ 問3

線形探索と平均値

探索位置ごとの比較回数の数え方と、出現頻度を使った平均の求め方を準備しましょう。

この問題で問われていること

小さな配列で線形探索を試し、比較回数の記録から平均を求める手順を確認できますか。

線形探索と平均値

小さな配列で線形探索を試し、比較回数の記録から平均を求める手順を確認できますか。

確認ポイント

• 線形探索で先頭・途中・末尾のデータを探す場合、それぞれどの比較まで数えるか確認できますか。
• 探索対象を全データに一つずつ替えたとき、比較回数の一覧から平均を求められますか。
• 同じ大きさのグループに分けた小さな表で、各グループとグループ内の各位置が探索対象になる頻度を数えられますか。 連続する整数の平均の求め方を調べ、項数が多い場合に端の項の扱いがどの程度影響するか確認できますか。

正解

イ

解説

添付の公式解答表では，問3の正答は「イ」。探索は，ブロックを特定する段階と，そのブロック内で目的のデータを探す段階に分かれる。ブロックは n/m 個あり，線形探索の平均比較回数は探索対象数のおよそ半分として評価するので，第1段階は約 n/(2m) 回，第2段階は約 m/2 回となる。したがって，合計は m/2 + n/(2m) です。設問の条件に従い，細かな定数項を省いた近似で考える。

添付の公式解答表では，問3の正答は「イ」。探索は，ブロックを特定する段階と，そのブロック内で目的のデータを探す段階に分かれる。ブロックは n/m 個あり，線形探索の平均比較回数は探索対象数のおよそ半分として評価するので，第1段階は約 n/(2m) 回，第2段階は約 m/2 回となる。したがって，合計は m/2 + n/(2m) です。設問の条件に従い，細かな定数項を省いた近似で考える。

選択肢ア

誤り。ブロック数 n/m とブロック内のデータ数 m をそのまま加えており，両段階を最後まで探索する場合の比較回数に相当する。平均比較回数を表していない。

選択肢イ（正解）

正しい。ブロック数は n/m なので，ブロックを特定する平均比較回数は約 n/(2m)。ブロック内の探索には平均で約 m/2 回の比較が必要となり，両者を加えた式になる。

選択肢ウ

誤り。これはブロックの総数を表す。ブロックを特定する探索の平均を考慮しておらず，ブロック内を探索する比較回数も含まれていない。

選択肢エ

誤り。ブロックを特定するための平均比較回数に相当するが，その後のブロック内の線形探索に必要な比較回数が含まれていない。

学習のポイント

小さな配列で線形探索を試し、比較回数の記録から平均を求める手順を確認できますか。