1、考研数据结构必须掌握的知识点与算法-打印版 作者： 日期：2 数据结构必须掌握的知识点与算法第一章 绪论1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出）2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求）3、算法与程序的关系：（1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。（3）一个算法若用程序设计语言来描述，则它就是一个程序。4、算法的时间复
2、杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算）第二章 线性表1、线性表的特点：（1）存在唯一的第一个元素；（这一点决定了图不是线性表）（2）存在唯一的最后一个元素；（3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表）（4）除最后一个元素外，其它均只有一个后继。2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。3、顺序表示的线性表（数组）地址计算方法：（1）一维数组，设DataType aN的首地址为A0，每一个数据（DataType类型）占m个字节，则ak的地址为：Aak
3、A0+m*k（其直接意义就是求在数据ak的前面有多少个元素，每个元素占m个字节）（2）多维数组，以三维数组为例，设DataType aMNP的首地址为A000，每一个数据（DataType类型）占m个字节，则在元素aijk的前面共有元素个数为：M*N*i+N*j+k，其其地址为：AaijkA000+m*(M*N*i+N*j+k)；4、线性表的归并排序：设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.25、掌握线性表的顺序表示法定义代码，各元素的含义；6、顺序线性表的初始化过程，可见算法2.37、顺序线性表的元素的查找。8、顺序线性表的元素的插入
4、算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.49、顺序线性表的删除元素过程，可见算法2.510、顺序线性表的归并算法，可见算法2.711、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析；12、链表中元素的查找13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.1116、链表的归并算法，可见算法2.12 17、建议了
5、解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解20、循环链表的插入、删除算法、图解21、双向链表的定义，意义22、双向链表的构造算法（其与单链表的区别是在创建时确定的）、图解23、双向链表的插入、删除算法、图解，可见算法2.18、2.1924、补充：在循环链表中，只设立一个表尾指针比只设立一个表头指针更方便些，为什么？第三章 栈和队列1、栈的顺序表示与实现2、栈的链表表示与实现3、栈的入栈、出栈操作算法4、栈的几个经典应用（迷宫、表达式求值）5、栈与递归的实现，如Hanoi塔问
6、题6、队列链式表示与实现7、链式队列的入队、出队操作算法8、循环队列的表示（顺序表示）和实现，特别注意其判满、判空方法、入队操作、出队操作的实现（特别重要，考得频率很大）9、补充：共享栈的方法与实现（即两个栈共享一个空间，他们采用栈顶相向，迎面增长的存储方式）10、补充：用两个栈来模拟一个队列的思路、算法11、补充：表达式（前缀、后缀、中缀）的表达互换，这个操作要求对栈在表达式求值中的应用相当熟练，并要求对后面的二叉树相当熟练12、补充：了解双端队列（只需了解）13、补充：链栈比顺序栈的优点与缺点14、补充：一系列元素依次入栈再出栈的顺序，经典题目为：有5个元素，其入栈次序为A、B、C、D、E
7、，以下哪种出栈的顺序是不可能的？15、补充：了解用循环链表实现队列，注意在该循环链表中只有一个头指针或一个表尾指针（只需了解）16、补充：根据给出的数学公式，写出对应的递归算法，最经典的就是用递归求阶乘。第六章 树和二叉树1、几个重要的概念：树、森林、子树、根、终端结点（叶子）、非终端结点、双亲、孩子、兄弟、堂兄弟、度、深度、有序树、无序树、二叉树、k叉树、完全二叉树、满二叉树、线索二叉树；2、二叉树的5种基本形态；3、二叉树的5个重要性质：（1）在二叉树的第i层上至多有2i1个结点（i1）；（2）深度为k的二叉树至多有2k1个结点，（k1）（3）对任何一棵二叉树T，如果其终端结点（叶子）数为
8、n0，度为2的结点数为n2，则n0=n2+1；（4）具有n个结点的完全二叉树的深度为；（5）如果对一棵有n个结点的完全二叉树（其深度为）的结点按性层序编号（从第1层到第层，每层从左到右），则对任一结点i（1in），有：（i）如果i=1，则结点i是二叉树的根，无双亲；如果i1,则其双亲Parent（i）是结点（ii）如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LChild（i）是结点2i；（iii）如果2i+1n，则结点i无右孩子；否则其右孩子RChild（i）是结点2i+1利用完全二叉树的上述性质，能处理大多数完全二叉树的计算题；4、二叉树的存储结构：（1）了解顺序存储结构，
9、只做了解；（2）链式存储结构，重要，需要掌握，后面的算法都是基于此结构；5、二叉树的遍历：（1）能对任意一棵二叉树进行手动前序、中序、后序遍历；（2）能将由前序+中序、后序+中序给出的序列还原成一棵二叉树；（3）能将一个数学表达式用中序方法将其用二叉树画出来，并能写出其前缀（波兰式）、中缀、后缀（逆波兰式）表达出来；6、二叉树的遍历递归算法（注意前、中、后序三个算法只有细微的差别），可见算法6.1，而他们的非递归算法不作要求；7、建立二叉树链表的递归算法，可见算法6.4；8、线索二叉树的存储结构图；9、能用手画出任意二叉树对应的线索二叉树（中序、后序线索）；10、线索二叉树的非递归遍历算法，可
10、见算法6.5；11、理解线索二叉树的中序线索化过程算法，可见算法6.6；12、手动写出任意森林、树的深度优先、广度优先遍历顺序；13、森林、二叉树的转换过程，能用手画出即可；14、哈夫曼树的相关概念：路径长度、带权路径长度WPL、权值；15、二叉哈夫曼树的构造过程，能用手动构造，并能将构造好的树用编码表示出来；16、了解哈夫曼树的构造算法，可见算法6.12，只需要了解，无需掌握；17、记住树的记数公式：对一棵有n个结点的有棵不同的二叉树18、补充：二叉排序树、插入、删除结点的操作（在查找一章中有详述）；19、补充：满二叉树、完全二叉树用数组存储方式，其元素、结点对应关系；20、补充：求二叉树的
11、高度（深度）算法；21、补充：将二叉树中左、右孩子交换的算法；22、补充：将用数组存储的完全二叉树转换成链式结构的算法；23、补充：对用数组存储的完全二叉树进行非递归的前序、中序、后序遍历算法；24、补充：求二叉树中叶子数、度为1的、度为2的结点数算法；25、补充：对于K叉树，其结点总数为N，求出该树的最大高度、高小高度；26、补充：构造结点数为n的k叉哈夫曼树（其所有的结点要么度为0，要么度为k），注意一般都需要增加m个权为0的结点（称为虚结点），其中如果叶子结点数目不足以构成正则的k叉树（树中只有度为k或0的结点），即不满足(n-1)MOD(k-1)=0（其中MOD是取余运算），需要添加权
12、为0的结点，添加的个数为m=k-(n-1)MOD(k-1)-1。添加的位置应该是距离根结点的最远处。假设n=10，k=3，则需要添加1个权为0的虚结点（其字母可以为空）。第七章 图1、图的几个重要概念：顶点、弧、弧尾、弧头、边、有向图、无向图、完全图、邻接点、入度、出度、度、路径、回路（环）、连通图、连通分量、强连通图、强连通分量、生成森林、关节点、重连通图、AOV-网、AOE-网；2、图的几种存储、表示方法：数组表示法（重要）、邻接表（最重要，应用最广）、逆邻接表（掌握）、十字链表（理解）、邻接多重表（了解），并能大致掌握他们各种方法表示的优缺点；3、图的两种遍历顺序：深度、广度优先，建议同
13、时掌握其算法；4、图的生成树和生成森林（只需掌握手画方法）；5、图的最小生成树的两种算法：普里姆（Prim）算法（实质是顶点优先）、克鲁斯卡尔（Kruskal）算法（实质是边优先），掌握他们的手动构造过程，了解算法；6、理解求关节点算法，可见算法7.10、7.11；7、了解拓扑排序；8、掌握由AOE-网得到关键路径的方法（手动），了解算法（7.13、7.14）；9、掌握最短路径的手动求解过程、方法（两种：迪杰斯特拉Dijkstra、弗洛伊德Floyd），了解算法；10、补充：Prim算法、Kruskal算法、Dijkstra算法、Floyd算法的时间复杂度；11、补充：了解拓扑排序算法；12、
14、补充：能将图的抽象定义，如有向图G（V，A），Vv1，v2，v3，v4，A，画成图，也能将图用抽象定义写出；13、补充：能根据图的邻接表、逆邻接表、数组表示法表示出来的图画出，亦能根据图写出其邻接表、逆邻接表、数组表示法；14、补充：了解四色定理(Four color theorem)：最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德摩尔根（Augustus De Morgan，18061871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。四色问题的内容是：“任何一张地图只用四种颜色就能使
15、具有共同边界的国家染上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”15、补充：了解离散数学中的欧拉图、哥尼斯堡七桥问题；16、补充：了解汉密尔顿图；第九章 查找1、掌握几个重要的概念：静态查找表、动态查找表、平均查找长度、二叉排序树、平衡二叉树、平衡因子、B树、B树、哈希表；2、顺序表的查找算法（9.1）及其时间复杂度的性能分析；3、折半查找（二分查找）算法（9.2）及其性能分析；4、能画出任意个数元素的二分查找过程形成的判定树；5、掌握次优二叉查找树的构造过程，能用手画出，其
16、算法只做了解要求；6、掌握索引顺序表的查找（又称分块查找）基本原理，并能分析其性能；7、能手动根据元素的顺序，构造出一棵二叉排序树；8、掌握二叉排序树的几种算法：查找算法（9.5a、9.5b）、二叉排序树的插入算法（9.6），而插入过程就是构造二叉排序树的过程；9、掌握二叉排序树的删除结点的手动过程及算法（9.7、9.8）；10、掌握二叉排序树的查找性能分析过程；11、平衡二叉树的构造过程，重点在于平衡被破坏后的调整，LL型、LR型、RR型、RL型的平衡旋转处理；12、平衡树查找的性能分析；13、B树的查找操作，了解其算法；14、B树的查找性能分析；15、B树的查找操作；16、引入哈希表的目的
17、、优点、基本原理；17、了解几种常用的哈希函数：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法；18、掌握几种常用的处理冲突的方法：开放定址法（线性探测法、伪随机数序列法）、再哈希法、链地址法、公共溢出区法；19、哈希表的查找性能分析；第十章 内部排序1、掌握几个重要的概念：排序、排序方法的稳定性（即关键字相同的经排序后原顺序会不会变化）、排序算法效率的稳定性（即排序算法效率会不会受待排序数据序列的影响而出现较大的变化）、内部排序、外部排序、堆2、直接插入排序的过程（手动分析一趟排序的过程、结果）、算法（10.1）；3、掌握折半插入排序算法（10.2）、理解2路插入排序、了解
18、表插入排序；4、希尔排序过程（手动分析一趟排序的过程、结果）、算法（10.4、10.5）；5、冒泡排序过程（手动分析一趟排序的过程、结果）、算法；6、快速排序过程（手动分析一趟排序的过程、结果）、原理、算法（10.6-8）7、快速排序性能分析；8、简单选择排序过程（手动分析一趟排序的过程、结果）、算法（10.9）；9、堆排序过程（手动分析建初始堆过程、一趟排序的过程、结果）、原理、算法（10.10-11），堆排序原理、过程、算法非常重要，是常考点；10、2路归并排序过程（手动分析一趟排序的过程、结果）、算法（10.2-4）；11、理解基数排序的原理、过程；12、掌握各种内部排序方法的比较；13、补充：各种内部排序的应用场合（这个比较难做，需要对各种排序算法非常清楚才能做到）；14、补充：冒泡排序的改进鲨鱼排序过程、原理、算法；15、补充：插入、选择、冒泡、快速、堆排序的算法效率稳定性分析，能判断哪种算法不受初始数据的影响；16、补充：用链表实现插入排序的过程、算法；11
