令和7年度 春期 午前 問5

✓ これが正解ウ5

解説

挿入と取出しで作れる出力順は全部で5通りです。

スタックは後入れ先出しの構造で、要素は積んだ順序と逆に取り出されます。設問は 3 個の要素をそれぞれ 1 回ずつ挿入と取出しをする場合に、取り出される順が何通りできるかを尋ねています。並びが実現可能かどうかは、同じ数の挿入と取出しからなる 3＋3 個の操作列で、途中で取出しの数が挿入の数を上回らない列に対応するかで判定できます。この個数は 3 個のときのカタラン数 5 で与えられ、実現可能な並びは A・B・C、A・C・B、B・A・C、B・C・A、C・B・A の 5 通りです。3 要素の全順列 6 通りのうち、C・A・B は最初に C を出した時点で B と A がスタックに残るため、A を B より先に出せず実現できません。

ほかの選択肢はなぜ違うのか

• ア3：3 を選ぶ肢は、実現可能な並びをかなり数え落としています。最初に A を出す並び、B を出す並び、C を出す並びのそれぞれから異なる並びが作れるので、3 通りにはとどまりません。
• イ4：4 を選ぶ肢は、条件を満たす並びを 1 つ数え落としています。実現不可能な C・A・B を除いた 5 通りが正しく、途中に挟まる並びの一つを取りこぼしています。
• エ6：6 を選ぶ肢は、3 要素の全順列である 6 通りをそのまま数えています。しかし後入れ先出しの制約により C・A・B は作れないので、この 1 通り分を差し引く必要があります。