CSP 初赛数据结构与算法复习

17 October 2019 | duanyll | Tags: 数据结构

数制转换

K进制转10进制: 按权展开, 小数点左边第$i$位的权为$K^{i-1}$, 右边第$i$位的权为$K^{-i}$.

10进制转K进制: 整数部分除K取余, 小数部分乘K取整.

先进后出.

进栈序列$1, 2, \cdots, n$对应的出栈序列总数: Catalan 数

已知中序遍历和另外两种之一可以唯一确定二叉树, 已知先序遍历和后序遍历不能唯一确定二叉树.

中缀表达式转换为前缀后缀表达式就是求表达式树的先序后序遍历的过程.

n个点可以构造的不同二叉树种类数: Catalan 数

二叉树的数组表示法: 参考线段树的写法.

二叉树第$i$层上至多有$2^{i-1}$个节点.
深度为$k$的二叉树至多有$2^k-1$个节点, 至少有$k$个节点.
二叉树中, 叶子节点个数为$n_0$, 度为2的节点个数为$n_2$, 则$n_0 = n_2 + 1$.
- 推广: K叉树中, 叶子节点个数为$n_0$, 度为K的节点个数为$n_k$, 则
\[n_0 = \sum((k-1)n_k)+1\]

满二叉树: 深度为$k$, 有$2^k-1$个节点, 每一层都爆满.

完全二叉树: 除了最下层, 其他每层都饱满, 最下层的结点都集中在该层最左边的若干位置上.

原则: 变长编码, 前缀互不相同.

构造方法: 每次选数量最少的两个节点合并(合并果子).

哈夫曼树是带权路径长度最短的二叉树.

STL中, 可以用以下函数维护一个位于数组上的堆.

make_heap(first, last, cmp);
push_heap(first, last, cmp);
pop_heap(first, last, cmp);
sort_heap(first, last, cmp);

向堆中插入元素时, 先将新元素插入堆的尾部, 然后将新元素依次与他的父亲节点交换直到满足堆的性质; 删除堆顶元素时, 将堆顶和堆的最后一个元素交换, 移除堆尾, 然后将堆顶向下调整直到满足堆的性质.

比较排序算法时间复杂度下限$O(n\log n)$

算法	复杂度	额外空间	稳定性	说明
插入排序	$O(n^2)$	否	是	原数据基本有序时较快
选择排序	$O(n^2)$	否	否	选出最小的一个数与第一个的数交换; 在剩下的数再找最小的与第二个的数交换…
归并排序	$O(n\log n)$	$O(n)$	是	可以用来求逆序对
冒泡排序	$O(n^2)$	否	是	原数据基本有序时较快
希尔排序	$O(n^{1.5})$	否	否	把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多; 原数据基本有序时较快
快速排序	$O(n\log n)$	否	否	不加随机化容易被卡
堆排序	$O(n\log n$$	否	否
桶排序	$O(n)$	$O(a)$	是
基数排序	$O(nm\log r)$	$O(r)$	是

希尔排序图解:

原码: 首位为符号位, 其余为真值.

反码: 首位为符号位, 正数所有位和原码一样, 负数除了符号位和原码一样, 其他位相反.

补码: 相反数等于取反加1, 0的表示只有一种, 加法自然溢出就能处理正负数.