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

正解：ウ

AI解説

スタックは LIFO(後入れ先出し)構造であり、A, B, C の順に入力しながら任意のタイミングで取り出すと、得られる出力順は3個の場合5通りである。全順列6通りのうち C, A, B の順だけは実現できない。C を最初に出力するには A, B, C を全部積む必要があり、その後は必ず B, A の順でしか取り出せないからである。 ア: 3通りは数え漏れである。ABC, ACB, BAC, BCA, CBA が可能である。 イ: 4通りも数え漏れである。 ウ: 正解。実現可能な出力順は5通り(不可能なのは CAB のみ)である。 エ: 6通りは全順列を可能とみなした誤りで、CAB が不可能なことを見落としている。 💡 n 個のスタック出力順の総数はカタラン数で、n=3 なら5、n=4 なら14。試験では「どの順が不可能か」を具体的に考えると確実である。