従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率を a とする。
平成26年度 春期 応用情報技術者 問6
テクノロジ系
正解と解説
正解 エ
表にあれば平均(n＋1)/2回、なければn回比較します。それぞれに確率1−aとaを掛けて足すと、(n＋1)(1−a)/2＋naです。
線形探索では、表の先頭から1件ずつ比較します。探す番号が表にあるとき、その番号は1〜n件目に同じ確率で現れます。このときの平均比較回数は(1＋2＋…＋n)/n＝(n＋1)/2回です。表にないときは、n件すべてと比較するのでn回です。表にある確率は1−a、ない確率はaです。したがって平均比較回数は(n＋1)/2×(1−a)＋n×a＝(n＋1)(1−a)/2＋naです。
ア：表にある場合の(n＋1)/2に確率1−aを掛けていません。表にない場合の比較回数もn/2ではなくnです。
イ：表にある場合だけを計算しています。表にない場合のn回×確率aが足されていません。
ウ：表にない場合の項がn/2になっています。正しくはn回に確率aを掛けたnaです。
出典：平成26年度 春期 応用情報技術者試験 問6
全年度から出題。10問で実力を判定します。登録不要。
出典：平成26年度 春期 応用情報技術者試験 問6（独立行政法人情報処理推進機構）
解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方