問題プレビューID: 14f58785基本情報技術者試験 午前免除試験 2013年12月15日

問 6
基本情報技術者試験 午前免除試験 2013年12月15日

昇順に整列された n 個のデータが格納されている配列 A がある。流れ図は,2 分探索法を用いて配列 A からデータ x を探し出す処理を表している。a,b に入れる操作の適切な組合せはどれか。ここで,除算の結果は小数点以下が切り捨てられる。

解説

正解は「ウ」です。

2 分探索法では,探索範囲を表す下限 lo と上限 hi の中央 k の値 A(k) を x と比較し,探索範囲を半分に絞り込みます。

  • A(k) < x のとき(x は A(k) より大きい),x は中央より後ろ(上位側)にあるので,探索範囲の下限を k の次に上げます。すなわち lo ← k+1 です。流れ図ではこの分岐が a に入ります。
  • A(k) > x のとき(x は A(k) より小さい),x は中央より前(下位側)にあるので,探索範囲の上限を k の前に下げます。すなわち hi ← k−1 です。流れ図ではこの分岐が b に入ります。

したがって,a = k+1→lo,b = k−1→hi となる「ウ」が正解です。

  • ア: a と b を入れ替え,更に lo と hi の割当ても逆にした組合せで,誤りです。
  • イ: 上下限の更新方向が逆になっており,探索範囲を狭める向きが逆になるため誤りです。
  • エ: a で hi を,b で lo を更新していますが,大小関係から考えて上下限の対応が逆で,誤りです。

関連問題

本文が同じ・似ている問題を表示しています