数据结构考研知识点总结

数据结构考研真题及知识点解析考察目标1.掌握数据结构的基本概念、基本原理和基本方法。2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3.能够运用数据结构的基本原理和方法进行问题的分析与求解；具备采用C、C++或Java语言设计与实现算法的能力。第2章线性表一、考研知识点（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、考查重点1．线性结构的特点；2．线性表在顺序存储及链式存储方式下的基本操作及其应用；3．线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处；4．能分析所写算法的时间和空间复杂度。分析：线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。线性表一章小的知识点比较少，一般会出一个综合题，并且容易和第三章、第九章和第十章的内容结合来考，注意对基本知识的理解，能够利用书上的理论解决具体问题。学习过程中要注意多积累，多看、多写一些相关算法。三、考研真题（一）选择题近几年第2章没有考选择题，只有两个计算时间复杂度的题目，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，可以和第3章、第9章和第10章的内容结合来出题。1．（11年）设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（A）。x=2;while(xn/2)x=2*x;A.O(logn)B.O(n)C.O(nlogn)D.O(n2)2.（12年）求整数n（n=0）的阶乘的算法如下，其时间复杂度是（B）。intfact(intn){if(n=1)return1;returnn*fact(n-1);}A.o(log2n)B.O(n)C.O(nlog2n)D.O(n2)分析：考查的是算法时间复杂度的计算。可以放在第二章，实际这内容贯穿每一章内容中算法的度量。（二）综合题1.（09年）已知一个带有表头结点的单链表结点结构为(data,link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处给出简要注释。分析：此题考查线性表的链式存储，主要是线性表的基本操作的应用。做此题时要把握算法的效率。（1）算法基本思想如下：从头到尾遍历单链表，并用指针p指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。（2）详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针p1指向当前遍历的结点，指针p指向p1所指向结点的前k个结点，如果p1之前没有k个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少结点，当ik时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。（3）算法描述：intlocate(Linklistlist,intk){p1=list-link;p=list;i=1;while(p1){p1=p1-link;i++;if(ik)p=p-next;//如果ik，则p也后移}if(p==list)return0;//链表没有k个结点else{printf(“%\n”,p-data);return1;}}2.（10年）设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P（0﹤P﹤n）个位置，即将R中的数据由（X0X1……Xn-1）变换为（XpXp+1……Xn-1X0X1……Xp-1）要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度分析：此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。解法一：（1）算法的基本设计思想：可以将这个问题看做是把数组ab转化成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a-1b，再将b逆置得到a-1b-1，最后将整个a-1b-1逆置得到（a-1b-1）-1=ba。设reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（p=3）个位置的过程如下：reverse(0,p-1)得到cbadefgh；reverse(p,n-1)得到cbahgfde；reverse(0,n-1)得到defghabc。注：reverse中，两个参数分别表示数组中待转换元素的始末位置。（2）算法描述：voidreverse(intR[],intlow,inthigh){//将数组中从low到high的元素逆置inttemp;for(i=0;i=(high-low)/2;i++){temp=R[low+i];R[l0ow+i]=R[high-i];R[high-i]=temp;}}voidconverse(intR[],intn,intp){reverse(R,0,p-1);reverse(R,p,n-1);reverse(R,0,n-1);}（3）上述算法中三个reverse函数的时间复杂度分别是O(p/2)、O((n-p)/2)、O(n/2)，故所设计算法的时间复杂度为O(n)，空间复杂度为O(1)。解法二：算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(n)，空间复杂度为O(p)。3.（11年）一个长度为L（L=1）的生序列S，处在第┌L/2┐个位置的数称为S的中位数，例如，若序列S1=（11,13,15,17,19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2,4,6,8,20），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。分析：此题考查线性表的顺序存储，主要是线性表的基本操作的应用。做此题时要把握算法的效率。（1）算法的基本设计思想如下：分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数过程如下：1）若a=b，则a或b即为所求中位数，算法结束；2）若ab，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求舍弃的长度相等；3）若ab，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等；在保留的两个升序序列中，重复过程1）-3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。（2）算法实现如下：intM_search(intA[],intB[].intn){ints1=0,d1=n-1,m1,s2=0,d2=n-1,m2;//分别表示序列A和B的首位数、末尾数和中位数While(s1!=d1||s2!=d2){m1=(s1+d1)/2;m2=(s2+d2)/2;if(A[m1]==B[m2])returnA[m1];elseif(A[m1B[m2])if(s1+d1)%2==0{s1=m1;d2=m2;}else{s1=m1+1;d2=m2;}elseif(s1+d1)%2==0{d1=m1;s2=m2;}else{d1=m1+1;s2=m2;}}returnA[s1]B[s2]?A[s1]:B[s2];}（3）算法的时间复杂度为O(logn)，空间复杂度为O(1)。4.（12年）假定采用带头结点的单链表，如果有共同后缀，长度分别为len1和len2（这个条件是我查了一些资料后加上的，网上给的资料这个题目不完整），则可共享相同的后缀存储空间，例如，“loading”和“Beijing”，如下图所示。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为（data，next），请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度。分析：两个单链表有公共结点，则从公共结点开始，它们的next都指向同一个结点。由于每个单链表结点只有一个next域，因此，从第一个公共结点开始，之后它们所有的结点都是重合的，不可能再出现分叉。因此，我们判断两个链表是不是有重合的部分，只要分别遍历两个链表到最后一个结点。如果两个尾结点是一样的，说明它们有公共结点；否则两个链表没有公共的结点。因为两个链表长度不一定一样，在顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点。假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点，之后再同步遍历，此时能够保证同时到达最后一个结点。在遍历中，第一个相同的结点就是第一个公共结点。（1）算法思想：根据两个单链表的长度，求出它们的长度之差；在长的单链表上先遍历长度之差个结点；同步遍历两个单链表，直接找到相同的结点，若有相同结点返回该节点，若没有则一直到链表结束。（2）算法实现：LinkListsearch（LinkListstr1，LinkListstr2，intlen1，int2）{if（len1len2）{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)returnlong;else{long=long-next;short=short-next;}}returnNULL;}（3）由于每个表仅遍历一遍，因此算法时间复杂度为O(len1+len2)，空间复杂度为O(1)。四、练习题（一）选择题1．下述哪一条是顺序存储结构的优点？（A）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（C）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法