| 第２種情報処理技術者試験 |
1996年度 ＝ 平成8年度・春期 |
午前 |
問15 |
n個の要素をもつ配列中の値と探索すべきデータXを順次比較し、配列中の値にデータXが存在した場合“有”を表示する。このとき、添字n + 1の場所に探索すベきデータXを入れておく。
| 添字
| 1
| 2
| 3
| …
| i
| …
| n
| n+1
|
| 値
| a1
| a2
| a3
| …
| ai
| …
| an
| X
|
この線形探索アルゴリズム中の に入れるべき適切な条件はどれか。
ステップ１ 添字iに1を入れる。
ステップ２ であればステップ５へとぶ。
ステップ３ 添字iに1を加算する。
ステップ４ ステップ２へとぶ。
ステップ５ 添字iがn以下であれば“有”を表示する
ステップ６ 終了
| ア i≧n
| イ i≠n
| ウ i＜n
| エ X＝ai
| オ X≠ai
|
エ
問題で示されているアルゴリズムは、番兵を用いた線形探索（linear search）です。線形探索は、ある特定のキー値をもつ要素を、配列や表の先頭要素から順に探索するアルゴリズムです。
ここでは、以下の配列を例に解説します。
┌─┬─┬─┬─┬─┬─┐
│５│４│７│３│６│２│
└─┴─┴─┴─┴─┴─┘
線形探索における繰返しの判定は、
- 目的とする値と等しい値に出会う。
- 配列や表の末尾に到達した。
のいずれかが成立することです。
ここで、目的とする値を配列の末尾に加えてみましょう。たとえば7を探索する場合は、配列の末尾に7を加えます。
┌─┬─┬─┬─┬─┬─┬─┐
│５│４│７│３│６│２│７│
└─┴─┴─┴─┴─┴─┴─┘
そうすると、探索の対象に目的とする値が存在することが保証されますので、
この探索における繰返しの判定は、
が成立することに変更できます。すなわち、判定条件が半分になり、高速化が図れます。
設問は、この判断の条件『現在着目している値aiが、目的とする値Xと等しいかどうか』ですから、エのX ＝ aiが正解です。
