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

• 従業員番号が表に存在する場合（確率 1−a）：先頭から探すので，平均比較回数は (1＋2＋…＋n)/n ＝ (n＋1)/2 回です。
• 従業員番号が表に存在しない場合（確率 a）：最後まで比較するので，比較回数は n 回です。

平均比較回数 ＝ (n＋1)/2 × (1−a) ＋ n × a ＝ (n＋1)(1−a)/2 ＋ na

• ア: (n＋1)/2 ＋ na/2
  誤り。存在する場合の確率 (1−a) が考慮されておらず，存在しない場合も n/2 回になっています。

• イ: (n＋1)(1−a)/2
  誤り。存在しない場合（確率 a）の比較回数 na が含まれていません。

• ウ: (n＋1)(1−a)/2 ＋ n/2
  誤り。存在しない場合の比較回数が確率 a を掛けずに n/2 となっており誤りです。

• エ: (n＋1)(1−a)/2 ＋ na
  正しい。存在する場合と存在しない場合の比較回数を，それぞれの確率で重み付けして足し合わせた正しい式です。

答え

エ: (n＋1)(1−a)/2 ＋ na