Important
- P117 归并排序
- 第八章最后一节
以上不考
- 不会考定义
- 重点考时间复杂度的计算或者频度的计算（准备这个就行）
- 课后习题第一题到第四题都属于上述知识点，都可以去看看
- 特别是程序设计、算法题、算法填空、算法问答、手写代码都可能出现这一章的东西
- 栈的后进先出、队列的先进先出特点的题目可能出现解答题
- 已知队尾、位标和长度求队头（即三者之间的关系）、求余运算的使用
- 单链表、双链表的构建与计算
- 算法题变化大，建议参照 Anyview，从基本操作开始到应用变化都很大
- 会有时间复杂度的要求
- P86 注意写序列的题目，本页第一道大题让写出每种排序的每一趟结果，这种题目很常见
- 本章算法题不多，考经典排序算法的写法或者一些变换（排序时直接插入排序时换哨位等）
- 考点较少
- 注意和后面章节的查找问题放在一起考，可能会考平均查找长度
- 根据设计好的哈希表求
- 线性法画哈希表，求 ASL
- 删除某一元素、插入某一元素的变化
- 后面的查找：二叉查找树
- 可能的算法题
- 各种基本操作的实现
- 个别变换的应用（例如习题 6）
- P124 第三题有序表按照折半查找写出查找某一元素的情况，求 ASL
- 会让写每一趟的排序结果，例如同一页的第四题冒泡、第五题快排、第六第七题归并排序
- 广义表：P124 第八题求表头表尾，第九题求深度长度，第十题画存储结构（这题是去年还是前年的题）
- 完全手写代码的题目也可能会来源于本章（还有是第二张）
- 解答题多，算法题也多
- 二叉树的应用、二叉查找树、平衡二叉树，重点多
- 书本解答题第一题：考察二叉树性质，第二题说简单（没看书），第三题说是写先序中序后序遍历，注意这类题目的拔高题，让你还原二叉树
- 堆的知识点：大顶堆、小顶堆的判断，给出删除最大/最小堆后的堆，考察筛选操作
- 第六题：写初始堆和每一趟的堆
- 第九题：考察二叉查找树，构造以及计算 ASL
- 第十题：平衡二叉树的构造
- 算法：Anyview 里面有很多，复习的时候与第二张同等地位对待
- P188 第三题：按照孩子兄弟法把树转换为二叉树或者将二叉树还原为树/森林
- 第四题：关于树的存储结构，考双亲孩子表示方法、树的遍历
- 遍历是重点，会让写遍历序列或者考察应用
- 孩子兄弟方法两个指针容易发生变化
- 并查集的优化，如何提高并查集的效率（有两种方法，课本上）
- B 树：考算法的可能性几乎为 0，特别是插入删除。查找还有点可能。解答题上参考第七题：B 树插入新节点发生分裂。第八（构造三阶 B 树，插入两个节点，超出边界会分裂；删除关键字少时会发生节点合并）、第九题画出 B 树（高阶 B 树，例如五阶）
- 重点：树的遍历和应用
- 必有一道解答题、一道算法题（可能是填空或者问答），往年来看
- P224 第一题，第一问考察邻接数组的存储结构，第二问求所有可能的拓扑序列，所有一定要按照某种顺序去构造，不容易漏掉
- 第二题（重点）反过来告诉存储结构（图 8.3.1），第二问遍历，第三问从某点开始的广度、深度优先序列
- P225 第三题，普利姆、克鲁斯卡尔求最小生成树
- 第四题，用迪杰斯克拉算法求最短路径
- 注意看作业系统讲过的关键算法，特别是图的遍历、深度、广度算法；利用深度广度进行应用（P206 算法 8.1.4 和算法 8.1.5）