• 首页
  • 教育理念
  • 文章专题
  • 编程教程
    • – Scratch编程教程
    • – AppInventor编程
    • – Python编程教程
    • – NOIP信息学奥赛
    • – C/C++编程教程
    • – JS编程教程
  • 少儿编程学院
    • – 在线课程
    • – 学院名师
    • – 动态资讯
  • 少儿编程社区
    • – 在线编程
    • – 编程作品
    • – 专题创作
  • 更多
    • – APP客户端
    • – 关于我们
    • – 寻求合作
    • – 少儿编程联盟
投稿 登录 注册
  • 首页
  • 文章专题
  • 教育理念
  • 编程教程
  • 少儿编程学院
  • 微信公众号
  • APP客户端
少儿编程学院
少儿编程教育-微信公众号
首页 › 编程教程 › NOIP信息学奥赛 › 正文
NOIP信息学奥赛信息竞赛编程竞赛

NOIP初赛复习(三)栈与卡特兰数

主编主编 NOIP信息学奥赛 2017-08-24 9,724 32

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

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

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

 

喜欢 (32)
打赏
  • 打赏支付宝扫一扫
  • 打赏微信扫一扫
微博 微信 QQ

微信扫一扫,分享到朋友圈

微信公众号
编程少年Scratch实物积木
少儿编程教育-微信公众号
上一篇

NOIP初赛复习(二)逻辑运算

下一篇

NOIP初赛复习(四)二叉树的遍历和性质

猜你喜欢

  • 第二届全国中学生网络安全竞赛即将在西安电子科大举办!

    第二届全国中学生网络安全竞赛即将在西安电子科大举办!

  • 严查违规竞赛,29项全国中小学生竞赛活动名单公布!

    严查违规竞赛,29项全国中小学生竞赛活动名单公布!

  • 教育部:2019年度中小学生全国性竞赛活动名单公示

    教育部:2019年度中小学生全国性竞赛活动名单公示

  • 第二十届全国中小学电脑制作活动通知

    第二十届全国中小学电脑制作活动通知

  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

  • STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

    STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

主编
主编官方

我真的不是自黑!

中国STEAM教育2018年度风云榜

微信公众号

推荐专题

  • 有趣的少儿编程游戏推荐

    查看专题
  • 国外优秀的少儿编程教育

    查看专题
  • S科学-T技术-E工程-M数学

    查看专题

猜你喜欢

  • 你家孩子玩的APP,可能是这个10岁小男孩开发的!
    2017-05-28

    你家孩子玩的APP,可能是这个10岁小男孩开发的!

  • 孩子长大不做程序员为什么要学编程?我来告诉你!

    孩子长大不做程序员为什么要学编程?我来告诉你!

    2017-07-12
  • 17岁编程少年自学Java编程,做公益不惧流言削发明志

    17岁编程少年自学Java编程,做公益不惧流言削发明志

    2018-12-05
  • 信奥指南 | 信息学进阶在 2018 年怎么安排?

    信奥指南 | 信息学进阶在 2018 年怎么安排?

    2018-03-02
  • 爸爸教我学Python编程-第11课-操作符和运算顺序

    爸爸教我学Python编程-第11课-操作符和运算顺序

    2018-01-28

热门文章

    暂无文章

热门标签

鲨鱼公园高考改革高考加分青橙创客青少儿防疫阿部和广错误观念逻辑思维费米科学贝尔科教谷歌教育计算机科学计算机思维解决方案西瓜创客

微信公众号

热门文章 热门标签 年度归档 少儿编程教育联盟

Copyright © 2021 少儿编程教育网 粤ICP备17057575号 · Designed by shaoerbc.org

大家都在搜

  • Scratch教程
  • scratch2下载
  • Scratch编程
  • 编程思维
  • 信息学奥赛
  • STEM教育
  • 编程一小时
  • 自主招生
  • 少儿编程竞赛

关注我们的公众号

微信公众号