応用情報技術者試験 令和5年度 春期 午前 問6
従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率を a とする。
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】エ
線形探索では、表の先頭から従業員番号を一つずつ比較します。番号が表に存在する場合、先頭にあれば1回、2番目なら2回、末尾ならn回の比較が必要です。各番号が同じ確率で検索されるので、存在する場合の平均比較回数は、（1＋2＋…＋n）÷n＝n（n＋1）÷2÷n＝（n＋1）÷2です。存在する確率は1－aなので、この場合の平均への寄与は（n＋1）（1－a）÷2となります。一方、番号が存在しない場合は末尾まで調べるためn回比較し、その確率はaなので、平均への寄与はnaです。したがって、全体の平均比較回数は（n＋1）（1－a）÷2＋naとなり、エが正解です。
アの（n＋1）na÷2は誤りです。存在する場合と存在しない場合の比較回数を、確率で重み付けして加算していません。
イの（n＋1）（1－a）÷2は誤りです。これは番号が存在する場合だけの平均への寄与であり、存在しない場合の比較回数が含まれていません。
ウの式は誤りです。存在しない場合の寄与をn÷2としていますが、正しくは、末尾まで調べるn回に発生確率aを掛けたnaです。
【ポイント】 平均計算量は、各場合の比較回数に発生確率を掛けて合計します。 線形探索は、探索成功時の平均が（n＋1）÷2回、探索失敗時がn回です。
出典：令和5年度 春期 応用情報技術者試験 午前 問6
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の80問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる