要素数nの配列に対して線形探索を行う場合の平均比較回数はどれか。ただし、探索する値は必ず配列中に存在するものとし、各要素が探索される確率は等しいとする。
ア (n+1)/2
イ n/2
ウ log₂n
エ n
正解: ア
要点: 線形探索では先頭から順に比較し、平均で(n+1)/2回の比較が必要。
この問題に出てくる用語
同じ回の前後の問題
- 令和元年度範囲 練習問題4: ある試行を行ったとき、事象Aが起こる確率が0.3、事象Bが起こる確率が0.5で、AとBが同時に起こる
- 令和元年度範囲 練習問題6: バブルソートで要素数5の配列を昇順に整列する場合、最悪の場合に必要な要素の交換回数はどれか。
テクノロジ系の他の問題
- 令和元年度範囲 練習問題6: バブルソートで要素数5の配列を昇順に整列する場合、最悪の場合に必要な要素の交換回数はどれか。
- 令和元年度範囲 練習問題7: 連結リスト（リンクリスト）の特徴として、適切なものはどれか。
- 令和元年度範囲 練習問題8: 深さ優先探索（DFS）で木構造を走査する方法のうち、行きがけ順（先行順、preorder）の走査順序
- 令和元年度範囲 練習問題9: クイックソートの時間計算量について、適切な記述はどれか。
- 令和元年度範囲 練習問題10: DRAM（Dynamic RAM）の特徴として、適切なものはどれか。
アプリで弱点分析つきの演習ができます