令和3年度 春期 応用情報技術者試験 午前 問5
テクノロジ／アルゴリズムA，B，C の順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。
出典：令和3年度 春期 応用情報技術者試験 午前 問5
- ア3
- イ4
- ウ5
- エ6
正解：ウ
解説
3個のデータをスタックに1回ずつ挿入・取出しするときの出力順序の総数は，カタラン数 C3＝5 通りです。具体的には ABC，ACB，BAC，BCA，CBA の5通りが可能で，CAB（Cを最初に出すにはA，Bを積む必要があり，その後BよりAを先に出すことはできない）だけが不可能です。
選択肢ごとの解説
- ア誤り。3通りでは可能な出力順序を数え漏らしています。ABC，ACB，BAC，BCA，CBA の5通りが可能です。
- イ誤り。4通りでは BCA などの可能な順序を数え漏らしています。
- ウ正しい。3要素の全順列6通りのうち CAB だけが実現不可能なので，6−1＝5通りです。
- エ誤り。6通りは3要素の全順列の数です。CAB はスタックでは実現できないので誤りです。