当前位置：首页 > news >正文

初赛复习

news 2026/6/14 7:20:48

重要知识点

以下是一些卡特兰数 \(C_n\) 的应用：

二叉树计数
- \(n\) 个结点的不同形态的二叉树的数量是卡特兰数 \(C_n\)。
括号匹配
- \(n\) 对括号的有效组合数。
栈操作序列（出栈顺序）
- \(n\) 个元素的出栈顺序数。
凸多边形的三角划分
- \(n + 2\) 条边的凸多边形划分成三角形的方法数。
Dyck路径（格路问题）
- 从 \((0,0)\) 到 \((2n,0)\)，每次向右上或右下移动一步，且不越过 \(x\) 轴的路径数。
满二叉树计数
- \(n + 1\) 个叶子的满二叉树的数量。
表达式加括号
- \(n + 1\) 个因子的乘法表达式加括号的方式数，例如：\(4\) 个因子 \(a,b,c,d\) 有 \(5\) 种加括号方式：\((a(b(cd))),(a((bc)d)),((ab)(cd)),((a(bc))d),(((ab)c)d)\)。
棋盘不相交对角线
- \({n} \times {n}\)棋盘上放置不相交的对角线（从左上到右下）的方法数。
凸多边形划分
- \(n + 2\) 边形的顶点配对成不相交的弦的方式数。

层次遍历是按层从小到大，每一层从左到右的顺序遍历。
5 个没有区别的结点构成不同形态的二叉树的种类有多少个？
- 因为卡特兰数 \(C_n = \frac{1}{n+1} \binom{2n}{n}\) 能表示具有 \(n\) 个结点的不同二叉树的形态数，所以答案为 \(C_5 = \frac{1}{6} \binom{10}{5} = 42\)；
- 由于我比较蒟蒻，我的方法是令 \(f_{i,j,k}\) 表示 \(i\) 个点，\(j\) 层数，最后一层有 \(k\) 个点的方案数，然后慢慢转移。其实 \(5\) 个点还是能接受的。
线性表若采用链表存储结构，内存中可用存储单元的地址可以是不连续的（即不一定要求地址连续）。
- 链表不需要连续的内存空间，而是利用分散的内存块通过指针串联起来。这与数组（顺序存储结构）形成对比，数组要求连续的内存空间。
在 Linux 系统中，比较两个文件的有无不同之处的命令是 diff。
- 在 Windows 系统中应该是 fc。
断电之后仍能保存数据的（非易失性存储器）有 硬盘、固态硬盘、U盘/闪存驱动器、光盘、ROM（只读存储器） 等；易失性存储器有 RAM (可读写储存器)、Cache (高速缓存)、显存 (VRAM） 等。