数据结构考研总结

1 / 74 数据结构考研总结 数据结构考研真题及知识点解析 考察目标 1. 掌握数据结构的基本概念、基本原理和基本方法。 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复 杂度与空间复杂度的分析。 3. 能够运用数据结构的基本原理和方法进行问题的分析与求解；具备采用 C、 C+或 Java语言设计与实现算法的能力。 第 2 章 线性表 一、考研知识点 2 / 74 线性表的定 义和基本操作 线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 二、考查重点 1线性结构的特点； 2线性表在顺序存储及链式存储方式下的基本操作及其应用； 3线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。 单链表中设置头指针、循环链表中设置尾指针而不设置头指3 / 74 针的各自好处； 4能分析所写算法的时间和空间复杂度。 分析： 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、 线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链 式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估 的。线性表一章小的知识点比较少，一般会出一个综合题，并且 容易和第三章、第九章和第 十章的内容结合来考，注意对基本知识的理解，能够利用书4 / 74 上的理论解决具体问题。学习过 程中要注意多积累，多看、多写一些相关算法。 三、考研真题 选择题 近几年第 2章没有考选择题，只有两个计算时间复杂度的题目，因为此章主要是线性表 的操作，而且又是这门课的一个基础，考综合题的可能性比较大，可以和第 3 章、第 9 章和 第 10章的内容结合来出题。 1设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是。 x=2; while(x 2.求整数 n 的阶乘的算法如下，其时间复杂度5 / 74 是。 int fact(int n) if(n return n*fact(n-1); 2 A. o(log2n) B. O(n) C. O(nlog2n) D. O(n2) 分析：考查的是算法时间复杂度的计算。可以放在第二章，实际这内容贯穿每一章内容 中算法的度量。 综合题 1. 已 知 一 个 带 有 表 头 结 点 的 单 链 表 结 点 结 构 为(data,link)，假 设该链表只给 6 / 74 出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒 数第 k个位置上的结点。若查找成功，算法输出该结点的 data值，并返回 1； 否则，只返回 0。要求： 描述算法的基本设计思想； 描述算法的详细实现步骤； 根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处给出简要注释。 分析：此题考查线性表的链式存储，主要是线性表的基本操作的应用。做此题时要把握 算法的效率。 算法基本思想如下：从头到尾遍历单链表，并用指针 p指向当前结点的前 k个结 7 / 74 点。当遍历到链表的最后一个结点时，指针 p所指向的结点即为所查找的结点。 详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指 针 p1指向当前遍历的结点，指针 p 指向 p1所指向结点 的前k 个结点，如果 p1 之前没有 k 个结点，那么 p指向表头结点。用整型变量 i表示当前遍历了多少结点，当 ik时，指针 p 随着每次遍历，也向前移动一个结点。当遍历完成时， p 或者指向表头结点，或者指向链表 中倒数第 k个位置上的结点。 算法描述： int locate(Linklist list, int k) 8 / 74 p1=list-link; p=list; i=1; while(p1) p1=p1-link; i+; if(ik)p=p-next; /如果 ik，则 p也后移 if(p=list)return 0; /链表没有 k 个结点 9 / 74 else printf(% n,p -data); return 1; 2.设将 n(n,1)个整数存放到一维数组 R中，试设计一个在时间和空间两方面 尽可能有效的算法，将 R 中保有的序列循环左移 P 个位置，即将 R中的数据由 变换为要求： 给出算法的基本 设计思想。 10 / 74 根据设计思想，采用 C 或 C+或 JAVA 语言表述算法，关键之处给出注释。 说明你所设计算法的时间复杂度和空间复杂度 分析：此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。 解法一： 算法的基本设计思想：可以将这个问题看做是把数组 ab 转化 成数组 ba，先将 a 逆置得到 ab，再将 b 逆置得 -1-1-1-1-1-1-1 到 ab，最后将整个 ab 逆置得到 =ba。设reverse函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3个位置的过程如下： reverse(0,p-1)得到 cbadefgh； reverse(p,n-1)得到 cbahgfde； 11 / 74 reverse(0,n-1)得到 defghabc。 注： reverse 中，两个参数分别表示数组中待转换元素的始末位置。 算法描述： void reverse(int R, int low, int high) /将数组中从 low 到 high 的元素逆置 int temp; for(i=0;i temp=Rlow+i; Rl0ow+i=Rhigh-i; Rhigh-i=temp; 12 / 74 void converse(int R, int n, int p) reverse(R,0,p-1); reverse(R,p,n-1); reverse(R,0,n-1); 上述算法中三个 reverse函数的时间复杂度分别是 O(p/2)、O(n-p)/2)、 O(n/2)，故所设计算法的时间复杂度为 O(n)，空间复杂度为 O(1)。 解法二： 算法思想：创建大小为 p 的辅助数组 S，将 R 中前 p 个整数13 / 74 依次暂存在 S 中，同时将 R 中后 n-p 个整数左移，然后将 S中暂存的 p个数依次放回到 R中的后续单元。 时间复杂度为 O(n)，空间复杂度为 O(p)。 3.一个长度为 L的生序列 S，处在第 L/2 个位置的数称为S 的中位数，例如，若序列 S1=，则 S1的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2=，则 S1 和 S2的中位数是 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列 A 和 B的中位数。要求： 给出算法的基本设计思想。 根据设计思想，采用 C 或 C+或 JAVA 语言描述算法，关键之处给出注释。 分析：此题考查线性表的顺序存储，主要是线性表的基本操作的应用。做此题时 要把握 -1 算法的效率。 算法的基本设计思想如下： 14 / 74 分别求出序 列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B的中位数过程如下： 1）若 a=b，则 a或 b 即为所求中位数，算法结束； 2）若 a 3）若 ab，则舍弃序列 A 中较大的一半，同时舍弃序列 B中较小的一半，要求舍弃的长度相等； 在保留的两个升序序列中，重复过程 1） -3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。 算法实现如下： int M_search(int A,int B.int n) int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2; /分别表示序列 A 和 B 的首位数、末尾数和中位数 While(s1!=d1|s2!=d2) 15 / 74 m1=(s1+d1)/2; m2=(s2+d2)/2; if(Am1=Bm2) return Am1; else if(Am1 if(s1+d1)%2=0 s1=m1;d2=m2; elses1=m1+1;d2=m2; else if(s1+d1)%2=0 d1=m1;s2=m2; elsed1=m1+1;s2=m2; 16 / 74 return As1 算法的时间复杂度为 O(logn)，空间复杂度为 O(1)。 4.假定采用带头结点的单链表，如果有共同后缀，长度分别为 len1 和 len2，则可共享相同的后缀存储空间，例如， loading 和 Beijing ，如下图所示。 设 str1和 str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由 str1和 str2所指向两个链表共同后缀的起始位置。要求： 给出算法的基本设计思想。 根据设计思想，采用 C 或 C+或 JAVA 语言描述算法，关键之处给出注释。 说明你所设计算法的时间复杂度。 17 / 74 分析：两个单链表有公共结点，则从公共结点开始，它们的next都指向同一个结点。由于每个单链表结点只有一个 next域，因此，从第一个公共结点开始，之后它们所有的结点都是重合的，不可能再出现分叉。因此，我们判断两个链表是不是有重合的部分，只要分别遍历两个链表到最后一个结点。如果两个尾结点是一样的，说明它们有公共结点；否则两个链表没有公共的结点。 因为两个链表长度不一定一样，在顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点。假设一个链表比另一个长 k 个结点，我们先在长的链表上遍历 k个结点，之后再同步遍历，此时能够保证同时到达最后一个结点。在遍历中，第一个相同的结点就是第一个公共结点。 算法思想：根据两个单链表的长度，求出它们的长度之差；在长的单链表上先遍历长度之差个结 点；同步遍历两个单链表，直接找到相同的结点，若有相同结点返回该节点，若没有则一直到链表结束。 算法实现： LinkList search 18 / 74 if long=str1-next; short=str2-next; k=len1-len2; else long=str2-next; short=str1-next; k=len2-len1; while(k) long=long-next; k-; while(long) if(long=short) return long; else long=long-next; short=short-next; 19 / 74 return NULL; 由 于每 个表仅遍 历一 遍，因此 算法 时间复杂 度为O(len1+len2)，空间复杂度为 O(1)。 四、练习题 选择题 1下述哪一条是顺序存储结构的优点？ A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 2下面关于线性表的叙述中，错误的是哪一个？ A线性表采用顺序存储，必须占用一片连续的存储单元。 20 / 74 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 3线性表是具有 n 个的有限序列。 A表元素 B字符 C数据元素 D数据项 E信息项 4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。 / 从 2016 年计算机考研大纲来看，考研数据结构基本概念的理解是重点，只有深刻理解基本概念，才能认真思考。提示：常考的点是基本概念的应用，数据结构的选择题主要是利用基本概念的运算，而大题则是多种基本数据结构上基本运算的叠加，数据结构陷阱重重，经过以下 6 个地方千万要注意。 21 / 74 (1)栈、队列和数组时数据结构的重要工具，考查重点偏向于应用。对于具体的定义的方式简单清楚就可以，重点是理解栈、队列的特点，熟练掌握栈、队列的一些经典的应用，在应用题中，常常会用到栈、队列数组作为工具。 (2)树是数据结构最重要的部分，它的内容纷繁而复杂，但又尤为重要，是复习的重中之重。对于树的复习方法，要重点掌握树的遍历，树的任何操作，其实都是以遍历为基础，稍加改动 visit函数而已。 (3)图的概念比较多，没有基本概念的基础，是很难把知识掌握清楚的。对于图，是承接着树而衍生出来的，在实际应用中，图更为广泛。所有问题都是化未知为已知，解决图的问题，很多时候是借助树和二叉树来实现的，应注意树、二叉树和图之间的对应关系。考研复习中，图无疑是另一个重点，此部分出大题的可能性很高。要重视有人名来命名的算法，这类算法是为了纪念作者而命名的，可见其经典性，这类算法也相当有难度，考试时，仅仅只会就此算法 稍加改动，或应用算法的思想来命题。 (4)线性表部分由于比较简单，又是整个数据结构的基础，所以考察的内容会比较细致。对于线性表灵活运用的程度要22 / 74 求较高。复习时，应充分理解线性表的顺序存储，链式存储(单链表、静态链表、循环链表、双向链表 )。熟练掌握初始化、插入、删除等基本操作。此部分，有可能出大题的地方：集合求并、一元多项式求和。 (5)内部排序会出选择题，重点考察的并不是排序的具体实现算法，而是排序的过程，每次排序的结果都要清楚，每种排序的特点都要明白，这都是选择题考察的侧重点，排序同时也会应用在综合题中，适当的 记忆 算法，重点还是理解排序算法的过程和思想。外部排序了解概念，对知识点的结论清晰。 (6)查找会出选择题，但是查找的思想会融入在排序里考察，也就是说查找是排序的基 础，对于此部分要注重理解算法的思想，重点放在常用算法的实现。 数据结构考研真题及知识点解析 考察目标 1. 理解数据结构的基本概念、基本原理和基本方法。 23 / 74 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复 杂度与空间复杂度的分析。 3. 能够运用数据结构的基本原理和方法进行问题的分析与求解，具 备采用 C、 C+或 Java语言设计与实现算法的能力。 第 2 章 线性表 一、考研知识点 线性表的定义和基本操作 线性表的实现 1.顺序存储 2.链式存储 24 / 74 3.线性表的应用 二、考研真题 选择题 近两年第 2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基 础，考综合题的可能性比较大，而且可以和第 3章、第 9 章和第 10章的内容结合来出题。 1设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是。 x=2; while(x (logn) (n) (nlogn) (n) 分析：答案是 A，此题考查的是算法时间复杂度的计算。可以放在第二章，实际这内容 25 / 74 贯穿每一章内容中算 法的度量。 综合题 1. 已 知 一 个 带 有 表 头 结 点 的 单 链 表 结 点 结 构 为(data,link)，假设该链表只给 出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法 ，查找链表中倒 数第 k个位置上的结点。若查找成功，算法输出该结点的 data值，并返回 1； 否则，只返回 0。要求： 描述算法的基本设计思想； 描述算法的详细实现步骤； 根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处给出简要注释。 分析：此题考查线性表的链式存储，主要是线性表的基本操26 / 74 作的应用。做此题时要把握 算法的效率。 算法基本思想如下：从头到尾遍历单链表，并用指针 p指向当前结点的前 k个结 点。当遍历到链表的最后一个结点时，指针 p所指向的结点即为所查找的结点。 详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指 针 p1指向当前遍历的结点，指针 p 指向 p1所指向结点的前k 个结点，如果 p1 之前没有 k 个结点，那么 p指向表头结点。用整型变量 i表示当前遍历了多少结 点，当 ik时，指针 p 随着每次遍历，也向前移动一个结点。当遍历完成时， p 或者指向表头结点，或者指向链表 27 / 74 中倒数第 k个位置上的结点。 算法描述： int locate(Linklist list, int k) p1=list-link; p=list; i=1; while(p1) p1=p1-link; i+; 28 / 74 if(ik)p=p-next; /如果 ik，则 p也后移 if(p=list)return 0; /链表没有 k 个结点 else printf(% n,p -data); return 1; 2.设将 n(n,1)个整数存放到一维数组 R中，试设计一个在时间和空间两方面尽可能有效的算法，将 R中保有的序列循环左移 P个位置，即将 R中的数据由变换为要求： 29 / 74 给出算法的基本设计思想。 根据设计思想，采用 C 或 C+或 JAVA 语言表述算法，关键之处给出注释。 说明你所设计算法的时间复杂度和空间复杂度 分析：此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。 解法一 ： 算法的基本设计思想：可以将这个问题看做是把数组 ab 转化成数组 ba，先将 a 逆置得到 ab，再将 b 逆置得 -1-1-1-1-1-1-1 到 ab，最后将整个 ab 逆置得到 =ba。设reverse函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3个位置的过程如下： reverse(0,p-1)得到 cbadefgh； 30 / 74 reverse(p,n-1)得到 cbahgfde； reverse(0,n-1)得到 defghabc。 注： reverse 中，两个参数分别表示数组中待转换元素的始末位置。 算法描述： void reverse(int R, int low, int high) /将数组中从 low 到 high 的元素逆置 int temp; for(i=0;i temp=Rlow+i; Rl0ow+i=Rhigh-i; Rhigh-i=temp; 31 / 74 void converse(int R, int n, int p) reverse(R,0,p-1); reverse(R,p,n-1); reverse(R,0,n-1); 上述算法中三个 reverse函数的时间复杂度分别是 O(p/2)、O(n-p)/2)、 O(n/2)，故所设计算法的时间复杂度为 O(n)，空间复杂度为 O(1)。 解法二： 32 / 74 算法思想：创建大小为 p 的辅助数组 S，将 R 中前 p 个整数依次暂存在 S 中，同时将 R 中后 n-p 个整数左移，然后将 S中暂存的 p个数依次放回到 R中的后续单元。 时间复杂度为 O(n)，空间复杂度为 O(p)。 3.一个长度为 L的生序列 S，处在第 L/2 个位置的数称为S 的中位数，例如，若序列 S1=，则 S1的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2=，则 S1 和 S2的中位数是 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列 A 和 B的中位数。要求： 给出算法的基本设计思想。 根据设计思想，采用 C 或 C+或 JAVA 语言描述算法，关键之处给出注释。 解答：此题考查线性表的顺序存储，主要是线性表的基本操作的应用。做此题时 要把握算法的效率。 算法的基本设计思想如下： 33 / 74 分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B的中位数过程如下： 1）若 a=b，则 a或 b 即为所求中位数，算法结束； 2）若 a 3）若 ab，则舍弃序列 A 中较大的一半，同时舍弃序列 B中较小的一半，要求舍弃的长度相等； 在保留的两个升序序列中，重复过程 1） -3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。 算法实现如下： int M_search(int A,int B.int n) int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2; /分别表示序列 A 和 B 的首位数、末尾数和中位数 While(s1!=d1|s2!=d2) 34 / 74 m1=(s1+d1)/2; m2=(s2+d2)/2; if(Am1=Bm2) return Am1; else if(Am1 if(s1+d1)%2=0 s1=m1;d2=m2; elses1=m1+1;d2=m2; else if(s1+d1)%2=0 d1=m1;s2=m2; elsed1=m1+1;s2=m2; 35 / 74 return As1 算法的时间复杂度为 O(logn)，空间负责杂度为 O(1)。 三、考查重点 1线性结构的特点； 2线性表在顺序存储及链式存储方式下的基本操作及其应用； 3线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处； 4能分析所写算法的时间和空间复杂度。 分析：线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。线性表一章小的知识点36 / 74 比较少，一般会出一个综合题，并且容易和第三章、第九章和第十章的内容结合来考，注意对基本知识的理解，能够利用书上的理论解决具体问题。学习过程中要注意多积累，多看、多写一些相关算法。 四、练习题 选择题 1下述哪一条是顺序存储结构的优点？ A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表 示 2下面关于线性表的叙述中，错误的是哪一个？ A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 37 / 74 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 3线性表是具有 n 个的有限序列。 A表元素 B字符 C数据元素 D数据项 E信息项 4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。 A顺序表 B双 链表 C带头结点的双循环链表 D单循环链表 5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表 38 / 74 6若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为 (1 2A. O(0) B. O(1) C. O(n) D. O(n) 7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为。 A O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 8线性表以链接方式存储时，访问第 i 位置元素的时间复杂性为。 A O B O C O D O 综合题 1掌握线性 表中几个最基本的操作算法 逆置操作 39 / 74 顺序表的就地逆置 void reverse(SqList &A) for(i=1,j=;i ij; /元素交换 链表的就地逆置 void LinkList_reverse(Linklist &L) p=L-next; q=p-next; while (q) 40 / 74 r=q-next; q-next=p; p=q; q=r; L-next-next=NULL; /修改第一个元素的指针值 L-next=p; /修改表头 结点指针值 线性表的合并 顺序表的合并：顺序存储的线性表 la， lb的关键字为整数，元素非递减有序，线性表空间足够大，试编写高效算法，将lb中元素合并到 la中，使新的 la 的元素仍非递减有序。 分析：从后往前插入，避免移动元素 41 / 74 void union (Sqlist la, Sqlist lb) m=; n=; k=m+n; i=m; j=n; /循环指针赋值，从后往前比较 while (i0&j0) if (i=j) k=i; k-; i-; else k=j; k-; j-; 42 / 74 if(j0) /判断 lb是否为空 k=j; k-; j-; =m+n; 数据结构复习重点归纳 一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言， 外排，文件，动态存储分配 三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授 的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考43 / 74 核的历史，那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为： 概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。 栈和队列：基础章节，容易出基本概念题， 必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 串 ：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据 KMP进行算法分析。 多维数组及广义表 ：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的 可选单元 或 侯补单元 。一般如果要出题，多数不会作为大题出。数组常与44 / 74 查找，排序 等章节结合来作为大题考查。 树和二叉树 ：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 图 ： 重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 查找 ：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 排序 ：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概 念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。 二、数据结构各章节重点勾划： 45 / 74 第 0 章 概述 本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。 第一章 线性 表 作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都 是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据 结构学科的重中之重，无论哪一章都涉及到了这个概念。 总体来说，线性表一章可供考查的重要考点有以下几个方面： 1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。 46 / 74 2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。 3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态 分配和动态分配。静态链表与顺序表的相似及不同之处。 4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出的问题。 在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。 5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。 47 / 74 第二章 栈与队列 栈与队列，是很多学习 DS 的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向 DS高手的一条必由之路， 学习此章前，你可以问一下自己是不是已经知道了以下几点： 1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据的特点。 2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法： n!阶乘问题， fib 数列问题， hanoi 问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。 3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原 理性了解，具体要求考查此为题目的算法设计题不多。 48 / 74 4.循环队列中判队空、队满条件，循环队列中入队与出队算法。 如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是 可以不看书，并不是可以不作题哦。 第三章 串 经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。 串，在概念上是比较少的一个章节，也是最容易自学的章节之一，但正如每个过来人所了解的， KMP 。 算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好 DS山河了，呵呵。 串一章需要攻破的主要堡垒有： 1.串的基本概念，串与线性表的关系，空串与空格串的区别，串相等的条件 2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特49 / 74 定的算法是很多学校在基本操作上的考查重点。 3.顺序串与链串及块链串的区别和联系，实现方式。 算法思想。 KMP中 next数组以及 nextval数组的求法。明确传统模式匹配算法的不足，明确 next 数组需要改进之外。其中，理解算法是核心 ，会求数组是得分点。不用我多说，这一节内容是本章的重中之重。可能进行的考查方式是：求next 和 nextval 数组值，根据求得的 next 或 nextval 数组值给出运用 KMP算法进行匹配的匹配过程。 第四章 数组与广义表 学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经 一回生，二回熟 了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考查重点可能与大学里的程序语言所关注的不太一样，下面会作介绍。 广义表的概念，是数据结构里第一次出现的。它是线性表 或表元素的有限序列，构成该结构的每个子表或元素也是线性结构的，所以，这一章也归入线性结构中。 50 / 74 本章的考查重点有： 1.多维数组中某数组元素的 position 求解。一般是给出数组元素的 首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。 2.明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解 1 中类型的题。 3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有某 种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。 4.广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法的基础。近来，在一些学校中，出现了这样一种题目类型：给出对某个广义表 L若干个求了若干次的取头和取尾操作后的串值，要求求出原广义表 L。大家要留意。 51 / 74 5.与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比如：求表深度，复制广义表等。这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。 第五章 树与二叉树 从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。 总体来说，树一章的知识点包括： 二叉树的概念、性质和存储结构，二叉树遍历的三种算法，在三种基本遍历算法的基础上 实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森52 / 74 林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。 下面我们来看考试中对以上知识的主要考查方法： 1.二叉树的概念、性质和存储结构 考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：第 i层的最多结点数，深度为 k 的二叉树的最多结点数， n0=n2+1 的性质， n 个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系。 二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。 2.二叉树的三种遍历算法 这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺 利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视53 / 74 其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来，所以，掌握了三种遍历的非递归算法后，对付诸如： 利用非递归算法求二叉树叶子个数 这样的题目就下笔如有神了。我会在另一篇系列文章里给出三种遍历的递归和非递归算法的背记版，到时请大家一定熟记。 3.可在三种遍历算法的基础上改造完成的其它二叉树算法： 求叶子个数，求二叉树结点总数，求度为 1或度为 2 的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n 的某个指定结点，删除值为 n 的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。 4.线索二叉树： 线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，54 / 74 为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它 算法问题。 5.最优二叉树： 最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不 难，属送分题。 6.树与森林： 二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2 以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通 的双分支树而言，不具有这种性质。 55 / 74 树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写出他们的遍 历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟，而森林也是利用二叉链表存储孩子及兄弟。 树一章，处处是重点，道道是考题，大家务必个个过关。 第六章 图 如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那么从树形结构的研究56 / 74 转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。 图这一章的特点是：概念繁多，与 离散数学中图的概念联系紧密，算法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，如果不考查树与图两章的知识，几乎是不可想像的。 下面我们看一下图这一章的主要考点以及这些考点的考查方式： 1.考查有关图的基本概念问题： 这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，连通图，连通分量等概念。与这些概念相联系的相关计算题也应该掌握。 2.考查图的几种存储形式： 图的存储形式包括：邻接矩阵，邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生57 / 74 用算法或手写出与给定的结构相对应的该图的另一种存储形式。 3.考查图的两种遍历算法：深度遍历和广度遍历 深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于 先序、中序、后序遍历 对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如： 求最长的最短路径问题 和 判断两顶点间是否存在长为 K的简单路径问题 ，就分别用到了广度遍历和深度遍历算法。 4.生成树、最小生成树的概念以及最小生成树的构造： PRIM算法和 KRUSKAL算法。 考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。 5.拓扑排序问题： 拓扑排序有两种方法，一 是无前趋的顶点优先算法，二是无58 / 74 后继的顶点优先算法。换句话说，一种是 从前向后 的排序，一种是 从后向前 排。当然，后一种排序出来的结果是 逆拓扑有序 的。 6.关键路径问题： 这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求， 三是最晚时间是什么意思、如何求。简单地说，最早时间是通过 从前向后 的方法求的，而最晚时间是通过 从后向前 的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤。 在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初 始时，应该首先将所有顶点的最早时间全部置为 0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。 第一章 59 / 74 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、 记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 在高级语言程序中又分为：非结构的原子类型和结构类型 抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。 一个抽象的数据类型的软件模块通常包含 定义和表示和实现 用三元组：数据对象