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

正解

イ. m/2＋n/2m

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

問題の解説

探索は、ブロックの最後尾を順に調べる段階と、見つけたブロック内を順に調べる段階の二つに分かれる。ブロック数は なので、平均はその半分の 回である。ブロック内は 個を平均して約 回で探せる。両者の和 が平均比較回数である。

選択肢ごとの解説

• アブロック数 n/m とブロック内の個数 m を足した値で、どちらも最悪の場合の比較回数であり、平均ではない。
• イ正しい。ブロックを選ぶ段階の平均 n/(2m) 回と、ブロック内を探す段階の平均 m/2 回の和である。
• ウブロックの数であり、最後尾を全て調べたときの回数にすぎない。ブロック内の探索も、平均を取ることも反映していない。
• エブロックを選ぶ段階の平均比較回数だけで、ブロック内の線形探索の分（m/2 回）が抜けている。