基本情報技術者試験 基本情報技術者試験 平成31年度 春期 午前 午前 問6: 三つのスタック A, B, C のいずれの初期状態も [1, 2, 3] であるとき，再帰的に定義された関数 f() を呼び出して終了した後の B の状態はどれ

問題本文

三つのスタック 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]

正解

ア. [1, 2, 3, 1, 2, 3]

解説

f() は再帰呼び出しで A→C→B のデータ転送を行う。初期 A=[1,2,3] から: pop 3→push C、再帰、pop 2→push C、再帰、pop 1→push C、再帰でA空でreturn、C[1,2,3,3,2,1] から pop 1→B、戻って pop 2→B、戻って pop 3→B。B は元の [1,2,3] に 1,2,3 を順に追加して [1,2,3,1,2,3]。アが正解。

選択肢ごとの解説

• ア.B の初期 [1,2,3] に、A から経由されて取り出された 1,2,3 が順に追加される。正解。
• イ.[1,2,3,3,2,1] は C から逆順に取り出されるイメージだが、実際の手順とは異なる。
• ウ.[3,2,1,1,2,3] は B の初期状態を逆順にした想定だが、B は変更されない部分が先頭に残る。
• エ.[3,2,1,3,2,1] は両端を逆順にした誤った想定。