平成28年度 春期 応用情報技術者試験 午前 問5
テクノロジ／アルゴリズムA，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。
出典：平成28年度 春期 応用情報技術者試験 午前 問5
- ア3
- イ4
- ウ5
- エ6
正解：ウ
解説
A，B，Cの順に入力し，各データについてスタックへの挿入と取出しを1回ずつ行う場合に得られる出力順列は，スタックの後入れ先出し（LIFO）性質を保つ並びだけです。全6通りの順列のうちCBAを先頭にできない等の制約があり，実現可能な出力順は5通りになります（ABC，ACB，BAC，BCA，CBA）。CABだけがスタック操作では実現不可能です。
選択肢ごとの解説
- ア誤り。3通りは制約が強すぎる数え方で，実際に実現可能な順序数より少なすぎます。
- イ誤り。4通りも実際に実現可能な出力順序の数より少なく数え漏れがあります。
- ウ正しい。ABC，ACB，BAC，BCA，CBAの5通りが実現可能であり，CABだけが不可能です。
- エ誤り。6通りは順列の総数であり，スタックのLIFO制約でCABが実現できないことを考慮していません。