応用情報技術者平成26年春期 午前問6

午前問6

従業員番号と氏名の対がn件格納されている表に線形探索法を用いて,与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで,検索する従業員番号はランダムに出現し,探索は常に表の先頭から行う。また,与えられた従業員番号がこの表に存在しない確率をaとする。
  • n+12na2
  • (n+1)(1−a)2
  • (n+1)(1−a)2n2
  • (n+1)(1−a)2+na
  • [この問題の出題歴]
  • ソフトウェア開発技術者 H20秋期 問12

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

データ数がnの線形リストを先頭から探索する場合、最小探索回数は1回、最大探索回数はn回なので、平均探索回数は(n+1)/2回で表されます。またデータが存在しない場合は、必ずリストの最後まで検索することになるので探索回数は常にn回となります。

データが存在しない確率がaなので、データが存在する確率は(1−a)です。

この処理における平均探索回数は、

 対象がリストに存在する場合の平均探索回数×対象が存在する確率=n+12×(1−a)

と、

 対象がリストに存在しない場合の探索回数×対象が存在しない確率=n×a

を足し合わせた値になります。

この数式を整えると、(n+1)(1−a)2+na になります。
© 2010-2022 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop