令和5年度春期応用情報技術者試験午前問6

この問題は2023(R5)春応用情報技術者午前に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

従業員番号と氏名の対が n件格納されている表に線形探索法を用いて, 与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで, 検索する従業員番号はランダムに出現し, 探索は常に表の先頭から行う。また, 与えられた従業員番号がこの表に存在しない確率を a とする。

ア.

\frac{(n+1)na}{2}

イ.

\frac{(n+1)(1-a)}{2}

ウ.

\frac{(n+1)(1-a)}{2} + \frac{n}{2}

エ.

\frac{(n+1)(1-a)}{2} + na

解答・解説を読む

正解: 選択肢エ

線形探索法（リニアサーチ）における平均比較回数を求める問題です。探索対象が表に存在する場合と存在しない場合に分けて期待値を計算します。

探索対象が表に存在する場合 与えられた従業員番号が表に存在する確率は $(1-a)$ です。ランダムに出現するため、1件目で見つかる、2件目で見つかる、...、 $n$ 件目で見つかる確率はそれぞれ等しくなります。この場合の平均比較回数は、 $(1 + 2 + \dots + n) \div n = \frac{n+1}{2}$ 回となります。
探索対象が表に存在しない場合 与えられた従業員番号が表に存在しない確率は $a$ です。この場合、表の先頭から末尾まですべてのデータを比較して初めて「存在しない」ことがわかるため、比較回数は必ず $n$ 回となります。全体の平均比較回数は、それぞれの期待値の和となるため、以下の式で求められます。 $\frac{n+1}{2} \times (1-a) + n \times a = \frac{(n+1)(1-a)}{2} + na$

各選択肢の解説

ア: 誤り。存在する場合の平均比較回数に、さらに $na$ を掛けたような不適切な式です。
イ: 誤り。探索対象が存在する場合の比較回数の期待値のみを計算しており、存在しない場合の比較回数が考慮されていません。
ウ: 誤り。存在しない場合の比較回数について、回数や確率の考慮が不正確な式です。
エ: 正解。存在する場合と存在しない場合それぞれの期待値の和を正しく表しています。