線形探索の平均比較回数を求めるには、「探索対象が表に存在する場合」と「存在しない場合」の期待値を算出し合計します。
2014年度 春期 応用情報技術者 午前 問6
難度
標準
従業員番号と氏名の対がn 件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率をaとする。
選択肢
解説
結論 → 詳細 → 補足 の 3 層構成
展開閉じる
解説
結論 → 詳細 → 補足 の 3 層構成
詳細Layer 2展開閉じる
探索対象が存在する確率は(1-a)で、データはランダムに出現するため、平均比較回数は(n+1)/2回です。よって、この場合の期待値は (n+1)(1-a)/2 となります。一方、探索対象が存在しない確率はaであり、この場合は必ず表の最後まで探索するため比較回数はn回です。したがって、この場合の期待値はnaとなります。両者を合計した (n+1)(1-a)/2 + na が全体の平均比較回数を表す式です。
この解説は？
分野「アルゴリズムとプログラミング」の学習ポイント
この問題の理解を「分野全体の力」に広げるための足がかり
- 何が問われるか
- 計算量（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で割った余りを表す。
- 令和5年度 秋期応用情報技術者 午前 問3逆ポーランド表記法(後置記法)で表現されている式 ABCD-×+において、A=16, B=8, C=4, D=2のときの演算結果はどれか。逆ポーランド表記法による式AB+は、中置記法による式A+Bと同一である。
- 令和4年度 春期応用情報技術者 午前 問5リストには、配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として、適切なものはどれか。ここで、配列を用いたリストは配列に要素を連続して格納することによってリストを構成し、ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリ…
- 令和3年度 秋期応用情報技術者 午前 問5バブルソートの説明として、適切なものはどれか。
応用情報技術者 の学習ガイド
応用情報技術者 勉強時間の目安｜基本情報合格者・実務経験者・初学者別の合格モデル
応用情報技術者試験の合格に必要な勉強時間を、基本情報合格者・実務経験者・初学者の3パターン別に分解。午前・午後の時間配分と社会人の週次スケジュール例を実例で解説します。
基本情報を飛ばして応用情報から受けてもいい？｜FEを省略してAPに挑む判断基準
基本情報（FE）を飛ばして応用情報（AP）からいきなり受けてもよいか。受験資格に制限はなく可能ですが、向き不向きがあります。飛ばしてよいケース・避けたほうがよいケース・注意点を、FEとAPの違いをふまえて正直に整理します。
応用情報技術者試験を取る意味はあるか｜APのメリットと「意味ない」と言われる理由を整理
応用情報技術者試験（AP）は「意味ない」と言われることがある資格です。取得メリットと「役に立たない」と言われる理由を、転職・実務・高度試験への接続の3観点で整理し、誰に向くのかを正直に解説します。
応用情報 午後 文系・非エンジニア向け選択科目4選｜暗記より読解で勝つ
応用情報技術者試験の午後選択を「文系・非エンジニア」目線で再構成。プログラミングを避けて読解力で勝てる4科目の選び方と、各科目の解答パターンを解説します。