令和7年度 秋期 応用情報技術者試験 問6
異なるn個のデータが昇順に整列された表がある。 この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。 次に，当該ブロック内を線形探索して目的のデータを探し出す。 このときの平均比較回数を表す式はどれか。 ここで，mは十分に大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。
正答2
異なるn個のデータが昇順に整列された表がある。 この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。 次に，当該ブロック内を線形探索して目的のデータを探し出す。 このときの平均比較回数を表す式はどれか。 ここで，mは十分に大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。