異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分に大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
ア m＋n/m
イ m/2＋n/2m
ウ m/n
エ n/2m
正解: イ
要点: ブロック探索の平均(n/m)/2＋ブロック内線形探索の平均 m/2 ＝ m/2＋n/2m。
ブロック数は n/m。第1段でブロック末尾を線形探索する平均比較回数は (n/m)/2＝n/2m。第2段でブロック内（サイズ m）を線形探索する平均は m/2。合計 m/2＋n/2m。
同じ回の前後の問題
- 令和7年度 秋期 問5: 記憶領域を管理するアルゴリズムのうち，ベストフィット方式の特徴として，適切なものはどれか。
- 令和7年度 秋期 問7: OSS として公開されているプログラム言語である Scala の特徴はどれか。
テクノロジ系の他の問題
- 令和7年度 秋期 問7: OSS として公開されているプログラム言語である Scala の特徴はどれか。
- 令和7年度 秋期 問8: プロセッサの高速化技法の一つとして，同時に実行可能な複数の動作を，コンパイルの段階でまとめて一つの複
- 令和7年度 秋期 問9: 画面表示用フレームバッファがユニファイドメモリ方式であるシステムの特徴はどれか。
- 令和7年度 秋期 問10: モーターの軸に装着された回転センサーから出力されるパルスの周期を，1MHz のクロック周波数でカウン
- 令和7年度 秋期 問11: 現状の HPC マシンを次の条件で更新する。更新後のノード数と総理論ピーク演算性能はどれか。総理論ピ
アプリで弱点分析つきの演習ができます