この問題では、線形探索法（Linear Search）における平均比較回数を問われています。線形探索法とは、リストの先頭から順番に目的のデータを探していく探索方法です。
令和5年度 春期 応用情報技術者 午前 問6
難度
標準
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率をaとする。
選択肢
解説
結論 → 詳細 → 補足 の 3 層構成
展開閉じる
解説
結論 → 詳細 → 補足 の 3 層構成
詳細Layer 2展開閉じる
まず、検索対象の従業員番号が表に「存在する」確率は (1-a) です。従業員番号が存在する場合、探索は先頭から順番に行われ、平均して表の半分（n/2）の位置で見つかると考えられます。ただし、最悪の場合は最後のn番目まで比較することになります。
補足Layer 3展開閉じる
一方、検索対象の従業員番号が表に「存在しない」確率は a です。この場合、表の全ての要素（n件）を比較する必要があり、比較回数は必ずn回となります。
したがって、平均比較回数は、「存在する確率 × 存在する場合の平均比較回数」＋「存在しない確率 × 存在しない場合の比較回数」で求められます。
（1-a）× (n+1)/2 ＋ a × n となります。
（1-a）× (n+1)/2 は、従業員番号が存在し、かつ先頭から平均して表の半数（(n+1)/2、これは探索が成功した場合の平均位置です）で見つかる場合を考慮しています。
a × n は、従業員番号が存在しない場合に、表の全ての要素n件を比較する場合です。
これらの項を整理すると、(1-a)(n+1)/2 + na となり、選択肢エが正解となります。
誤りの選択肢についてですが、アはaの項がnではなくnaになっており、イとウは存在しない場合の比較回数nが考慮されていません。
この解説は？
分野「アルゴリズムとプログラミング」の学習ポイント
この問題の理解を「分野全体の力」に広げるための足がかり
- 何が問われるか
- 計算量（O 記法）・基本データ構造・典型アルゴリズム（探索・整列）・再帰の挙動を読む力。
- 学習の進め方
- 擬似コードを実際にトレースして変数の遷移を表に書き出す習慣を付ける。スタック/キュー/木の図示が定着の鍵。
- 関連キーワード
- 計算量二分探索クイックソート再帰スタックキュー木構造
AI コパイロット
この問題を AI と深掘りする
用語解説・選択肢分析・類題生成をその場で対話。クイズモードでは解答→解説がゼロ遷移。
関連する問題
アルゴリズムとプログラミング の他の問題
- 応用情報技術者2009年度 秋期 午前 問5n個の要素x₁,x₂,…,xₙから成る単方向の連結リストに対して、新たな要素xₙ₊₁の末尾への追加に要する時間をf(n)とし、末尾の要素xₙの削除に要する時間をg(n)とする。nが非常に大きいとき、実装方法1と実装方法2におけるg(n)/f(n)の挙動として、適切なものはどれか。…
- 応用情報技術者2009年度 秋期 午前 問6流れ図で表される処理を複数回実行した場合、途中に出現し得る実行順序はどれか。ここで、二重線は並列処理の同期を表す。 原図の構成：同期点から左側のA→Bと右側のX→Yへ並列に分かれ、BとYの両方の終了を同期点で待ち合わせた後、次の周回のA及びXへ進む。
- 応用情報技術者2009年度 春期 午前 問7文字列を引数とする関数len、first、butfirstを用いて、関数compを再帰的に定義した。comp("11", "101")を呼び出したとき、返されるものはどれか。 〔関数の定義〕 - len(S)：文字列Sの長さを返す。空文字列なら0。 - first(S)：先頭の…
- 応用情報技術者2009年度 春期 午前 問8相異なるn個のデータが昇順に整列された表がある。この表をm 個のデータごとの ブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、 目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して 目的のデータを探し出す。このときの平均比較回数…
- 応用情報技術者2009年度 春期 午前 問20データ構造のキューを実現する方法において、片方向リンクに比べた場合の双方向 リンクの特徴として、適切なものはどれか。
他試験区分の同分野問題
応用情報技術者 と共通カリキュラムの他区分で「アルゴリズムとプログラミング」分野を演習する
他年度の「アルゴリズムとプログラミング」問題
応用情報技術者 の同じ分野を年度をまたいで演習する
- 令和7年度 秋期応用情報技術者 午前 問6異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式は…
- 令和6年度 秋期応用情報技術者 午前 問6自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数 h(x)を h (x) = x mod n とすると、任意のキーaとbが衝突する条件はどれか。ここで、nはハッシュ表の大きさであり, x mod nはxをnで割った余りを表す。
- 令和4年度 春期応用情報技術者 午前 問5リストには、配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として、適切なものはどれか。ここで、配列を用いたリストは配列に要素を連続して格納することによってリストを構成し、ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリ…
- 令和3年度 秋期応用情報技術者 午前 問5バブルソートの説明として、適切なものはどれか。
- 令和2年度 10月試験応用情報技術者 午前 問3式A+B×Cの逆ポーランド表記法による表現として、適切なものはどれか。
応用情報技術者 の学習ガイド
応用情報技術者 勉強時間の目安｜基本情報合格者・実務経験者・初学者別の合格モデル
応用情報技術者試験の合格に必要な勉強時間を、基本情報合格者・実務経験者・初学者の3パターン別に分解。午前・午後の時間配分と社会人の週次スケジュール例を実例で解説します。
基本情報を飛ばして応用情報から受けてもいい？｜FEを省略してAPに挑む判断基準
基本情報（FE）を飛ばして応用情報（AP）からいきなり受けてもよいか。受験資格に制限はなく可能ですが、向き不向きがあります。飛ばしてよいケース・避けたほうがよいケース・注意点を、FEとAPの違いをふまえて正直に整理します。
応用情報技術者試験を取る意味はあるか｜APのメリットと「意味ない」と言われる理由を整理
応用情報技術者試験（AP）は「意味ない」と言われることがある資格です。取得メリットと「役に立たない」と言われる理由を、転職・実務・高度試験への接続の3観点で整理し、誰に向くのかを正直に解説します。
応用情報 午後 文系・非エンジニア向け選択科目4選｜暗記より読解で勝つ
応用情報技術者試験の午後選択を「文系・非エンジニア」目線で再構成。プログラミングを避けて読解力で勝てる4科目の選び方と、各科目の解答パターンを解説します。