数据结构考前一天

线性表：矩阵，链表（单链表必考）

栈和队列：出入判断，括号匹配，中缀转后缀

字符串数组：模式匹配next，nextval数组，数组寻址，三角矩阵对应一维数组k，

二叉树：二叉链表，求叶子数量，求深度，左右转换，前中后遍历，森林与二叉树转化，哈夫曼树，哈夫曼编码，

图：DFS，BFS，邻接矩阵，邻接表（EdgeNode,VertexNode），最小生成树（prime加点，kruskal加边），最短路径（dijkstra，floyd考试直接找路径），AOV网拓扑排序路径，AOE网（v事件，a活动）事件：最短时间（大），最长时间（倒过来小），活动：最短（起点的最早），最长时间（尾的最长减自身），

查找：折半（二分法）r，l，m，二叉排序树（删除节点，都有的话找右子树中序第一），平衡二叉树（排序树左右深度不超过1，更正为平衡二叉树）ASL（USUCC加框，深度减1），散列表（开放寻址，拉链法）计算ASL（usucc是每个到空的距离，空本身为1），

排序：直接插入（本身有序，插入仍有序），

希尔排序（增量序列画圈），

冒泡（两两交换），简单选择（寻最小，放到最前面），

快速排序（选轴，右→左小于轴，左到右大于轴，不能就补轴，轴确定后再两边继续排），

堆排序（建立大or小堆，堆顶与最后叶子互换，删除叶子，继续建堆），

二路归并排序（奇数自己一组，下次加入旁边的）