第２種情報処理技術者試験
1995年度 ＝ 平成7年度・秋期
午前
問13
1,000人の個人顧客名を昇順に並べた名簿がある。来客名による検索を線形探索法を用いて行う。平均比較回数の見積りとして正しい組合せはどれか。
名簿中に来客名がないとき、ないことが分かるまでの平均比較回数
名簿中に来客名があるとき、その顧客名に到達するまでの平均比較回数
ア
333
333
イ
500
333
ウ
500
500
エ
1,000
500
オ
1,000
1,000
解答
ウ
解説
線形探索法
（
linear search
）は、ある特定のキー値をもつ要素を、配列や表の先頭要素から順に探索するアルゴリズムです。
名簿中に来客名がないとき、ないことが分かるまでの平均比較回数
具体的な比較回数を考えてみます。名簿は、個人顧客名の昇順に並べられていますので、探索の過程で、来客名より大きい顧客名に出会ったときに探索が失敗終了します。
先頭要素が来客名より大きい場合は、比較は1回
2番目の要素が客名より大きい場合は、比較は2回
3番目の要素が客名より大きい場合は、比較は3回
:
末尾の要素が客名より大きい、比較は1,000回
といった具合で1,000通りが存在する。したがって、比較回数の平均は、
(1 + 2 + 3 + …+ 1,000) / 1,000
であり、
500
となります。
名簿中に来客名があるとき、その顧客名に到達するまでの平均比較回数
具体的な比較回数を考えてみます。名簿は、個人顧客名の昇順に並べられていますので、探索の過程で、来客名と等しい顧客名に出会ったときに探索が成功終了します。
先頭要素が来客名と等しい場合は、比較は1回
2番目の要素が来客名と等しい場合は、比較は2回
3番目の要素が来客名と等しい場合は、比較は3回
:
末尾の要素が来客名と等しい場合は、比較は1,000回
といった具合で1,000通りが存在する。したがって、比較回数の平均は、
(1 + 2 + 3 + …+ 1,000) / 1,000
であり、
500
となります。
