問題
相異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し、各ブロックの最後尾の要素だけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、m は十分大きく、n は m の倍数とし、目的のデータは必ず表の中に存在するものとする。
選択肢
- 1m＋n/m
- 2m/2＋n/2m
- 3n/m
- 4n/2m
正解
2. m/2＋n/2m
詳しい解説を見る解説を閉じる
解説
ブロックは全部で n/m 個あり、目的のブロックを最後尾要素の線形探索で見つけるまでの平均比較回数は (n/m)/2＝n/2m 回である。さらに当該ブロック内（m 個）を線形探索する平均比較回数は m/2 回である。両者の和 m/2＋n/2m が平均比較回数となるので、イが正解である。（出典: 平成24年度 春期 応用情報技術者試験 午前 問9）
一問一答
全400問を繰り返し学習