異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分に大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。
平成30年度 春期 応用情報技術者 問6
テクノロジ系
正解と解説
正解 イ
ブロックの数はn/m個なので、ブロックを探す平均比較回数はn/2mです。ブロック内を探す平均比較回数はm/2なので、合計はm/2＋n/2mです。
表をm個ずつに分けると、ブロックの数はn/m個です。線形探索の平均比較回数は、探す範囲の要素数の約半分です。各ブロックの最後尾だけを線形探索して目的のブロックを見つける平均比較回数は、(n/m)/2＝n/2mです。見つけたブロック内のm個を線形探索する平均比較回数は、m/2です。合計の平均比較回数は、m/2＋n/2mです。
ア：m＋n/mは、ブロックの探索とブロック内の探索がともに最後まで比較する場合の回数です。最悪の比較回数であり、平均ではありません。
ウ：n/mは、ブロックの最後尾をすべて比較する最悪の回数です。ブロック内の探索の回数も含まれていません。
エ：n/2mは、目的のブロックを探すまでの平均比較回数だけです。ブロック内の探索の平均比較回数m/2が足されていません。
出典：平成30年度 春期 応用情報技術者試験 問6
全年度から出題。10問で実力を判定します。登録不要。
出典：平成30年度 春期 応用情報技術者試験 問6（独立行政法人情報処理推進機構）
解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方