平成24年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズムA，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。
出典：平成24年度 春期 応用情報技術者試験 午前 問6
- ア3
- イ4
- ウ5
- エ6
正解：ウ
解説
3つのデータをスタックに1回ずつ挿入・取出しする場合に得られる出力順序のパターン数は，スタック可能な順列の数（カタラン数）で表され，n＝3のときC₃＝5通りです。具体的にはABC，ACB，BAC，BCA，CBAの5通りが可能です（CABは不可能）。
選択肢ごとの解説
- ア誤り。3通りでは可能な出力順序をすべて数え切れていません。
- イ誤り。4通りでも実際に可能な5通りに満たない数です。
- ウ正しい。スタックによる並べ替え可能な順列数はカタラン数C₃＝5通りです。
- エ誤り。6通りは3個の要素の全順列数（3！）であり，スタックでは実現不可能なCABを含んでしまいます。