栈是数据结构中一种常用的结构。可以想象成一个没有盖的圆桶。只有两个操作:入栈和出栈。

概念:入栈、出栈、栈顶。入栈和出栈都是针对栈顶元素操作的。具体如下图:

NOIP初赛复习(三)栈与卡特兰数-少儿编程教育网

题型:比较集中,具体体现在历年题目中。

统计:设栈S的初始状态为空,元素a, b, c, d, e 依次入栈,以下出栈序列有多少种可能( )。

答案为:

NOIP初赛复习(三)栈与卡特兰数-少儿编程教育网

 

代入n=5,答案为42。

 

卡特兰数

说到Catalan数,就不得不提及Catalan序列,Catalan序列是一个整数序列,其:

通项公式是

NOIP初赛复习(三)栈与卡特兰数-少儿编程教育网

 

 

 

递推公式是

C(n) = C(1)*C(n-1) + C(2)*C(n-2) + ... +C(n-1)C(1),n>=2

我们从中取出的Cn就叫做第n个Catalan数,前几个Catalan数如下:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900,2674440, 9694845, 35357670, …

咋看之下没什么特别的,但是Catalan数却是许多计数问题的最终形式。

Catalan数在组合计算中的应用

1、矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,有几种括号化的方案?

2、一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?

3、n个节点构成的二叉树,共有多少种情形?

4、求一个凸多边形区域划分成三角形区域的方法数?

NOIP初赛复习(三)栈与卡特兰数-少儿编程教育网

5、在圆上选择2n个点,将这些点成对链接起来使得所得到的n条线段不相交,一共有多少种方法?(下图供参考)

NOIP初赛复习(三)栈与卡特兰数-少儿编程教育网

6、n*n的方格地图中,从一个角到另外一个角,不跨越对角线的路径数为h(n).例如, 4×4方格地图中的路径有:

NOIP初赛复习(三)栈与卡特兰数-少儿编程教育网

7、n层的阶梯切割为n个矩形的切法数也是。如下图所示:

NOIP初赛复习(三)栈与卡特兰数-少儿编程教育网

8、有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?

9、甲乙两人比赛乒乓球,最后结果为20∶20,问比赛过程中甲始终领先乙的计分情形的种数。

10、2n个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?


往年真题

1. 元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3,那么第5个出栈的可能是( )。

A.R1    B.R2      C.R4    D.R5

2. 有六个元素FEDCBA 从左至右依次顺序进栈,在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列?

A.EDCFAB      B.DECABF      C.CDFEBA     D.BCDAEF

3. 设栈S的初始状态为空,元素a,b,c,d,e,f依次入栈,出栈顺序为b,d,c,f,e,a那么栈容量至少应该是( )。

A.6           B.5          C.4            D.3            E.2

4. 地面上有标号为A、B、C的3根细柱, 在A柱上方有10个直径相同中间有孔的圆盘, 从上到下次编号为1, 2, 3, ……,将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。如果B柱上的操作记录为:“进,进,出,进,进,出,出,进,进,出,进,出,出”。那么在C柱上从下到上的盘子的编号为( ).(模拟结果)

A. 2 4 36 5 7   B. 2 4 1 2 5 7  C. 2 4 3 1 7 6     D. 2 4 3 6 7 5 E. 2 1 4 3 7 5

5. 某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站状态为空,从这一时刻开始的出入记录为:“进,出,进,进,进,出,出,进,进,进,出,出”。假设车辆入站的顺序为1,2,3,……,则车辆出站的顺序为( )。(模拟结果)

A. 1, 2,3, 4, 5    B. 1, 2, 4, 5, 7    C. 1, 4, 3, 7, 6     D. 1, 4, 3, 7, 2    E. 1, 4, 3, 7, 5

6. 设栈S的初始状态为空,元素a, b, c, d, e 依次入栈,以下出栈序列不可能出现的有( )。 (这种情况逐个排除,但是如果问你有多少种可能呢?参考catalan数)

A. a, b,c, e, d      B. b, c, a, e, d     C.a, e, c, b, d      D. d, c, e, b, a


栈与卡特兰数往年真题参考答案:
1.ACD 2.C 3.D 4.D 5.C 6.C