[知识总结] 【考研记录一】数据结构一轮复习完毕

前言

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

第一章——绪论

北交大考纲：
（1）掌握相关的基本概念，如数据结构、逻辑结构、存储结构、数据类型、 抽象数据类型等；
（2）掌握算法设计的原则，掌握计算语句频度和估算算法时间复杂度和空 间复杂度的方法；
（3）了解使用类 C 语言描述算法的方法。

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

第二章——线性表

北交大考纲：
（1）掌握线性表的逻辑结构和存储结构；
（2）掌握线性表在顺序结构和链式结构上实现基本操作的方法；
（3）理解线性表两种存储结构的不同特点及其适用场合， 会针对需求选用合适的存储结构解决实际问题；
（4）了解一元多项式的表示方法和基本运算的实现方法。

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

第三章——栈和队列

北交大考纲：
（1）了解栈和队列的特点；
（2）掌握在两种存储结构上栈的基本操作的实现；
（3）掌握栈的各种应用，理解递归算法执行过程中栈状态的变化过程；
（4）掌握循环队列和链队列的基本运算；
（5）会应用队列结构解决实际问题。

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

第四章——串

北交大考纲：
（1）掌握串的基本运算的定义，了解利用基本运算来实现串的其它运算的方法；
（2）了解在顺序存储结构和在堆存储结构以及块链存储结构上实现串的各种操作的方法；
（3）理解 KMP 算法，掌握 NEXT 函数和改进 NEXT 函数的定义和计算。

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

第五章——树

北交大考纲：
（1）熟练掌握二叉树的结构特点和性质，掌握二叉树各种存储结构及 构建方法；
（2）掌握按先序、中序、后序和层次次序遍历二叉树的算法，理解二叉树的线索化实质和方法；
（3）利用二叉树的遍历求解实际问题；
（4）掌握树的各种存储结构及其特点，掌握树的各种运算的实现算法；
（5）掌握建立最优二叉树和哈夫曼编码的方法。

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

第六章——图

北交大考纲：
（1）熟练掌握图的基本概念，会构建各种图的存储结构；
（2）掌握深度优先搜索遍历图和广度优先搜索遍历图的算法；
（3）灵活运用图的遍历算法求解各种路径问题，包括最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。

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

第七章——查找

北交大考纲：
（1）熟练掌握各种静态查找和动态查找算法，会计算查找成功时和失败时的平均查找长度；
（2）掌握二叉排序树的建立、插入和删除过程，掌握二叉平衡树的建立和旋转平衡方法；
（3）掌握B-树的建立、插入和删除结点的过程；
（4）熟练掌握哈希表的构造方法和处理冲突的方法。

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

第八章——排序

北交大考纲：
（1）掌握各种排序算法，包括插入类、交换类、选择类、归并类排序及基数 排序；
（2）能够对各种排序方法进行比较分析，如稳定性、时间和空间性能等，了解各种排 序方法的特点和不同并灵活应用；
（3）理解外部排序的主要思想和过程。

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

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

遗留知识点：

1. 共享栈
2. 双端队列
3. 栈和队列的应用
4. KMP
5. 广义表
6. 并查集
7. 平衡二叉树的调整
8. 十字链表和邻接多重表
9. 最短路径
10. 关键路径
11. B-树
12. 堆排
13. 基数排序
14. 外部排序（败者树、置换-选择排序、最佳归并树）