令和7年度春期 応用情報技術者試験 午前 問5

正解：ウ

AI解説

スタックを用いて要素を並べ替えるとき、n個の要素に対して実現可能な出力順列の総数はカタラン数Cnで与えられる。n=3のときC3=5であり、A,B,Cの3データを1回ずつ挿入・取出しする場合の出力順序は5通りとなる。 ア: 3通りは、実現可能な出力順序を一部しか数え上げていない過小な値である。 イ: 4通りも同様に、数え漏れがある過小な値である。 ウ: 正しい。カタラン数C3=5が、スタックを介して得られる出力順列の総数である。 エ: 6通りは、スタックの制約を考慮せずに単純に3個の要素の順列総数(3!=6)を答えてしまった誤答であり、スタックの後入れ先出し制約により実現不可能な順序が含まれてしまう。 💡 スタックによる並べ替え可能な順列数はカタラン数(1,2,5,14,42,…)として知られ、要素数の階乗より少なくなる点に注意する。