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

数制转换

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

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

栈

先进后出.

image.png

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

二叉树

image.png

先序遍历	根	左	右	2 7 1 6 5 3 8 9 4
中序遍历	左	根	右	1 7 5 6 3 2 8 4 9
后序遍历	左	右	根	1 5 3 6 7 4 9 8 2

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

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

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

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

二叉树的性质

1. 二叉树第层上至多有个节点.
2. 深度为的二叉树至多有个节点, 至少有个节点.
3. 二叉树中, 叶子节点个数为, 度为2的节点个数为, 则.
   • 推广: K叉树中, 叶子节点个数为, 度为K的节点个数为, 则

完全二叉树和满二叉树

image.png

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

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

1. 满二叉树 完全二叉树
2. 在满二叉树的最下层上, 从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树.
3. 完全二叉树上, 若一个节点没有左孩子, 则他一定没有右孩子.
4. 有个节点的完全二叉树深度为

哈夫曼树

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

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

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

堆

image.png

• 堆总是一棵完全二叉树.
• 堆中某个节点的值总是不大于或不小于其父节点的值.

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

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

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

排序算法

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

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

希尔排序图解:

image.png

图论算法

• 最小生成树
  • Kruskal: 按边权排序, 每次取最小.
  • Prim: 每个点出边按边权排序, 取链接不同连通块最小
• 最短路
  • Floyd
  • Dijkstra
  • SPFA
• 拓扑排序

计算机中数的表示

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

image.png

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

image.png

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

(CCF式)队列及循环队列

操作	队列	循环队列
入队	tail++	tail = (tail + 1) % (n + 1)
出队	head++	head = (head + 1) % (n + 1)
队满		head == (tail + 1) % (n + 1)