応用情報技術者試験 応用情報技術者試験 平成30年度春期 午前 問6: 異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的

正解

イ. m/2＋n/2m

正答率 48.8%（594人中 290人が正解）

問題の解説

2段階の線形探索の平均比較回数を求める問題。線形探索の平均比較回数は「対象件数の約半分」になることがポイント。第1段階では n 個を m 個ずつに分けた n/m 個のブロックの最後尾だけを線形探索するので、平均比較回数は (n/m)÷2 ＝ n/2m 回。第2段階では目的のブロック内の m 個を線形探索するので、平均比較回数は m÷2 ＝ m/2 回。両者を合計すると m/2 ＋ n/2m となり、イが正解。「探索対象の数の半分」という線形探索の平均回数を2回の探索それぞれに当てはめるのがコツ。