令和7年度 春期 応用情報技術者試験 午前 問5

解説

入力順が A，B，C に固定され，各データについて push と pop を1回ずつ行える場合，出力順序の総数は n＝3 のカタラン数 C₃＝5 通りです。実際に列挙すると ABC，ACB，BAC，BCA，CBA の5通りで，CAB は「C を出した後に A を B より先に出す」ことになりスタックの後入れ先出しの性質に反するため実現できません。

選択肢ごとの解説

• ア誤り。3 通りとするのは，ABC，BAC，CBA のように一部の順序しか数え上げていない場合の値です。
• イ誤り。4 通りとするのは，実現可能な5通りのうち ACB や BCA などを数え落とした場合の値です。
• ウ正しい。ABC，ACB，BAC，BCA，CBA の 5 通りです。
• エ誤り。6 通りは3個の順列 3!＝6 をそのまま数えた値で，スタックでは実現できない CAB を含んでしまっています。