令和7年度秋期 応用情報技術者試験 午前 問6
異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分に大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。
- ア m＋n/m
- イ m/2＋n/(2m)
- ウ n/m
- エ n/(2m)
解答・解説を見る
正解：イ
AI解説
ブロック分割による探索では、まず各ブロックの最後尾のn/m個のデータを線形探索して目的のブロックを見つけ(平均比較回数はn/(2m)回)、次にそのブロック内のm個のデータを線形探索する(平均比較回数はm/2回)。両者の合計であるm/2+n/(2m)が全体の平均比較回数となる。 ア: m+n/mは、平均ではなく最大回数に近い形の式や、割り算の位置を誤った場合に生じ得る式であり、平均比較回数の正しい式とは異なる。 イ: 正しい。ブロック探索の平均比較回数n/(2m)と、ブロック内探索の平均比較回数m/2を足し合わせたm/2+n/(2m)が正しい式である。 ウ: n/mは、ブロックの個数(またはブロック探索の最大回数)を表す式であり、平均比較回数を表す式ではない。 エ: n/(2m)は、ブロックを探し出す部分の平均比較回数のみであり、ブロック内探索の分(m/2)を含んでいない。 💡 2段階の線形探索(索引付き順次探索)では、「各段階の平均比較回数(要素数の半分)」をそれぞれ求めてから合計する、という考え方を身につけておくとよい。
出典：令和7年度 秋期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。