修了試験 2023-01-22実施分 基本情報技術者試験 問9

解説

正解は2です。 この探索は、まずブロックの最後尾だけを調べてブロックを特定し、次にそのブロック内を調べる2段階の線形探索です。 線形探索で目的の要素が等しい確率で現れるとき、平均比較回数は要素数の約半分になります。 【計算】 ブロックの数はn/m個です。 最後尾データの線形探索で、目的のブロックを見つけるまでの平均比較回数は(n/m)÷2＝n/2mです。 1ブロックにはm個のデータがあります。 ブロック内の線形探索の平均比較回数はm/2です。 合計の平均比較回数はm/2＋n/2mです。 【選択肢別解説】 1：× m＋n/mは、両方の段階で最後まで調べた場合の最大比較回数です。 平均はそれぞれ半分になります。 2：○ ブロック選択の平均n/2mとブロック内探索の平均m/2を足した式であり、平均比較回数を表します。 3：× n/mはブロック選択段階の最大比較回数だけです。 平均は半分であり、ブロック内の探索回数も足す必要があります。 4：× n/2mはブロック選択段階の平均比較回数だけです。 ブロック内探索の平均m/2が抜けています。 【ポイント】 要素数Nの線形探索の平均比較回数はN/2と覚えておきます。 2段階の探索は、各段階の平均を足し合わせて求めます。