情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和3年度春期 午前Ⅰ 問2: A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。

問題本文

A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。

選択肢

• ア.3
• イ.4
• ウ.5
• エ.6

正解

ウ. 5

解説

A,B,Cをスタックへ各1回push/popできるとき、出力順序の総数は要素数3のカタラン数C3=5に等しい。実際にはABC,ACB,BAC,BCA,CBAの5通りが作れ、CABはCを出した後にAをBより先に出せないため不可能。よってウが正解。スタックの後入れ先出し(LIFO)の制約を具体的に列挙して数える典型問題で、式の暗記より動作の理解が重要。

選択肢ごとの解説

• ア.3通りでは不足。BAC,BCAなど途中でpop/pushを交互に行う順序を数え漏らしている。
• イ.4通りでも不足で、実際に作成可能な順序を1つ数え漏らしている。
• ウ.ABC,ACB,BAC,BCA,CBAの5通りが作成可能で、カタラン数C3=5に一致するため正しい。
• エ.6通り(3の階乗)は全順列だが、CABはスタックでは実現できず誤り。