FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：昇順配列 a={1,2,4,4,4,7,9} に対して、次の…
問題
昇順配列 a={1,2,4,4,4,7,9} に対して、次の手続 upperScore(a, 4) を実行したときの戻り値はどれか。
○整数型: upperScore(整数型の配列: 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
return left × 10 ＋ a[left － 1]- ア 54
- イ 64（正解）
- ウ 67
- エ 70
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：64
upperScore は key より大きい最初の位置を探します。4以下なら left を進めるので、4が3個続く範囲をすべて飛ばします。最終的に left=6、left-1=5 となり、a[5]=4です。戻り値は6×10+4=64となります。
54は最後の4の位置5を left と勘違いした値、67は a[left]=7 を足してしまった場合、70はkeyの直後の値だけに注目した場合に出やすい値です。
lowerBound と upperBound の違いは比較演算子です。a[mid]＜key ならkey以上、a[mid]≦key ならkeyより大きい位置を探します。
仕組みと計算量：この手続は探索範囲を [left, right) の半開区間として扱い、a[mid]≦key なら左端を mid+1 に、そうでなければ右端を mid に縮めます。区間は毎回ほぼ半分になるので比較回数は O(log n) で、要素数7のこの配列では3回の反復で確定します。最終的な left は「key を超える最初の位置」を必ず指し、a[left-1] は key 以下の末尾要素になります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。