三つのスタックＡ、Ｂ、Ｃのいずれの初期状態も [1、2、3] であるとき、再帰的に定義された関数 f() を呼び出して終了した後のＢの状態はどれか。ここで、スタックが
[a1、a2、...、an-1] の状態のときにanを pushした後のスタックの状態は [a1、a2、...、an-1、an]で表す。
f(){
Ａが空ならば{
何もしない。
｝
そうでない場合{
Ａからpopした値をＣに pushする。
f() を呼び出す。
Ｃからpopした値をＢに 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]
ア
スタックはLIFO (後入れ先出し) により置換するアルゴリズムである。
popはスタックからデータを取り出す操作、pushはスタックにデータを入れる操作である。
三つのスタックは以下のように遷移していく。
0-0 初期状態
Ａ[1, 2, 3] Ｂ[1, 2, 3] Ｃ[1, 2, 3]
0-1 f()を呼び出す。
①-1 Ａからpopした値をＣにpushする。
Ａ[1, 2, 3] Ｂ[1, 2, 3] Ｃ[1, 2, 3, 3]
①-2 f()を呼び出す。
②-1 Ａからpopした値をＣにpushする。
Ａ[1, 2] Ｂ[1, 2, 3] Ｃ[1, 2, 3, 3, 2]
②-2 f()を呼び出す。
③-1 Ａからpopした値をＣにpushする。
Ａ[1] Ｂ[1, 2, 3] Ｃ[1, 2, 3, 3, 2, 1]
③-2 f()を呼び出す。
Ａが空なので何もしない
③-3 Ｃからpopした値をＢにpushする。
Ａ[] Ｂ[1, 2, 3, 1] Ｃ[1, 2, 3, 3, 2, 1]
②-3 Ｃからpopした値をＢにpushする。
Ａ[] Ｂ[1, 2, 3, 1, 2] Ｃ[1, 2, 3, 3, 2]
①-3 Ｃからpopした値をＢにpushする。
Ａ[] Ｂ[1, 2, 3, 1, 2, 3] Ｃ[1, 2, 3, 3]
よって、スタックＢの状態は、[1, 2, 3, 1, 2, 3] となる。
| 問５ | 目次 | 問７ |