問題プレビューID: b83ba4a5基本情報技術者試験 午前免除試験 2021年7月25日

問 8
基本情報技術者試験 午前免除試験 2021年7月25日

三つのスタック A,B,C のいずれの初期状態も [1, 2, 3] であるとき,再帰的に定義された関数 f() を呼び出して終了した後の B の状態はどれか。ここで,スタックが [a1,a2,⋯ ,an−1][a_1, a_2, \cdots, a_{n-1}] の状態のときに ana_n を push した後のスタックの状態は [a1,a2,⋯ ,an−1,an][a_1, a_2, \cdots, a_{n-1}, a_n] で表す。

f() {
  A が空ならば {
    何もしない。
  }
  そうでない場合 {
    A から pop した値を C に push する。
    f() を呼び出す。
    C から pop した値を B に push する。
  }
}
解説

正解は「ア」です。

初期状態の A,B,C はいずれも [1, 2, 3] で,スタックの末尾が先頭(pop される側)です。関数 f()f() は,A が空になるまで「A から pop して C に push し,再帰呼出しした後に C から pop して B に push する」ことを繰り返します。

  1. A=[1, 2, 3] から 3 を pop し,C=[1, 2, 3, 3] にしてから再帰呼出しへ進みます。
  2. A=[1, 2] から 2 を pop し,C=[1, 2, 3, 3, 2] にしてから再帰呼出しへ進みます。
  3. A=[1] から 1 を pop し,C=[1, 2, 3, 3, 2, 1] にしてから再帰呼出しへ進みます。
  4. A が空なので何もせずに戻ります。C から 1 を pop して B に push し,B=[1, 2, 3, 1] になります。
  5. 呼出し元に戻り,C から 2 を pop して B に push し,B=[1, 2, 3, 1, 2] になります。
  6. さらに呼出し元に戻り,C から 3 を pop して B に push し,B=[1, 2, 3, 1, 2, 3] になります。

したがって B の状態は [1, 2, 3, 1, 2, 3] となり,「ア」が正解です。

  • イ・ウ・エ: いずれも pop と push の順序を誤った値であり,正しい B の状態とは一致しません。

関連問題

本文が同じ・似ている問題を表示しています