基本情報技術者試験「探索」の問題
次の手続 kthSmallest は、配列 arr を選択ソートと同じ要領で小さい順に k 回だけ確定させ、k 番目に小さい値を返す。arr = {37, 12, 58, 29, 41, 8, 23}（要素数 7、添字は 1 から）、k = 3 を与えて実行したとき、戻り値はどれか。
○整数型: kthSmallest(整数型の配列: arr, 整数型: k)
整数型: i, j, minPos, tmp
for (i を 1 から k まで 1 ずつ増やす)
minPos ← i
for (j を i + 1 から arrの要素数 まで 1 ずつ増やす)
if (arr[j] < arr[minPos])
minPos ← j
endif
endfor
tmp ← arr[i]
arr[i] ← arr[minPos]
arr[minPos] ← tmp
endfor
return arr[k]ア23
イ290
ウ12
エ58
正解
ア．23
外側ループを k=3 回だけ回し、各回で未確定部分の最小値を先頭へ送る。確定する値は 8（1 番目）、12（2 番目）、23（3 番目）であり arr[3]=23 を返すため アが正しい。
?選択肢ごとの解説
ア ○外側ループを k=3 回だけ回し、各回で未確定部分の最小値を先頭へ送る。確定する値は 8（1 番目）、12（2 番目）、23（3 番目）であり arr[3]=23 を返すため アが正しい。
イ ×3 番目に小さい値 23 ではなく桁を膨らませた 290 とした、配列値と無関係な数値を選んだ誤りである。
ウ ×最小値（1 番目に小さい値）8 ではなく 2 番目の 12 を答えており、k の数え方を 1 つずらした誤りである。
エ ×最大値に近い 58 を選んでおり、k 番目に『大きい』値と取り違えた誤りである。
✎くわしく
k 番目に小さい値は、選択ソートを途中で打ち切る部分整列で求められる。全体を整列せずとも先頭 k 個を確定させれば足りる点が効率上の核心である。k の数え始め（1 番目＝最小）を正しく把握する必要がある。
✓本番での押さえどころ
試験のコツ
小さい順に並べた仮想列を書き、左から k 番目を読む。全整列は不要と理解する。
覚え方
『小さい順に k 個だけ確定させれば答え』と覚える。
よくある誤り
k を 0 始まりと誤って 1 つずれる、または k 番目に大きい値と取り違えるミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0069