数据结构考研总结.docx

《数据结构考研总结.docx》由会员分享，可在线阅读，更多相关《数据结构考研总结.docx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构考研总结考察目标1 .掌握数据结构的基本概念、基本原理和基本方法。2 .掌握数据的逻辑结构、存储结构及基本操作的实 现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3 .能够运用数据结构的基本原理和方法进行问题的 分析与求解；具备采用C、C+或Java语言设计与实现算法的能力。第2章线性表一、考研知识点线性表的定义和基本操作线性表的实现1 .顺序存储2 .链式存储3 .线性表的应用二、考查重点1 .线性结构的特点；2 .线性表在顺序存储及链式存储方式下的基本操作及 其应用；3 .线性表的顺序存储及链式存储情况下，其不同和优 缺点比较，及其各自适用的场合。单链表中设置头指针、循环链

2、表中设置尾指针而不设 置头指针的各自好处；4 .能分析所写算法的时间和空间复杂度。分析：线性表是一种最简单的数据结构，在线性表方面，主 要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性 表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。 另外，还要掌握线性表的基本应用。线性表一章在线性结构的学习乃至整个数据结构学科 的学习中，其作用都是不可低估的。线性表一章小的知识点比较少，一般会出一个综 合题，并且容易和第三章、第九章和第十章的内容结合来考，注意对基本知识的理解，能够 利用书上的理论解决具体问题。学习过程中要注意多积累，多看、多写一些

3、相关算法。三、考研真题选择题近几年第2章没有考选择题，只有两个计算时间复杂 度的题目，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，可以和第3章、第9章和第10章的内容结合来出题。1 .设n是描述问题规模的非负整数，下面程序片段的 时间复杂度是。x=2;while x=2*x; A. 0 B. 0 C. 0 D. 02 .求整数n的阶乘的算法如下，其时间复杂度是。int factif return 1;return n*fact;)A. o B. 0 C. 0 D. 0分析：考查的是算法时间复杂度的计算。可以放在第 二章，实际这内容贯穿每一章内容中算法的度量。综

4、合题1 .已知一个带有表头结点的单链表结点结构为，假设 该链表只给出了头指针list。在不改变链表的前提下，请设计一 个尽可能高效的算法，查找链表中倒数第k个位置上的结点。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：描述算法的基本设计思想；描述算法的详细实现步骤；根据设计思想和实现步骤，采用程序设计语言描述算 法，关键之处给出简要注释。分析：此题考查线性表的链式存储，主要是线性表的 基本操作的应用。做此题时要把握算法的效率。算法基本思想如下：从头到尾遍历单链表，并用指针P 指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针P所指向 的结点即为所查找的结点。

5、详细实现步骤：增加两个指针变量和一个整型变量， 从链表头向后遍历，其中指针pl指向当前遍历的结点，指针P指向pl所指向结 点的前k个结点，如果pl之前没有k个结点，那么P指向表头结点。用整型变量i表示当 前遍历了多少结点，当ik时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时, P或者指向表头结点，或者指向链表中倒数第k个位置上的结点。算法描述：int locatepl=:list-link;p=list;i=l ；while(pl=pl-link;i+；ifp=p-next;如果ik,则p也后移ifreturn 0;链表没有k个结点else(printf;return 1;)2 .设

6、将n个整数存放到一维数组R中，试设计一个在 时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P个位置，即将R中的数据由变换为要求：给出算法的基本设计思想。根据设计思想，采用C或C+或JAVA语言表述算法, 关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度分析：此题考查的是数组的操作，线性表的顺序存储 的核心就是数组，因此此题实质上是考查的线性表的顺序存 储的操作及其应用。做此题时要考虑算法的时间和空间复杂 度。解法一：算法的基本设计思想：可以将这个问题看做是把数组 ab转化成数组ba,先将a逆置得到ab,再将b逆置得到ab,最后将整个ab逆置得到二ba。 设reverse函

7、数执行将数组元素逆置的操作，对abcdefgh 向左循环移动3个位置的过程如下：reverse 得至!J cbadefgh；reverse 得至！J cbahgfde；reverse 得至!J defghabco注：reverse中，两个参数分别表示数组中待转换元素 的始末位置。算法描述：void reverse将数组中从low到high的元素逆置int temp;for/2;i+)temp=RElow+i;R10ow+i=Rhigh-i;Rhigh-i=temp;)void conversereverse;reverse;reverse;)上述算法中三个reverse函数的时间复杂度分别是0

8、、 0/2)、0,故所设计算法的时间复杂度为0,空间复杂度为0。解法二：算法思想：创建大小为p的辅助数组S,将R中前p个 整数依次暂存在S中，同时将R中后n-p个整数左移，然后 将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为0,空间复杂度为0。3 . 一个长度为L的生序列S,处在第厂L/21个位置的 数称为S的中位数，例如，若序列Sl=,则S1的中位数是 15,两个序列的中位数是含它们所有元素的升序序列的中位 数。例如，若S2=，则S1和S2的中位数是11。现在有两个 等长升序序列A和B,试设计一个在时间和空间方面都尽可 能高效的算法，找出两个序列A和B的中位数。要求：给出算法的基本

9、设计思想。根据设计思想，采用C或C+或JAVA语言描述算法， 关键之处给出注释。分析：此题考查线性表的顺序存储， 主要是线性表的基本操作的应用。做此题时要把握T算法的效率。算法的基本设计思想如下：分别求出序列A和B的中位数，设为a和b,求序歹U A 和B的中位数过程如下：1）若a=b,则a或b即为所求中位数，算法结束；2）若a 3）若ab,则舍弃序列A中较大的一半， 同时舍弃序列B中较小的一半，要求舍弃的长度相等；在保留的两个升序序列中，重复过程1） -3）,直到两 个序列中只含一个元素时为止，较小者即为所求的中位数。算法实现如下：int Msearchint sl=O, dl=n-l, ml

10、, s2=0, d2=n-l, m2;分别表示序列A和B的首位数、末尾数和中位数Whileml=/2;m2=/2;if return Aml;else ifif%2=0sl=ml;d2=m2;elsesl=ml+l;d2=m2;elseif%2=0dl=ml;s2=m2;elsedl=ml+l;s2=m2;)return Asl 算法的时间复杂度为0,空间复杂度为0。4.假定采用带头结点的单链表，如果有共同 后缀,长度分别为lenl和len2,则可共享相同的后缀存储 空间，例如，loading”和“Beijing，如下图所示。设strl和str2分别指向两个单词所在单链表的头结 点，链表结点结

11、构为，请设计一个时间上尽可能高效的算法, 找出由strl和str2所指向两个链表共同后缀的起始位置。要求：给出算法的基本设计思想。根据设计思想，采用C或C+或JAVA语言描述算法, 关键之处给出注释。说明你所设计算法的时间复杂度。分析：两个单链表有公共结点，则从公共结点开始， 它们的next都指向同一个结点。由于每个单链表结点只有 一个next域，因此，从第一个公共结点开始，之后它们所 有的结点都是重合的，不可能再出现分叉。因此，我们判断 两个链表是不是有重合的部分，只要分别遍历两个链表到最 后一个结点。如果两个尾结点是一样的，说明它们有公共结 点；否则两个链表没有公共的结点。因为两个链表长度

12、不一定一样，在顺序遍历两个链表 到尾结点时，并不能保证在两个链表上同时到达尾结点。假 设一个链表比另一个长k个结点，我们先在长的链表上遍历 k个结点，之后再同步遍历，此时能够保证同时到达最后一 个结点。在遍历中，第一个相同的结点就是第一个公共结点。算法思想：根据两个单链表的长度，求出它们的长度 之差；在长的单链表上先遍历长度之差个结点；同步遍历两 个单链表，直接找到相同的结点，若有相同结点返回该节点, 若没有则一直到链表结束。算法实现：LinkList searchiflong=strl-next; short=str2-next;k=lenl-len2;else long=str2-next

13、; short=strl-next;k=len2-lenl;while long=long-next; k一;whileif return long;else long=long-next; short=short-next;)return NULL;)由于每个表仅遍历一遍，因此算法时间复杂度为0,空间复杂度为0o四、练习题选择题1 .下述哪一条是顺序存储结构的优点?A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示2 .下面关于线性表的叙述中，错误的是哪一个？A.线性表采用顺序存储，必须占用一片连续的存储单 y L o8 .线性表采用顺序存储，便于进行插入和

14、删除操作。C.线性表采用链接存储，不必占用一片连续的存储单 yL oD.线性表采用链接存储，便于插入和删除操作。9 .线性表是具有n个的有限序列。A.表元素 B.字符 C.数据元素 D.数 据项 E.信息项10 若某线性表最常用的操作是存取任一指定序号的元 素和在最后进行插入和删除运算，则利用存储方式最节省时 间。/从2016年计算机考研大纲来看，考研数据结构基本概 念的理解是重点，只有深刻理解基本概念，才能认真思考。 提示：常考的点是基本概念的应用，数据结构的选择题主要 是利用基本概念的运算，而大题则是多种基本数据结构上基 本运算的叠加，数据结构陷阱重重，经过以下6个地方千万 要注意。栈、队

15、列和数组时数据结构的重要工具，考查重点偏 向于应用。对于具体的定义的方式简单清楚就可以，重点是 理解栈、队列的特点，熟练掌握栈、队列的一些经典的应用, 在应用题中，常常会用到栈、队列数组作为工具。树是数据结构最重要的部分，它的内容纷繁而复杂， 但又尤为重要，是复习的重中之重。对于树的复习方法，要 重点掌握树的遍历，树的任何操作，其实都是以遍历为基础, 稍加改动visit函数而已。图的概念比较多，没有基本概念的基础，是很难把知 识掌握清楚的。对于图，是承接着树而衍生出来的，在实际 应用中，图更为广泛。所有问题都是化未知为已知，解决图 的问题，很多时候是借助树和二叉树来实现的，应注意树、 二叉树和

16、图之间的对应关系。考研复习中，图无疑是另一个 重点，此部分出大题的可能性很高。要重视有人名来命名的 算法，这类算法是为了纪念作者而命名的，可见其经典性， 这类算法也相当有难度，考试时，仅仅只会就此算法稍加改 动，或应用算法的思想来命题。线性表部分由于比较简单，又是整个数据结构的基础, 所以考察的内容会比较细致。对于线性表灵活运用的程度要 求较高。复习时，应充分理解线性表的顺序存储，链式存储。熟练掌握初始化、插入、删除等基本操作。此部分，有可能 出大题的地方：集合求并、一元多项式求和。内部排序会出选择题，重点考察的并不是排序的具体 实现算法，而是排序的过程，每次排序的结果都要清楚，每 种排序的特

17、点都要明白，这都是选择题考察的侧重点，排序 同时也会应用在综合题中，适当的“记忆”算法，重点还是 理解排序算法的过程和思想。外部排序了解概念，对知识点 的结论清晰。查找会出选择题，但是查找的思想会融入在排序里考 察，也就是说查找是排序的基础，对于此部分要注重理解算 法的思想，重点放在常用算法的实现。数据结构考研真题及知识点解析考察目标1 .理解数据结构的基本概念、基本原理和基本方法。2 .掌握数据的逻辑结构、存储结构及基本操作的实 现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3 .能够运用数据结构的基本原理和方法进行问题的 分析与求解，具备采用C、C+或Java语言设计与实现算法的能

18、力。第2章线性表一、考研知识点线性表的定义和基本操作线性表的实现1 .顺序存储2 .链式存储3 .线性表的应用二、考研真题选择题近两年第2章没有考选择题，因为此章主要是线性表 的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、 第9章和第10章的内容结合来出题。1.设n是描述问题规模的非负整数，下面程序片段的 时间复杂度是。x=2;while x=2*x;2A. 0 B. 0 C. 0 D. 0分析：答案是A,此题考查的是算法时间复杂度的计算。 可以放在第二章，实际这内容贯穿每一章内容中算法的度量。综合题1 .已知一个带有表头结点的单链表结点结构为，假设 该链表只给出

19、了头指针list。在不改变链表的前提下，请设计一 个尽可能高效的算法，查找链表中倒数第k个位置上的结点。若查找成功，算法输出该结 点的data值，并返回1；否则，只返回0。要求：描述算法的基本设计思想；描述算法的详细实现步骤；根据设计思想和实现步骤，采用程序设计语言描述算 法，关键之处给出简要注释。分析：此题考查线性表的链式 存储，主要是线性表的基本操作的应用。做此题时要把握算法的效率。算法基本思想如下：从头到尾遍历单链表，并用指针P 指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针P所指向 的结点即为所查找的结点。详细实现步骤：增加两个指针变量和一个整型变量， 从链表头向后遍历，

20、其中指针pl指向当前遍历的结点，指针P指向pl所指向结 点的前k个结点，如果pl之前没有k个结点，那么p指向表头结点。用整型变量i表示当 前遍历了多少结点，当ik时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时,P或者指向表头结点，或者指向链表中倒数第k个位置上的结点。算法描述：int locatepl=list-link;p=list;i=l;whilepl=pl-link;i+；ifp=p-next;如果ik,则p也后移)ifreturn 0;链表没有k个结点elseprintf;return 1;2 .设将n个整数存放到一维数组R中，试设计一个在 时间和空间两方面尽可能有效的算法

21、，将R中保有的序列循 环左移P个位置，即将R中的数据由变换为要求：给出算法的基本设计思想。根据设计思想，采用C或C+或JAVA语言表述算法， 关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度分析：此题考查的是数组的操作，线性表的顺序存储 的核心就是数组，因此此题实质上是考查的线性表的顺序存 储的操作及其应用。做此题时要考虑算法的时间和空间复杂 度。解法一：算法的基本设计思想：可以将这个问题看做是把数组 ab转化成数组ba,先将a逆置得到ab,再将b逆置得到ab,最后将整个ab逆置得到二ba。 设reverse函数执行将数组元素逆置的操作，对abcdefgh 向左循环移动3个位置的过程

22、如下：reverse 得至!J cbadefgh；reverse 得至！J cbahgfde；reverse 得至!J defghabco注：reverse中，两个参数分别表示数组中待转换元素 的始末位置。算法描述:void reverse将数组中从low到high的元素逆置int temp;for/2;i+)temp=RElow+i;R10ow+i=Rhigh-i;Rhigh-i=temp;)void conversereverse;reverse;reverse;)上述算法中三个reverse函数的时间复杂度分别是0、 0/2)、0,故所设计算法的时间复杂度为0,空间复杂度为0。解法二：算

23、法思想：创建大小为p的辅助数组S,将R中前p个 整数依次暂存在S中，同时将R中后n-p个整数左移，然后 将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为0,空间复杂度为0。3. 一个长度为L的生序列S,处在第厂L/21个位置的 数称为S的中位数，例如，若序列Sl=,则S1的中位数是 15,两个序列的中位数是含它们所有元素的升序序列的中位 数。例如，若S2=，则S1和S2的中位数是11。现在有两个 等长升序序列A和B,试设计一个在时间和空间方面都尽可 能高效的算法，找出两个序列A和B的中位数。要求：给出算法的基本设计思想。根据设计思想，采用C或C+或JAVA语言描述算法， 关键之处给出注

24、释。解答：此题考查线性表的顺序存储， 主要是线性表的基本操作的应用。做此题时要把握算法的效 率。算法的基本设计思想如下：分别求出序列A和B的中位数，设为a和b,求序歹U A 和B的中位数过程如下：1）若a=b,则a或b即为所求中位数，算法结束；2）若a 3）若ab,则舍弃序列A中较大的一半， 同时舍弃序列B中较小的一半，要求舍弃的长度相等；在保留的两个升序序列中，重复过程1） -3）,直到两 个序列中只含一个元素时为止，较小者即为所求的中位数。算法实现如下：int Msearchint sl=O, dl=n-l, ml, s2=0, d2=n-l, m2;分别表示序列A和B的首位数、末尾数和中

25、位数Whileml=/2;m2=/2;if return Aml;else ifif%2=0sl=ml;d2=m2;elsesl=ml+l;d2=m2;elseif%2=0dl=ml;s2=m2;elsedl=ml+l;s2=m2;)return Asl 算法的时间复杂度为0,空间负责杂度为0。三、考查重点1 .线性结构的特点；2 .线性表在顺序存储及链式存储方式下的基本操作及 其应用;3 .线性表的顺序存储及链式存储情况下，其不同和优 缺点比较，及其各自适用的场合。单链表中设置头指针、循 环链表中设置尾指针而不设置头指针的各自好处；4 .能分析所写算法的时间和空间复杂度。分析：线性表一章在线

26、性结构的学习乃至整个数据结 构学科的学习中，其作用都是不可低估的。线性表一章小的 知识点比较少，一般会出一个综合题，并且容易和第三章、 第九章和第十章的内容结合来考，注意对基本知识的理解， 能够利用书上的理论解决具体问题。学习过程中要注意多积 累，多看、多写一些相关算法。四、练习题选择题1 .下述哪一条是顺序存储结构的优点？A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示2 .下面关于线性表的叙述中，错误的是哪一个？A.线性表采用顺序存储，必须占用一片连续的存储单 y L o8 .线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一

27、片连续的存储单y L oD.线性表采用链接存储，便于插入和删除操作。3 .线性表是具有n个的有限序列。A.表元素 B.字符 C.数据元素 D.数 据项 E.信息项4 .若某线性表最常用的操作是存取任一指定序号的元 素和在最后进行插入和删除运算，则利用存储方式最节省时 间。A.顺序表 B.双链表 C.带头结点的双循环 链表 D.单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插 入一个元素和删除第一个元素，则采用存储方式最节省运算 时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表6 .若长度为n的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的

28、算法的时间复杂度为。2A. 0 B. 0 C. 0 D. 07 .对于顺序存储的线性表，访问结点和增加、删除结 点的时间复杂度为。A. 0 0 B. 0 0 C. 0 0 D. 0 08 .线性表以链接方式存储时，访问第i位置元素的时 间复杂性为。A. 0 B. 0 C. 0 D. 0综合题1 .掌握线性表中几个最基本的操作算法 逆置操作顺序表的就地逆置void reverseforA. elemiA. elemj; 元素交换)链表的就地逆置void LinkList_reverse p=L-next; q=p-next;whiler=q-next;q-next=p;P=q； q=r;L-ne

29、xt-next=NULL; 修改第一个元素的指针值L-next=p;修改表头结点指针值线性表的合并顺序表的合并：顺序存储的线性表la, 1b的关键字为 整数，元素非递减有序，线性表空间足够大，试编写高效算 法，将1b中元素合并到la中，使新的la的元素仍非递减 有序。分析：从后往前插入，避免移动元素void unionm=la. length; n=lb. length;k=m+n; i=m; j=n;循环指针赋值，从后往前比较whileifla. elemk=la. elemi; k-； i-;elsela. elemk=lb. elemj; k-; j一; )if 判断lb是否为空 la.

30、 elemk=lb. elemj; k一; j一;la. length=m+n;数据结构复习重点归纳一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为：概论，线性表， 栈和队列，串，多维数组和广义表，树和二叉树，图，查找, 内排，外排，文件，动态存储分配。对于绝大多数的学校而言，“外排，文件，动态存储 分配”三章基本上是不考的，在大多数高校的计算机本科教 学过程中，这三章也是基本上不作讲授的。所以，大家在这 三章上可以不必花费过多的精力，只要知道基本的概念即 可。但是，对于报考名校特别是该校又有在试卷中对这三章 进行过考核的历史，那么这部分朋友就要留意这三章了。按照以上我们给出的章

31、节以及对后三章的介绍，数据 结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有 的学校甚至不考。线性表：基础章节，必考内容之一。考题多数为基本 概念题，名校考题中，鲜有大型算法设计题。如果有，也是 与其它章节内容相结合。栈和队列：基础章节，容易出基本概念题，必考内容 之一。而栈常与其它章节配合考查，也常与递归等概念相联 系进行考查。串：基础章节，概念较为简单。专门针对于此章的大 型算法设计题很少，较常见的是根据KMP进行算法分析。多维数组及广义表：基础章节，基于数组的算法题也 是常见的，分数比例波动较大，是出题的“可选单元”或 “侯补单元”。一般如果要出题，多数不会作为大题出

32、。数 组常与“查找，排序”等章节结合来作为大题考查。树和二叉树：重点难点章节，各校必考章节。各校在 此章出题的不同之处在于，是否在本章中出一到两道大的算 法设计题。通过对多所学校的试卷分析，绝大多数学校在本 章都曾有过出大型算法设计题的历史。图：重点难点章节，名校尤爱考。如果作为重点来考, 则多出现于分析与设计题型当中，可与树一章共同构成算法 设计大题的题型设计。查找：重点难点章节，概念较多，联系较为紧密，容 易混淆。出题时可以作为分析型题目给出，在基本概念型题 目中也较为常见。算法设计型题中可以数组结合来考查，也 可以与树一章结合来考查。排序：与查找一章类似，本章 同属于重点难点章节，且概念

33、更多，联系更为紧密，概念之 间更容易混淆。在基本概念的考查中，尤爱考各种排序算法 的优劣比较此类的题。算法设计大题中，如果作为出题，那 么常与数组结合来考查。二、数据结构各章节重点勾划：第0章概述本章主要起到总领作用，为读者进行数据结构的学习 进行了一些先期铺垫。大家主要注意以下几点：数据结构的 基本概念，时间和空间复杂度的概念及度量方法，算法设计 时的注意事项。本章考点不多，只要稍加注意理解即可。第一章线性表作为线性结构的开篇章节，线性表一章在线性结构的 学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链 式存储的概念，链式存储概念将是整个数据结构学科的重

34、中 之重，无论哪一章都涉及到了这个概念。总体来说，线性表一章可供考查的重要考点有以下几 个方面：1 .线性表的相关基本概念，如：前驱、后继、表长、 空表、首元结点，头结点，头指针等概念。2 .线性表的结构特点，主要是指：除第一及最后一个 元素外，每个结点都只有一个前趋和只有一个后继。3 .线性表的顺序存储方式及其在具体语言环境下的两 种不同实现：表空间的静态分配和动态分配。静态链表与顺 序表的相似及不同之处。4 .线性表的链式存储方式及以下几种常用链表的特点 和运算：单链表、循环链表，双向链表，双向循环链表。其 中，单链表的归并算法、循环链表的归并算法、双向链表及 双向循环链表的插入和删除算法

35、等都是较为常见的考查方 式。此外，近年来在不少学校中还多次出现要求用递归算法 实现单链表输出的问题。在链表的小题型中，经常考到一些诸如：判表空的题。 在不同的链表中，其判表空的方式是不一样的，请大家注意。5 .线性表的顺序存储及链式存储情况下，其不同的优 缺点比较，即其各自适用的场合。单链表中设置头指针、循 环链表中设置尾指针而不设置头指针以及索引存储结构的 各自好处。第二章栈与队列栈与队列，是很多学习DS的同学遇到第一只拦路虎， 很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈 与队列，是走向DS高手的一条必由之路，学习此章前，你可以问一下自己是不是已经知道了以 下几点：1 .栈、队列的

36、定义及其相关数据结构的概念，包括： 顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取 数据的特点。2 .递归算法。栈与递归的关系，以及借助栈将递归转 向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi 问题，背包问题，二叉树的递归和非递归遍历问题，图的深 度遍历与栈的关系等。其中，涉及到树与图的问题，多半会 在树与图的相关章节中进行考查。3 .栈的应用：数值表达式的求解，括号的配对等的原 理，只作原理性了解，具体要求考查此为题目的算法设计题 不多。4 .循环队列中判队空、队满条件，循环队列中入队与 出队算法。如果你已经对上面的几点了如指掌，栈与队列一章可 以不看书了。注意，我说

37、的是可以不看书，并不是可以不作 题哦。第三章串经历了栈一章的痛苦煎熬后，终于迎来了 串一章的柳暗花明。串，在概念上是比较少的一个章节，也是最容易自学 的章节之一，但正如每个过来人所了解的，KMP o算法是这一章的重要关隘，突破此关隘后，走过去 又是一马平川的大好DS山河了，呵呵。串一章需要攻破的主要堡垒有：1串的基本概念，串与线性表的关系，空串与空格串 的区别，串相等的条件2 .串的基本操作，以及这些基本函数的使用，包括： 取子串，串连接，串替换，求串长等等。运用串的基本操作 去完成特定的算法是很多学校在基本操作上的考查重点。3 .顺序串与链串及块链串的区别和联系，实现方式。4 . KMP算法

38、思想。KMP中next数组以及nextval数组 的求法。明确传统模式匹配算法的不足，明确next数组需 要改进之外。其中，理解算法是核心，会求数组是得分点。 不用我多说，这一节内容是本章的重中之重。可能进行的考 查方式是：求next和nextval数组值，根据求得的next或 nextval数组值给出运用KMP算法进行匹配的匹配过程。第四章 数组与广义表学过程序语言的朋友，数组的概念我们已经不是第一 次见到了，应该已经“一回生，二回熟” 了，所以，在概念 上，不会存在太大障碍。但作为考研课程来说，本章的考查 重点可能与大学里的程序语言所关注的不太一样，下面会作 介绍。广义表的概念，是数据结构

39、里第一次出现的。它是线 性表或表元素的有限序列，构成该结构的每个子表或元素也 是线性结构的，所以，这一章也归入线性结构中。本章的考查重点有：1 .多维数组中某数组元素的position求解。一般是给 出数组元素的首元素地址和每个元素占用的地址空间并组 给出多维数组的维数，然后要求你求出该数组中的某个元素 所在的位置。2 .明确按行存储和按列存储的区别和联系，并能够按 照这两种不同的存储方式求解1中类型的题。3 .将特殊矩阵中的元素按相应的换算方式存入数组 中。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的 稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组， 带辅助行向量的二元组，十字链表存

40、储。掌握将稀疏矩阵的 三元组或二元组向十字链表进行转换的算法。4 .广义表的概念，特别应该明确表头与表尾的定义。 这一点，是理解整个广义表一节算法的基础。近来，在一些 学校中，出现了这样一种题目类型：给出对某个广义表L若 干个求了若干次的取头和取尾操作后的串值，要求求出原广 义表L。大家要留意。5 .与广义表有关的递归算法。由于广义表的定义就是 递归的，所以，与广义表有关的算法也常是递归形式的。比 如：求表深度，复制广义表等。这种题目，可以根据不同角 度广义表的表现形式运用两种不同的方式解答：一是把一个 广义表看作是表头和表尾两部分，分别对表头和表尾进行操 作；二是把一个广义表看作是若干个子表

41、，分别对每个子表 进行操作。第五章树与二叉树从对线性结构的研究过度到对树形结构的研究，是数 据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一 切，将最终影响你的专业课总分。所以，树这一章的重要性, 已经不说自明了。总体来说，树一章的知识点包括：二叉树的概念、性质和存储结构，二叉树遍历的三 种算法，在三种基本遍历算法的基础上实现二叉树的其它算 法，线索二叉树的概念和线索化算法以及线索化后的查找算 法，最优二叉树的概念、构成和应用，树的概念和存储形式, 树与森林的遍历算法及其与二叉树遍历算法的联系，树与森 林和二叉树的转换。下面我们来看考试中

42、对以上知识的主要考查方法：1 .二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义，让你说明二 叉树与普通双分支树的区别；考查满二叉树和完全二叉树的 性质，普通二叉树的五个性质：第i层的最多结点数，深度 为k的二叉树的最多结点数，n0=n2+l的性质，n个结点的 完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之 间的换算关系。二叉树的顺序存储和二叉链表存储的各自优缺点及适 用场合，二叉树的三叉链表表示方法。2 .二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法 能否理解，进而关系到树一章的算法设计题能否顺利完成。 二叉树的遍历算法有三种：先序，中序和后序。其划

43、分的依 据是视其每个算法中对根结点数据的访问顺序而定。不仅要 熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并 且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的 很多算法，可以直接根据三种递归算法改造而来，所以，掌 握了三种遍历的非递归算法后，对付诸如：“利用非递归算 法求二叉树叶子个数”这样的题目就下笔如有神了。我会在 另一篇系列文章里给出三种遍历的递归和非递归算法的背 记版，到时请大家一定熟记。3 .可在三种遍历算法的基础上改造完成的其它二叉树 算法：求叶子个数，求二叉树结点总数，求度为1或度为2 的结点总数，复制二叉树，建立二叉树，交换左右子树，查 找值为n的某个指定结点，删除值

44、为n的某个指定结点，诸 如此类等等等等。如果你可以熟练掌握二叉树的递归和非递 归遍历算法，那么解决以上问题就是小菜一碟了。4 .线索二叉树：线索二叉树的引出，是为避免如二叉树遍历时的递归 求解。众所周知，递归虽然形式上比较好理解，但是消耗了 大量的内存资源，如果递归层次一多，势必带来资源耗尽的 危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的 算法，线索化后二叉树的遍历算法，基本线索二叉树的其它 算法问题。5 .最优二叉树：最优二叉树是为了解决特定问题引出的特殊二叉树结 构，它的前提是给二叉树的每条边赋予了权值，这样形成的 二叉树按权相

45、加之和是最小的。最优二叉树一节，直接考查 算法源码的很少，一般是给你一组数据，要求你建立基于这 组数据的最优二叉树，并求出其最小权值之和，此类题目不 难，属送分题。6 .树与森林：二叉树是一种特殊的树，这种特殊不仅仅在于其分支 最多为2以及其它特征，一个最重要的特殊之处是在于：二 叉树是有序的！即：二叉树的左右孩子是不可交换的，如果 交换了就成了另外一棵二叉树，这样交换之后的二叉树与原 二叉树我们认为是不相同的两棵二叉树。但是，对于普通的 双分支树而言，不具有这种性质。树与森林的遍历，不像二叉树那样丰富，他们只有两 种遍历算法：先根与后根。在难度比较大的考试中，也有基 于此二种算法的基础上再进

46、行扩展要求你利用这两种算法 设计其它算法的，但一般院校很少有这种考法，最多只是要 求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍 历算法是有对应关系的：先根遍历对应二叉树的先序遍历， 而后根遍历对应二叉树的中序遍历。这一点成为很多学校的 考点，考查的方式不一而足，有的直接考此句话，有的是先 让你求解遍历序列然后回答这个问题。二叉树、树与森林之 所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用 二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子 及兄弟，而森林也是利用二叉链表存储孩子及兄弟。树一章，处处是重点，道道是考题，大家务必个个过 关。第六章图如果说，从线性结构向树形结构研究的转变，是数据 结构学科对数据组织形式研究的一次升华，那么从树形结构 的研究转到图形结构的研究，则进一步让我们看到了数据结 构对于解决实际问题的重大推动作用。图这一章的特点是：概念繁多，与离散数学中图的概 念联系紧密，算法复杂，