午前問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する。
}
}
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] |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- ア
解説
スタック(stack)とは、最後に入力したデータが先に出力されるという特徴をもつデータ構造の一種で、このようなデータの入出力方式を「LIFO(Last In, First Out)」と呼びます。
f()にA,B,Cを当てはめると
①Aは空ではないので、Aからpopした値をCにpushする。
A[1,2,3]
B[1,2,3]
C[1,2,3]
↓
A[1,2]
B[1,2,3]
C[1,2,3,3]
②Aは空ではないので、Aからpopした値をCにpushする。
A[1,2]
B[1,2,3]
C[1,2,3,3]
↓
A[1]
B[1,2,3]
C[1,2,3,3,2]
③Aは空ではないので、Aからpopした値をCにpushする。
A[1]
B[1,2,3]
C[1,2,3,3,2]
↓
A[]
B[1,2,3]
C[1,2,3,3,2,1]
④Aは空なので、Cからpopした値をBにpushする。
A[]
B[1,2,3]
C[1,2,3,3,2,1]
↓
A[]
B[1,2,3,1]
C[1,2,3,3,2]
⑤Aは空なので、Cからpopした値をBにpushする。
A[]
B[1,2,3,1]
C[1,2,3,3,2]
↓
A[]
B[1,2,3,1,2]
C[1,2,3,3]
⑥Aは空なので、Cからpopした値をBにpushする。
A[]
B[1,2,3,1,2]
C[1,2,3,3]
↓
A[]
B[1,2,3,1,2,3]
C[1,2,3]
よってBの状態は[1,2,3,1,2,3]となります。
f()にA,B,Cを当てはめると
①Aは空ではないので、Aからpopした値をCにpushする。
A[1,2,3]
B[1,2,3]
C[1,2,3]
↓
A[1,2]
B[1,2,3]
C[1,2,3,3]
②Aは空ではないので、Aからpopした値をCにpushする。
A[1,2]
B[1,2,3]
C[1,2,3,3]
↓
A[1]
B[1,2,3]
C[1,2,3,3,2]
③Aは空ではないので、Aからpopした値をCにpushする。
A[1]
B[1,2,3]
C[1,2,3,3,2]
↓
A[]
B[1,2,3]
C[1,2,3,3,2,1]
④Aは空なので、Cからpopした値をBにpushする。
A[]
B[1,2,3]
C[1,2,3,3,2,1]
↓
A[]
B[1,2,3,1]
C[1,2,3,3,2]
⑤Aは空なので、Cからpopした値をBにpushする。
A[]
B[1,2,3,1]
C[1,2,3,3,2]
↓
A[]
B[1,2,3,1,2]
C[1,2,3,3]
⑥Aは空なので、Cからpopした値をBにpushする。
A[]
B[1,2,3,1,2]
C[1,2,3,3]
↓
A[]
B[1,2,3,1,2,3]
C[1,2,3]
よってBの状態は[1,2,3,1,2,3]となります。