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

初赛复习

news 2025/9/16 21:04:09

重要知识点

以下是一些卡特兰数 $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） 等。