| 第２種情報処理技術者試験 |
2000年度 ＝ 平成12年度・秋期 |
午前 |
問14 |
相異なるn 個のデータが昇順に整列された表がある。この表を1ブロックm 個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、目的のデータの存在するブロックを探し出す。次に当該ブロック内を線形探索して目的のデータを探し出す。このときの平均探索回数はどれか。ここで、m ＜ nとし、目的のデータは必ず表の中に存在するものとする。
ｎ
ア ─
ｍ
|
ｎ
イ ───
２ｍ
|
ｎ
ウ ｍ ＋ ─
ｍ
|
ｍ ｎ
エ ─ ＋ ──
２ ２ｍ
|
エ
x 個のデータからの線形探索に要する平均探索回数は、x / 2回すなわちデータ数の半分です。
本問では、m 個のデータから線形探索を行い、さらにn / m 個のデータから線形探索を行うことなります。したがって、平均探索回数はm / 2 ＋ n / 2m となります。
