応用情報に戻る
線形探索難易度: 標準2023年度

応用情報技術者 過去問線形探索 2023年度 第6問

問題

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

選択肢

  1. 1(n+1)na/2
  2. 2(n+1)(1−a)/2
  3. 3(n+1)(1−a)/2 + n/2
  4. 4(n+1)(1−a)/2 + na

正解

4. (n+1)(1−a)/2 + na

詳しい解説を見る

解説

表に存在する場合(確率 1−a)の平均比較回数は (n+1)/2、存在しない場合(確率 a)は最後まで調べるので n 回となる。期待値は (1−a)×(n+1)/2 + a×n=(n+1)(1−a)/2 + na。よってエが正解。存在しない場合に必ず n 回比較する点を na の項で正しく加算している。(出典: 令和5年度 春期 応用情報技術者試験 午前 問6)

一問一答

全400問を繰り返し学習

同じ年度の過去問

この調子で演習を続けよう

スキマ資格では応用情報の全3360問を分野別・難易度別に体系的に学習できます。応用情報技術者試験(AP)は IPA が実施する情報処理技術者試験のレベル3。2026年度からCBT方式へ移行し、科目A(四肢択一80問)・科目B(記述11問中5問選択)の2部構成で、それぞれ基準点以上が必要です。テクノロジ・マネジメント・ストラテジの全分野から出題されます。