三つのスタックA,B,Cのいずれの初期状態も[1, 2, 3]であるとき,再帰的に定義された関数f( )を呼び出して終了した後のBの状態はどれか。ここで,スタックが,[a₁, a₂, …, aₙ₋₁]の状態のときにaₙをpushした後のスタックの状態は[a₁, a₂, …, aₙ₋₁, aₙ]で表す。
f( ){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
f( )を呼び出す。
Cからpushした値をBにpopする。
}
}
- [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からpopした値をCにpushする。
- Aからpopした値をCにpushする。
- Aからpopした値をCにpushする。
- Cからpushした値をBにpopする。
- Cからpushした値をBにpopする。
- Cからpushした値をBにpopする。
1〜3の処理で、スタックCが[1, 2, 3, 3, 2, 1]となり、
4〜6の処理で、スタックBが[1, 2, 3, 1, 2, 3]となります。
参考情報
分野・分類
分野 | テクノロジ系 |
大分類 | 基礎理論 |
中分類 | アルゴリズムとプログラミング |
小分類 | アルゴリズム |
出題歴
- FE 平成31年度春期 問6