基本情報技術者試験 平成31年度 春期 午前 問6
スタックとキューのデータ構造についての問題。
--------------------------
平成31年度 春期 午前 問6
三つのスタック A,B,C のいずれの初期状態も [1,2,3] であるとき、再帰的に定義された関数 f( ) を呼び出して終了した後の B の状態はどれか。ここで、スタックが [a1,a2,a3] の状態の時に a4 を push した後のスタックの状態は [a1,a2,a3,a4] で表す。
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]
--------------------------
解説
説明する単語が多そうな問題。
まず、スタックについて。
データ構造の考え方でキューとスタックがある。簡単な概念図が上の通り。
きったない図で申し訳ない。
スタックにデータを入れることを push、データを取り出すことを pop と呼ぶ。
図の形の通り、後に入れた（push した）データほど先に取り出される（pop される）。この方式は LIFO（Last In First Out）とも呼ぶ。
最後に入れたものを、最初に取り出す。積み上がっていく宿題みたいな構造。
一方のキューはスーパーのレジ行列の様なデータ構造。
キューにデータを入れることをエンキュー（Enqueue）、データを取り出すことをデキュー（Dequeue）と呼ぶ。先に入れたデータほど先に取り出される。
こちらの方式は FIFO（First In First Out）とも呼ぶ。
再帰的に定義された関数とは関数 f( ) の処理の中で自分と同じ関数 f( ) を呼び出す様な処理をする関数。再帰的に呼び出せるための条件がいくつか存在するが、それはまた別の機会に。
自分自身を呼び出すときは関数の最初に戻るのではなく、元の関数とは別の関数を新たに処理することに注意。便宜的に、呼び出した順に f( )_1, f( )_2 と末尾に数字をつけて説明する。
まず f( )_1 が実行される。
この時点では A は空でないので、"そうでない場合" の処理をする。
A から pop した値を C に push なので、
A が [1,2,3] → [1,2]、C が [1,2,3] → [1,2,3,3] となる。
次の行で関数 f( ) が再帰的に呼び出されるので、f( )_2 が実行される。
この時 f( )_1 は f( )_2 の終了待ち状態となり、f( )_2 が終わり次第、次の行の処理をする。
f( )_2 の実行時点でも A は空でないので、A から pop した値が C に pushされる。
なので、A が [1,2] → [1]、C が [1,2,3,3] → [1,2,3,3,2]となる。
次の行で f( )_3 が実行され、f( )_2 は f( )_3 の終了待ちとなる。
f( )_3 の実行時点でも A は空でないので、A から pop した値が C に push される。
なので、A が [1] → 空、C が [1,2,3,3,2] → [1,2,3,3,2,1] となる。
次の行で f( )_4 が実行され、f( )_3 は f( )_4 の終了待ちとなる。
f( )_4 の実行時点で A は空なので、"何もしない"の処理のみで f( )_4 は終了する。
f( )_4 が終了したので f( )_3に戻り、次の行の処理である C から pop して B に push を実行して f( )_3 が終了する。
なので、C が [1,2,3,3,2,1] → [1,2,3,3,2]、B が [1,2,3] → [1,2,3,1] となる。
f( )_2 に戻り、次の行の処理である C から pop して B に push を実行する。
なので、C が [1,2,3,3,2] → [1,2,3,3]、B が [1,2,3,1] → [1,2,3,1,2] となる。
f( )_1 に戻り、次の行の処理である C から pop して B に push を実行する。
なので、C が [1,2,3,3] → [1,2,3]、B が [1,2,3,1,2] → [1,2,3,1,2,3]となる。
ここでようやく関数の実行が終わるので、選択肢アの [1,2,3,1,2,3] が正解。
ちなみに、このように再帰的に関数を呼び出す動きの管理もスタックを使うと実現できる。
スタックにそれまで実行していた関数における終了待ち状態の情報をスタックに積み重ねていけばいい。
f( )_1 の終了待ち状態の情報が最初にスタックに push されたので、最後に pop されるのは f( )_1 となる。
前後の問題はこちら。
