平成20年秋期試験問題 午前問12

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

  • n+12na2
  • (n+1)(1-a)2
  • (n+1)(1-a)2n2
  • (n+1)(1-a)2+na
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
データ数がnの線形リストを先頭から探索する場合、最小探索回数は1回、最大探索回数はn回なので、目的のデータがある場合の平均探索回数はn+12回です。一方、目的のデータが存在しない場合は、リストの最後まで検索することになるので探索回数は常にn回となります。

データが存在しない確率がaなので、データが存在する確率は(1-a)です。したがって、設問の探索処理における平均探索回数は、以下の2つを足し合わせた式で表すことができます。
対象がリストに存在する場合の平均探索回数×対象が存在する確率
n+12×(1-a)
対象がリストに存在しない場合の探索回数×対象が存在しない確率
n×a
つまり、
 平均比較回数=n+12×(1-a)+n×a
となり、この数式を整えると、(n+1)(1-a)2+na になります。

この問題の出題歴


Pagetop