HOME»ソフトウェア開発技術者平成20年秋期»午前問12
ソフトウェア開発技術者平成20年秋期 午前問12
問12
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率を aとする。
- n＋12＋na2
- (n＋1)(1－a)2
- (n＋1)(1－a)2＋n2
- (n＋1)(1－a)2＋na
- [出題歴]
- 応用情報技術者 R5春期 問6
- 応用情報技術者 H26春期 問6
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
エ
解説
データ数がnの線形リストを先頭から探索する場合、最小探索回数は1回、最大探索回数はn回なので、目的のデータがある場合の平均探索回数はn＋12回です。一方、目的のデータが存在しない場合は、リストの最後まで検索することになるので探索回数は常にn回となります。
データが存在しない確率がaなので、データが存在する確率は(1－a)です。したがって、設問の探索処理における平均探索回数は、以下の2つを足し合わせた式で表すことができます。
平均比較回数＝n＋12×(1－a)＋n×a
となり、この数式を整えると、(n＋1)(1－a)2＋na になります。
データが存在しない確率がaなので、データが存在する確率は(1－a)です。したがって、設問の探索処理における平均探索回数は、以下の2つを足し合わせた式で表すことができます。
- 対象がリストに存在する場合の平均探索回数×対象が存在する確率
- n＋12×(1－a)
- 対象がリストに存在しない場合の探索回数×対象が存在しない確率
- n×a
平均比較回数＝n＋12×(1－a)＋n×a
となり、この数式を整えると、(n＋1)(1－a)2＋na になります。