第2種情報処理技術者試験 1996年度 = 平成8年度・春期 午前 問15

 n個の要素をもつ配列中の値と探索すべきデータXを順次比較し、配列中の値にデータXが存在した場合“有”を表示する。このとき、添字n + 1の場所に探索すベきデータXを入れておく。

 添字  1 2 3 i n n+1
a1 a2 a3 ai an X

 この線形探索アルゴリズム中の      に入れるべき適切な条件はどれか。
  ステップ1  添字iに1を入れる。
  ステップ2       であればステップ5へとぶ。
  ステップ3  添字iに1を加算する。
  ステップ4  ステップ2へとぶ。
  ステップ5  添字iがn以下であれば“有”を表示する
  ステップ6  終了

 ア i≧n  イ i≠n  ウ i<n  エ X=ai  オ X≠ai

解答

 エ

解説

 問題で示されているアルゴリズムは、番兵を用いた線形探索(linear search)です。線形探索は、ある特定のキー値をもつ要素を、配列や表の先頭要素から順に探索するアルゴリズムです。
 ここでは、以下の配列を例に解説します。

   ┌─┬─┬─┬─┬─┬─┐    │5│4│7│3│6│2│    └─┴─┴─┴─┴─┴─┘

 線形探索における繰返しの判定は、 のいずれかが成立することです。
 ここで、目的とする値を配列の末尾に加えてみましょう。たとえば7を探索する場合は、配列の末尾に7を加えます。

   ┌─┬─┬─┬─┬─┬─┬─┐    │5│4│7│3│6│2││    └─┴─┴─┴─┴─┴─┴─┘

 そうすると、探索の対象に目的とする値が存在することが保証されますので、 この探索における繰返しの判定は、 が成立することに変更できます。すなわち、判定条件が半分になり、高速化が図れます。
 設問は、この判断の条件『現在着目している値aiが、目的とする値Xと等しいかどうか』ですから、X = aiが正解です。


BohYoh.comトップページへ