题13 题目 Q:3 个不同元素依次进栈, 能得到 ( ) 种不同的出栈序列 A. 4 B. 5 C. 6 D. 7 分析 A:这是个结论 栈的数学性质:当 个不同元素进栈时,出栈元素不同排列的个数为 。 这个公式称为卡特兰数(Catalan)公式 也就是 解 B 当 个不同元素进栈时,出栈序列的个数为 考题中给出的 值不会很大,可以根据栈的特点,若 已经出栈,则 前面的尚未出栈的元素一定逆置有序地出栈,因此可采用例举方法。 如 依次进栈的出栈序列有 , 。 另外,在一些考题中可能会问符合某个特定条件的出栈序列有多少种,比如此题中的问以 开头的出栈序列有几种,这种类型的题目一般都使用穷举法。
