408 | 【2015年】计算机统考真题 自用回顾知识点整理

选择题

T2：卡特兰数

        前序序列和中序序列的关系相当于以 前序序列为入栈次序，以中序序列为出栈次序。

        转化为“以序列a, b, c, d为入栈次序，则出栈序列的个数为多少”。

        

• 1、出栈序列
  • 一个栈(无穷大)的进栈序列为1，2，3，…，n，出栈顺序种数h(n)
• 2、括号匹配
  • 由1对括号，可以组成一种合法括号序列：()。
  • 由2对括号，可以组成两种合法括号序列：()()、(())。
  • 由n对括号组成的合法括号序列一共有多少种？h(n)
• 3、生成二叉树
  • n个节点构成的二叉树，共有多少种情形？h(n)
• 4、满二叉树个数
  • n+1个叶子的满二叉树个数为多少？h(n)

数据结构