FE SUBJECT B
基本情報技術者 科目Bの問題解説
問題
昇順配列 a={1,3,3,5,8,13,21} に対して、次の手続 lowerBoundScore(a, 6) を実行したときの戻り値はどれか。
○整数型: lowerBoundScore(整数型の配列: a, 整数型: key)
整数型: left ← 1, right ← aの要素数 ＋ 1, mid
while (left ＜ right)
mid ← (left ＋ right) ÷ 2 の商
if (a[mid] ＜ key)
left ← mid ＋ 1
else
right ← mid
endif
endwhile
if (left ≦ aの要素数)
return left × 10 ＋ a[left]
else
return 0
endif- ア 48
- イ 58
- ウ 68
- エ 0
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：58
正解：58
lowerBound は「key以上になる最初の位置」を二分探索で探す。最初は left=1, right=8 で、mid=4 の a[4]=5 は6未満なので left=5 になる。次に mid=6 の13は6以上なので right=6、最後に mid=5 の8も6以上なので right=5 となり、left=5で止まる。戻り値は left×10+a[left] なので 5×10+8=58。
48は mid=4 の途中値を答えにしてしまった場合、68は right=6 の途中状態を最終位置と誤読した場合に出やすい。0は key が全要素より大きい場合だけで、今回は a[5]=8 が見つかる。
境界探索では、見つけたいのは key そのものではなく「条件を初めて満たす位置」。left と right が一致した時点の left を最後に使う。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。