従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率をaとする。

選択肢

• ア(n+1)na / 2
• イ(n+1)(1-a) / 2
• ウ(n+1)(1-a)/2 + n/2
• エ(n+1)(1-a)/2 + na

正解と解説

正解：エ (n+1)(1-a)/2 + na

表に存在する場合（確率1-a）は、目的の要素が先頭からn番目までのどこかに等確率であるので平均比較回数は(n+1)/2になる。存在しない場合（確率a）は末尾まで調べ切るのでn回である。両者を確率で重み付けして足すと(n+1)(1-a)/2 + na となる。

選択肢ごとの解説

• ア存在する場合の項に確率aを掛けており、確率の割り当てが逆になっている。
• イ存在しない場合のn回の比較が抜け落ちている。
• ウ存在しない場合の比較回数をn/2としており、末尾まで調べ切る事実と合わない。
• エ存在する場合の(n+1)/2と存在しない場合のnを、それぞれの確率で重み付けした正しい式。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 午前 問6
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 午前 問6
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 午前 問19
• 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力…2018年度 秋期 午前 問27
• 探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す…2018年度 秋期 午前 問8