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

数制转换

K进制转10进制: 按权展开, 小数点左边第位的权为, 右边第位的权为.

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

先进后出.

image.png

进栈序列对应的出栈序列总数: Catalan 数

image.png

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

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

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

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

image.png

满二叉树: 深度为, 有个节点, 每一层都爆满.

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

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

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

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

image.png

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

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

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

比较排序算法时间复杂度下限

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