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

問題本文

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

選択肢

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

正解

ウ. 5

解説

スタックはLIFO(後入れ先出し)で、各要素にpush/popを1回ずつ行える。A,B,Cの3要素で実現可能な出力順序の総数はカタラン数Cₙ=C(2n,n)/(n+1)で求まり、n=3ならC₃=5。実際にABC,ACB,BAC,BCA,CBAの5通りが可能で、CABはCを出した後Aを先に出せず不可能。ウが正解。スタックの順序制約はコンパイラや式評価で頻出の基礎概念。

選択肢ごとの解説

• ア.3通りでは実現可能な並びを数え落としており、カタラン数C₃=5と一致せず誤り。
• イ.4通りも数え漏れがあり、スタックで作れる順序の総数より少ないため誤り。
• ウ.カタランC₃=5でABC・ACB・BAC・BCA・CBAの5通りが可能なため正しい。
• エ.6は3要素の全順列だが、CABはスタックでは作れないため過大で誤り。