本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成31年度 春期 基本情報技術者試験問題と解説

問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]


正解


解説

スタックはLIFO (後入れ先出し) により置換するアルゴリズムである。
popはスタックからデータを取り出す操作、pushはスタックにデータを入れる操作である。
三つのスタックは以下のように遷移していく。

0-0 初期状態
 A[1, 2, 3] B[1, 2, 3] C[1, 2, 3]

0-1 f()を呼び出す。

@-1 Aからpopした値をCにpushする。
 A[1, 2, 3] B[1, 2, 3] C[1, 2, 3, 3]
@-2 f()を呼び出す。
  A-1 Aからpopした値をCにpushする。
   A[1, 2] B[1, 2, 3] C[1, 2, 3, 3, 2]
  A-2 f()を呼び出す。
    B-1 Aからpopした値をCにpushする。
     A[1] B[1, 2, 3] C[1, 2, 3, 3, 2, 1]
    B-2 f()を呼び出す。
      Aが空なので何もしない
    B-3 Cからpopした値をBにpushする。
     A[] B[1, 2, 3, 1] C[1, 2, 3, 3, 2, 1]
  A-3 Cからpopした値をBにpushする。
   A[] B[1, 2, 3, 1, 2] C[1, 2, 3, 3, 2]
@-3 Cからpopした値をBにpushする。
 A[] B[1, 2, 3, 1, 2, 3] C[1, 2, 3, 3]

よって、スタックBの状態は、[1, 2, 3, 1, 2, 3] となる。

問5 目次 問7