前言

从10月1日开始，经过一个星期多一点的时间，算是先把王道的《数据结构》的一轮复习完成了，主要是针对书上的基本概念过了一遍，同时做了部分的选择题。但是第一遍过的时候只是把自己原先就会的过了一遍，有一些难得知识点暂时先搁置了，打算之后再集中理解，下面大概总结一下各章的情况。

第一章——绪论

• 目前来看第一章还是最简单的一章，除了一些数据结构得基本概念外（这些应该就不会考），唯一的考点就是计算时间复杂度了。但是时间复杂度也是得多练，要把对数类型的复杂度计算吃透，掌握通用的计算方式。

第二章——线性表

• 从第二章开始就是重点了，线性表是后面好几章的基础，顺序存储与链式储存也不是难点，我的感觉应该会是在链表的插入与删除的算法语句上出考点，其次就是顺序与链式的比较。
• 对于考纲上提到的一元多项式的表示方法，这个第三章中才提及到。

第三章——栈和队列

• 这一章不仅是重点，也是难点，其中栈和队列也是之后几章算法实现中经常会用到的关键的数据结构，例如栈经常用于递归，队列经常用于广度/层次遍历。
• 先说栈，对于栈的一些基本操作和判断（进出顺序）其实还是比较简单的，不过遗留了一个共享栈。
• 其次是队列，队列里从循环队列开始，难度就开始上来了，但是只要一些基础的判断条件和公式运用的熟练，对结构理解深刻，也还是ok的，不过这一节遗留了双端队列。
• 第三小节是栈和队列的应用，例如考纲中提到的一元多项式的表示方法和基本运算，以及栈的各种应用和递归，由于这一节算法比较多，当时不知为何看的比较头大，也有可能是状态不好，就跳过了，算是遗留的重要的一节，之后再补回来。
• 第四小节在考纲中是单独的一章出现的——数组与广义表：
  
  北交大考纲：
  （1）掌握数组在以行为主和以列为主的存储结构中的地址计算方法；
  （2）掌握矩阵压缩存储时的下标变换方法，了解以三元组表示稀疏矩阵的方法；
  （3）理解广义表的定义及其存储结构，理解广义表的头尾和子表两种分析方法。
  
• 其中特殊矩阵的存储是很重要的一个知识点，选择题应该会是必出，要掌握各种特殊矩阵（上、下三角，对称，三对角，稀疏矩阵）与一维数组之间的转换，由于公式多（分上下行列），最好是理解了自己推，然而以三元组表示稀疏矩阵的方法在王道的数据结构中提及的并不详细，之后还要再详细复习。
• 还有就是广义表的知识，在王道的数据结构里根本没有提及！ 这个知识点还要去看严蔚敏的数据结构才行，也算是一个遗留知识点。

第四章——串

• 串这一章的内容比较少，其存储结构和基本操作也没有太大的难度。
• 重点在第二节模式匹配上。其中BF算法较为简单，也好实现，主要就是KMP算法了，可以说是数据结构中理解难度最大的算法之一（其实我觉得可以把之一去了 ）。不过考纲中也说了是理解KMP，所以直接考其算法的概率很低，主要还是掌握NEXT函数和改进NEXT函数的定义和计算，这个一般会出一些选择题，但是当时也没有仔细复习，算是一个遗留知识点。

第五章——树

• 终于来到树了，数据结构中最常考的数据结构之一——树 。理解难度和算法难度上都比较大。出的题目有选择也会有大题。
• 二叉树性质的考查以及一些节点的计算就不说了，选择题经常考，难度中规中矩，理解好公式就行。
• 二叉树的先中后遍历，树、森林的转化以及线索二叉树理解上都不是很难，也还ok。但是遗漏了一个并查集，主要大纲上也没提到，之后再说吧。
• 树的存储结构这块没啥说的，三种，理解其区别就行。
• 最后就是平衡二叉树和哈夫曼编码了。个人觉得哈夫曼编码是比较简单的，练几道题就熟悉了，平衡二叉树的判定也不难，难就难在平衡二叉树不平衡时的调整，这块我还没有复习好，算一个遗留知识点。

第六章——图

• 到了最复杂的数据结构了——图。图的基础概念就要比其他的数据结构多好多，不过耐心一些还是可以理解过来的，其次是处处结构，邻接矩阵和邻接表法都好理解，主要是十字链表和邻接多重表理解起来有些难度，这里算我的遗留知识点。
• 关于dfs和bfs，理解上也不难，但是害怕出算法，dfs要递归，bfs要队列，不管是手敲还是手写难度上都是比较大的，这一块有些虚。dfs一般为暴力穷举题居多，bfs一般为最优解题居多。
• 图的应用是这一章的重点也是难点，也是我最恶心的一节 ，最小生成树理解不难（普利姆和克鲁斯卡尔），最短路径就有些难度了，而且算法也是特别复杂，这算是我的一个遗留知识点；拓扑排序ok，关键路径没有仔细复习，算我的遗留知识点。

第七章——查找

• 顺序、折半、分块理解起来都不难，就是算法虚。
• 散列也不难，做几道题就熟悉了。
• 其中B-树是一个遗留的知识点，因为初学也没有学这一块，之后再补。

第八章——排序

• 这一章排序太多，纯记算法肯定不行，理解位住。
• 要熟悉每种算法的特征（适用情况，时间复杂度，稳定性），以及和其他算法的区别。
• 其中堆排和基数排序是遗留的知识点。
• 外部排序看的不扎实，错的题比较多，要对败者树、置换-算则排序以及最佳归并树（虚段计算）再做复习。

仔细一看，第一遍复习的漏洞还是挺多的 ，课后题我基本上只是先做了选择，好多的算法应用都没有做，这点才是最虚的，所以还得至少再复习一遍才行。