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

正解：ウ

AI解説

3個のデータをスタックに通す際に得られる出力順列の数は、カタラン数C_nで求められ、n＝3のときC_3＝5通りとなる(公式:C_n＝(2n)!／{(n+1)!・n!})。全順列6通り(3!)のうち、スタックの後入れ先出し(LIFO)の制約によって実現不可能な1通り(この場合はB, C, Aの順)が除かれ、5通りに絞られる。 ア: 全順列6通りより少ない数だが、正しいカタラン数の値ではない。 イ: 同様に候補となりうる数だが、n＝3のカタラン数の値ではない。 ウ: 正しい。3個のデータに対するスタックの挿入・取出しで実現可能な出力順序の数はカタラン数C_3＝5通りである。 エ: 3個のデータの全順列の数(3！＝6通り)であり、スタックのLIFO制約によって実現できない順序が1通り存在するため、実際に出力可能な順序数はこれより少ない。 💡 スタックを介した出力順列の総数はカタラン数で求まる、という定石を覚えておくと計算が速い。n＝1で1通り、n＝2で2通り、n＝3で5通りと押さえておくとよい。