基本情報技術者平成31年春期 午前問6

午前問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する。
 }
}
  • [1,2,3,1,2,3]
  • [1,2,3,3,2,1]
  • [3,2,1,1,2,3]
  • [3,2,1,3,2,1]

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

スタックは後入れ先出しのデータ構造で、"pop"と"push"の2つの命令によってデータを操作します。
pop
スタックからデータを取り出す
push
スタックにデータを追加する
再帰関数f()の処理に伴う、各スタックの状態の変化をトレースします。

<プログラム開始>
A[1,2,3] B[1,2,3] C[1,2,3]

〔f() 呼び出し1回目〕
Aからpopした値をCにpushする。Aから一番右の"3"が取り出され、Cの一番右に追加される(以下、取出位置と追加位置は同様)。
A[1,2] B[1,2,3] C[1,2,3,3]

〔f() 呼び出し2回目〕
Aからpopした"2"をCにpushする。
A[1] B[1,2,3] C[1,2,3,3,2]

〔f() 呼び出し3回目〕
Aからpopした"1"をCにpushする。
A[] B[1,2,3] C[1,2,3,3,2,1]

〔f() 呼び出し4回目〕
Aが空なので何もしない

〔f() 呼び出し3回目の続き〕
Cからpopした"1"をBにpushする。
A[] B[1,2,3,1] C[1,2,3,3,2]
//f() 3回目終了

〔f() 呼び出し2回目の続き〕
Cからpopした"2"をBにpushする。
A[] B[1,2,3,1,2] C[1,2,3,3]
//f() 2回目終了

〔f() 呼び出し1回目の続き〕
Cからpopした"3"をBにpushする。
A[] B[1,2,3,1,2,3] C[1,2,3]
//f() 1回目終了

<プログラム終了>

関数f()が終了した後のBの状態は[1,2,3,1,2,3]になっています。したがって「ア」が正解です。
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop