平成28年度春期 応用情報技術者試験 午前 問5

正解：ウ

AI解説

スタックはLIFO(後入れ先出し)構造である。A、B、Cの順に到着するデータをそれぞれ1回pushし1回popするとき、可能な出力列を数え上げる。ABC、ACB、BAC、BCA、CBAの5通りが可能で、CABだけが不可能なので、答えは5通り(ウ)である。CABが不可能なのは、Cを最初に出力するにはA、Bがスタックに積まれている必要があり、その時点で上にあるBより先に下のAを取り出せないためである。 ア: 3通りは数え漏れによる誤りである。 イ: 4通りは数え漏れによる誤りである。 ウ: 正解。3要素の全順列6通りのうちCABのみ実現不可能で、5通りとなる。 エ: 6通りは全順列が可能とした誤りで、スタックのLIFO制約によりCABは実現できない。 💡 n個の入力に対するスタックの可能な出力順序数はカタラン数C(2n,n)/(n+1)で、n=3なら5となる。「最初にCが出たら、残りは必ず後入れのBが先」のように、逆順制約で不可能パターンを見つけるのが実戦的。