正答3
解説
正解は3です。
A、B、Cの順に到着するデータを、スタックを経由して出力するときの出力順序の数を問う問題です。
図は、右からA、B、Cの順に入れ、スタック上部の左の口から取り出す構造を示しています。
スタックは、後に入れたものを先に取り出すLIFO（Last In First Out）の構造です。
【計算】
各データを入れてすぐ出すことを3回繰り返すと、A、B、Cの順になります。
Aを入出力した後、B、Cを入れてCから出すと、A、C、Bの順になります。
A、Bを入れてB、Aの順に出し、Cを入出力すると、B、A、Cの順になります。
A、Bを入れてBを出し、Cを入出力してからAを出すと、B、C、Aの順になります。
A、B、Cをすべて入れてから取り出すと、C、B、Aの順になります。
C、A、Bの順は、Cを出した時点でAがBの下にあるため、Aを先に出せず実現できません。
以上より、出力順序は5通りです。
【選択肢別解説】
1：× 3通りでは、上で示した5通りの一部しか数えていません。
2：× 4通りでは1通り不足しています。
上の5通りはすべて実現できます。
3：○ 3個の並べ方6通りのうち、C、A、Bだけが実現できないので5通りです。
4：× 6通りは3個の順列の総数です。
C、A、Bはスタックでは作れないので除く必要があります。
【ポイント】
n個のデータをスタック経由で出力する順序の数はカタラン数になり、n＝3では5通りです。
「下にあるものは、上のものより先に出せない」という制約から、実現できない順序を見抜けるようにしましょう。