基本情報技術者 2019年 春期 午前（科目A） 問06
問題文
三つのスタックA, B, Cのいずれの初期状態も[1, 2, 3]であるとき、再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか．ここで、スタックがの状態のときにをpushした後のスタックの状態はで表す。
f(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
f()を呼び出す。
Cからpopした値をBにpushする。
}
}
選択肢
ア：[1, 2, 3, 1, 2, 3]（正解）
イ：[1, 2, 3, 3, 2, 1]
ウ：[3, 2, 1, 1, 2, 3]
エ：[3, 2, 1, 3, 2, 1]
🔒 解説は解答すると表示されます
スタックの再帰操作と順序変換【午前解説】
正解の理由
正解は ア です。処理の流れは次の通りです。初期状態は各スタックとも [1, 2, 3]（右端がtop）です。f()は
- Aが空でない限りAからtopを取り出してCにpushする（A→Cで要素が逆順に積まれる）
- 再帰から戻ってきたらCからtopを取り出してBにpushする（C→Bで再び逆順になる） 結果としてAの要素は二回反転され、元の順序のままBの末尾に追加されます。これを実際に追うとBは [1,2,3,1,2,3] になります。
解法ステップ
- 初期状態を確認：A=[1,2,3]（top=3）、B=[1,2,3]、C=[1,2,3]。
- f()の1回目（最上位呼び出し）：Aから3をpop、Cにpush → A=[1,2], C=[1,2,3,3]。
- f()呼び出し（2回目）：Aから2をpop、Cにpush → A=[1], C=[1,2,3,3,2]。
- f()呼び出し（3回目）：Aから1をpop、Cにpush → A=[], C=[1,2,3,3,2,1]。
- 次の再帰呼び出しでAが空なので何もしないで戻る。
- 帰りがけにCから順にpopしてBにpush：まず1 → B=[1,2,3,1]、次に2 → B=[1,2,3,1,2]、最後に3 → B=[1,2,3,1,2,3]。
- 最終的にBは [1,2,3,1,2,3]（選択肢ア）になる。
選択肢別の誤答解説
- ア: 正解。上記の通りAの要素が元の順序でBの末尾に追加されるため一致する。
- イ: [1,2,3,3,2,1] — これはAの要素をCに移したまま（反転した順序のまま）Bに移したと誤解したケース。C→Bで反転が戻るため誤り。
- ウ: [3,2,1,1,2,3] — 初期Bの順序自体を入れ替えたと考える誤り。Bの初期内容は変わらず、Aの要素が末尾に追加される。
- エ: [3,2,1,3,2,1] — AとBの両方が逆順になったとする誤解。実際にAの要素は最終的に元の順序で追加されるので不一致。
よくある誤解
- 「push/pop の方向を左右逆に考える」：配列表記で右端がtopであることを忘れ、順序を逆に解釈するミス。
- 「C の初期内容を無視してAの順序が変わると考える」：Cに既に要素があっても、Aの要素はCの末尾に順に追加されるだけでBへの追加順は同じです。
- 「再帰を単なるループと同じに扱う」：再帰では「入る時の操作（A→C）」と「戻る時の操作（C→B）」が分離している点を見落とすことがあります。
補足コラム
このパターンは「再帰で要素を一時的なスタックに移す→戻りで別のスタックに移す」という典型的な二段階のスタック移動です。二度の「反転」が起きるため、最終的には元の順序が復元されます。アルゴリズム的に見ると、Aの内容をBの末尾に追加する（順序は保たれる）操作と等価です。スタック表記（左底・右頂）と操作の順序を明確にする練習が重要です。
FAQ
Q1: Cの初期要素があると結果に影響しますか？
A1: Cの初期要素はそのまま残り、Aから追加された要素はCの末尾に続きます。Bに移すときはその末尾から順に取り出すため、Cの初期要素とAの要素の相対順序は保たれます。
A1: Cの初期要素はそのまま残り、Aから追加された要素はCの末尾に続きます。Bに移すときはその末尾から順に取り出すため、Cの初期要素とAの要素の相対順序は保たれます。
Q2: 再帰を使わずループで実装しても同じですか？
A2: はい。再帰は処理の順序を自然に表現しているだけで、同等のループ（AからCへ全て移し、次にCからBへ全て移す）で同様の結果が得られます。
A2: はい。再帰は処理の順序を自然に表現しているだけで、同等のループ（AからCへ全て移し、次にCからBへ全て移す）で同様の結果が得られます。
Q3: 表記が [1,2,3] のとき 3 が top だとどう確認する？
A3: 問題にある「a_n を push した後の状態は [..., a_n]」という記述から、右端が後から積まれる（top）ことが明示されています。
A3: 問題にある「a_n を push した後の状態は [..., a_n]」という記述から、右端が後から積まれる（top）ことが明示されています。
関連キーワード: スタック、再帰、LIFO、push、pop、データ構造、アルゴリズム、再帰的呼び出し、スタック操作、順序復元
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！