問 題
平均探索回数に関する次の記述の㋐ ㋑ ㋒に当てはまるものの組合せとして最も妥当なのはどれか。
「互いに値が異なる n 個のデータが昇順に整列された表があり、この表から目的のデータを探し出すことを考える。まずこの表をデータ数が m 個ごとのブロックに分割し、各ブロックの最後尾のデータのみを線形探索することによって、目的のデータが存在するブロックを探し出す。次に，そのブロック内を線形探索して目的のデータを探し出す。
いま n は m の倍数であるとし、目的のデータは必ず表の中に存在するものとする。また m は十分に大きい数であり、 n は m に対して十分に大きい数であるとする。探索対象の要素数が十分に大きい場合線形探索における平均探索回数は、その要素数の 1/2 となることを考慮すると、目的のデータが存在するブロックを探し出すための線形探索における平均探索回数は㋐ である。
そのブロック内で目的のデータを探し出すためにブロック内の先頭から線形探索すると、その平均探索回数は㋑ である。したがって全体の平均探索回数は ㋒ である。」
正解 (5)
解 説
㋐ですが
データ総数 n により、当然平均探索数は変わるはずです。よって n が含まれない 選択肢 1~3 は明らかに誤りです。
そして、m は十分に大きいとあるため、目的のデータが存在するブロックにおいて、目的データを探すために必要な探索数は、問題文より要素数の半分です。すなわち、m/2 が平均探索数とわかります。
以上より、正解は 5 です。
コメント