異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、mは十分に大きく、nはmの倍数とし、目的のデータは必ず表の中に存在するものとする。

選択肢

• アm＋n/m
• イm/2＋n/2m
• ウn/m
• エn/2m

正解と解説

正解：イ m/2＋n/2m

表はn/m個のブロックに分かれる。まず各ブロック末尾の値を線形探索してブロックを特定するので、その平均比較回数はブロック数の半分でn/(2m)回になる。次に見つけたブロック内をm個から線形探索するのでm/2回。合計はm/2＋n/(2m)回となる。

選択肢ごとの解説

• アブロック内・ブロック間とも最悪回数を足しており、平均ではなく最大値。
• イ正解。ブロック内の平均m/2回と、ブロック探索の平均n/(2m)回の合計。
• ウブロック数そのもので、ブロック内の探索と平均化が考慮されていない。
• エブロックを特定するまでの平均回数だけで、ブロック内探索が抜けている。

同じ分野の他の問題

• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 午前 問6
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 午前 問19
• 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における…2023年度 春期 午前 問6
• 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力…2018年度 秋期 午前 問27
• 探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す…2018年度 秋期 午前 問8