平成31年度 春期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム三つのスタックA，B，Cのいずれの初期状態も[1，2，3]であるとき，再帰的に定義された関数f( )を呼び出して終了した後のBの状態はどれか。ここで，スタックが[a1，a2，…，an-1]の状態のときanをpushした後のスタックの状態は[a1，a2，…，an-1，an]で表す。 f(){ Aが空ならば{ 何もしない。 } そうでない場合{ Aからpopした値をCにpushする。 f()を呼び出す。 Cからpopした値をBにpushする。 } }
出典：平成31年度 春期 基本情報技術者試験 午前 問6
- ア[1，2，3，1，2，3]
- イ[1，2，3，3，2，1]
- ウ[3，2，1，1，2，3]
- エ[3，2，1，3，2，1]
正解：ア
解説
f()はAが空になるまで再帰呼び出しを繰り返し，その過程でAの要素（3，2，1の順）をすべてCへ移します。再帰から戻る際に，各呼び出しの最後でCの一番上の値をBへpushするので，戻る順序（内側の呼出しから先に戻る）によりCから1，2，3の順でBへ積まれます。その結果，Bは元の[1，2，3]の上に，同じ並びの[1，2，3]が積み増しされた形になります。
選択肢ごとの解説
- ア正しい。Aの中身を一旦Cへ移し，再帰から戻りながらCからBへ移すことで，Bには元の[1，2，3]の上に同じ並びの[1，2，3]が積み増しされます。
- イ誤り。[1，2，3，3，2，1]はAの要素を移した順のまま逆転させずにBへ積んだ誤りで，再帰から戻る順序を反映していません。
- ウ誤り。[3，2，1，1，2，3]はBの初期状態の並びまで書き換えてしまった誤りで，Bの下側3要素は初期状態のまま変化しません。
- エ誤り。[3，2，1，3，2，1]はAとCの要素の移動順序を取り違えた誤りです。