数据结构考研知识点总结

数据结构考研知识点总结数据结构考研真题及知识点解析考察目标1.理解数据结构的基本概念、基本原理和基本方法。2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3.能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C++或Java语言设计与实现算法的能力。第2章线性表一、考研知识点(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储2.链式存储3.线性表的应用二、考研真题(一)选择题近两年第2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、第9章和第10章的内容结合来出题。1((11年)设n是描述问题规模的非负整数，下面程序片段的时间复杂度是()。x=2;while(x<n/2)x=2*x;2A.O(logn)B.O(n)C.O(nlogn)D.O(n)分析:答案是A，此题考查的是算法时间复杂度的计算。可以放在第二章，实际这内容贯穿每一章内容中算法的度量。(二)综合题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表示当前遍历了多少结点，当i>k时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。(3)算法描述:intlocate(Linklistlist,intk){p1=list->link;p=list;i=1;while(p1){p1=p1->link;i++;if(i>k)p=p->next;//如果i>k，则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代表数-1组的前p个元素，b代表数组中余下的n-p个元素)，先将a逆置得到ab，再将b逆置得-1-1-1-1-1-1-1到ab，最后将整个ab逆置得到(ab)=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)若a<b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求舍弃的长度相等;3)若a>b，则舍弃序列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[m1<B[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)。三、考查重点1(线性结构的特点;2(线性表在顺序存储及链式存储方式下的基本操作及其应用;3(线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处;4(能分析所写算法的时间和空间复杂度。分析:线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。线性表一章小的知识点比较少，一般会出一个综合题，并且容易和第三章、第九章和第十章的内容结合来考，注意对基本知识的理解，能够利用书上的理论解决具体问题。学习过程中要注意多积累，多看、多写一些相关算法。四、练习题(一)选择题1(下述哪一条是顺序存储结构的优点,(A)A(存储密度大B(插入运算方便C(删除运算方便D(可方便地用于各种逻辑结构的存储表示2(下面关于线性表的叙述中，错误的是哪一个,(B)A(线性表采用顺序存储，必须占用一片连续的存储单元。B(线性表采用顺序存储，便于进行插入和删除操作。C(线性表采用链接存储，不必占用一片连续的存储单元。D(线性表采用链接存储，便于插入和删除操作。3(线性表是具有n个(C)的有限序列(n>0)。A(表元素B(字符C(数据元素D(数据项E(信息项4(若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用(A)存储方式最节省时间。A(顺序表B(双链表C(带头结点的双循环链表D(单循环链表5(某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用(D)存储方式最节省运算时间。A(单链表B(仅有头指针的单循环链表C(双链表D(仅有尾指针的单循环链表6(若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为(C)(1<=i<=n+1)。2A.O(0)B.O(1)C.O(n)D.O(n)7.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(C)。A(O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)8(线性表(a1,a2,„,an)以链接方式存储时，访问第i位置元素的时间复杂性为(C)。A(O(i)B(O(1)C(O(n)D(O(i-1)(二)综合题1(掌握线性表中几个最基本的操作算法(1)逆置操作顺序表的就地逆置voidreverse(SqList&A){for(i=1,j=A.length;i<j;i++,j--)A.elem[i]<->A.elem[j];//元素交换}链表的就地逆置voidLinkList_reverse(Linklist&L){p=L->next;q=p->next;while(q){r=q->next;q->next=p;p=q;q=r;}L->next->next=NULL;//修改第一个元素的指针值L->next=p;//修改表头结点指针值}(2)线性表的合并顺序表的合并:顺序存储的线性表la，lb的关键字为整数，元素非递减有序，线性表空间足够大，试编写高效算法，将lb中元素合并到la中，使新的la的元素仍非递减有序。分析:从后往前插入，避免移动元素voidunion(Sqlistla,Sqlistlb){m=la.length;n=lb.length;k=m+n;i=m;j=n;//循环指针赋值，从后往前比较while(i>0&&j>0){if(la.elem[i]>=lb.elem[j]){la.elem[k]=la.elem[i];k--;i--;}else{la.elem[k]=lb.elem[j];k--;j--;}}if(j>0)//判断lb是否为空{la.elem[k]=lb.elem[j];k--;j--;}la.length=m+n;}链表的合并:把元素递增排列的链表A和B合并为C，且C中元素递减排列，使用原结点空间。分析:本算法的思想是，按从小到大的顺序依次把A和B的元素插入新表的头部pc处，因为合并以后是逆序，因此采用头插法，最后处理A或B的剩余元素。LinkListUnion(LinkListA,LinkListB,LinkListC){pa=A->next;pb=B->next;C=A;A->next=null;while(pa!=null&&pb!=null)if(pa->data<=pb->data){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}else{r=pb->next;pb->next=C->next;C->next=pb;pb=r;while(pa!=null){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}while(pb!=null){r=pb->next;pb->next=C->next;C->next=pb;pb=r;}returnC;}(3)链表的拆分:设L为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，算法中不得申请新的结点空间。分析:利用原链表空间，在原链表的分解过程中新建链表。voiddiscreat(linklistL){s=L->next;p=L;p->next=NULL;q->next=NULL;while(s!=NULL){r=s->next;if(s->data%2!=0)//奇数链链接{s->next=p->next;p->next=s;}else//偶数链链接{s->next=q->next;q->next=s;}s=r;}}2(算法练习(1)试编写在带头结点的单链表中删除最小值结点的高效算法。voiddelete(linklistL){p=L->next;pre=L;q=p;while(p->next!=NULL)//找最小值元素，pre指向最小值的前驱{if(p->next->data<q->data){pre=p;q=p->next;}p=p->next;}pre->next=q->next;free(q);}分析:此算法的高效在于在循环过程中利用最小值结点的前驱指针进行比较，比较结束后直接保留了最小值结点的前驱，方便进行删除操作。(2)设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如xyx,xyyx都是中心对称。分析:判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论;否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。intdc(Linklisth,intn){?h是带头结点的n个元素单链表，链表中结点的数据域是字符。chars[];inti=1;?i记结点个数，s字符栈p=h->next;?p是链表的工作指针，指向待处理的当前元素。for(i=1;i<=n/2;i++)?链表前一半元素进栈。{s[i]=p->data;p=p->next;}i--;?恢复最后的i值if(n%2==1)p=p->next;?若n是奇数，后移过中心结点。while(p!=null&&s[i]==p->data){i--;p=p->next;}?测试是否中心对称。if(p==null)return1;?链表中心对称elsereturn0;?链表不中心对称}?算法结束。(3)已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。分析:在单链表中删除自第i个元素起的共len个元素，应从第1个元素起开始计数，记到第i个时开始数len个，然后将第i-1个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结点。这时应继续查到A的尾结点，得到删除元素后的A链表。再查B链表的第j个元素，将A链表插入之。插入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i，len和j的合法性。LinklistDelInsert(Linklistheada,Linklistheadb,inti,j,len){?heada和headb均是带头结点的单链表。if(i<1||len<1||j<1){printf(“参数错误\n”);exit(0);}?参数错，退出算法。p=heada;?p为链表A的工作指针，初始化为A的头指针k=0;?计数while(p!=null&&k<i-1)?查找第i个结点。{k++;p=p->next;}if(p==null){printf(“给的%d太大\n”,i);exit(0);}?i太大，退出算法q=p->next;?q为工作指针，初始指向A链表第一个被删结点。k=0;while(q!=null&&k<len){k++;u=q，q=q->next;free(u);}?删除结点，后移指针。if(k<len){printf(“给的%d太大\n”,len);exit(0);}p->next=q;?A链表删除了len个元素。if(heada->next!=null)?heada->next=null说明链表中结点均已删除，无需往B表插入{while(p->next!=null)p=p->next;?找A的尾结点。q=headb;?q为链表B的工作指针。k=0;?计数while(q!=null&&k<j-1)?查找第j个结点。{k++;q=q->next;}?查找成功时，q指向第j-1个结点if(q==null){printf(“给的%d太大\n”,j);exit(0);}p->next=q->next;?将A链表链入q->next=heada->next;?A的第一元素结点链在B的第j-1个结点之后}//iffree(heada);?释放A表头结点。}第3章栈和队列一、考研知识点(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用二、考研真题(一)选择题1.(09年)为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。A.栈B.队列C.树D.图分析:答案是B，此题可以认为考查队列的特点，也可以看做是考查四种数据结构的特点。2.(09年)设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队顺序是bdcfeag，则栈S的容量至少是()。A.1B.2C.3D.4分析:答案是C，此题考查栈的入栈和出栈操作和队列的入队和出队操作。3.(10年)若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是()。A.dcebfaB.cbdaefC.dbcaefD.afedcb分析:答案是D，此题考查栈的入栈和出栈操作，但题目出的不是太严谨，严格说应该是CD两个答案。4.(10年)某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是(C)A.bacdeB.dbaceC.dbcaeD.ecbad分析:答案是C，此题考查队列的入队和出队操作。5((11年)元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可进栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A.3B.4C.5D.6分析:答案是B，出栈序列必为d_c_b_a.e的顺序不定，在任意一个“_”上都有可能。6((11年)已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和对位元素。若初始时队列为空，且要求低1个进入队列的元素存储在[0]处，则初始时front和rear的值分别是A.0,0B.0，n-1C.n-1,0D.n-1,n-1分析:答案是B，插入元素时，front不变，rear+1，而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1，front为0(二)综合题10年考研综合题的第二题如果用解法二，可以认为考查了队列的基本操作，因为栈和队列本身是线性结构，所以考试时可以综合来考，和第2章的内容没有太明显的界限。三、考查重点1(栈和队列的特点，及其应用2(栈的顺序存储和链式存储的入栈和出栈操作，以及判断栈的空和满的条件;3(队列的顺序存储和链式存储的入队和出队操作，以及判断队列空和满的条件;4(理解栈与递归的关系，利于对以后章节(树和图)的学习和复习。分析:此章内容是线性表的深化，如果线性表理解的好，这一章就比较容易。这一章小的知识点比较多，一般容易出选择题，从09和10年的考研真题来看，主要是考查站和队列的特点及其应用、栈的入栈出栈操作和队列的入队出对操作、判断栈和队列的空与满的条件。一般不会单独出综合题，如果出综合题会将栈和队列作为其他结构中一个小环节出题，比如和线性表结合，作为实现递归的工具和二叉树结合等。四、练习题(一)选择题1.一个栈的输入序列为123„n，若输出序列的第一个元素是n，输出第i(1<=i<=n)个元素是(B)。A.不确定B.n-i+1C.iD.n-i2.若一个栈的输入序列为1,2,3,„,n，输出序列的第一个元素是i，则第j个输出元素是(D)。A.i-j-1B.i-jC.j-i+1D.不确定的3.输入序列为ABC，可以变为CBA时，经过的栈操作为(B)。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.循环队列存储在数组A[0..m]中，则入队时的操作为(D)。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)5.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为(B),A.1和5B.2和4C.4和2D.5和1(二)综合题这一章一般不会单独出综合题，和其他章节的结合在相关章节中有例题体现。第5章数组和广义表一、考研知识点特殊矩阵的压缩存储二、考研真题近两年此知识点没有出题。三、考查重点分析:重点考查特殊矩阵的压缩存储中矩阵中元素于在存储空间中地址的计算，只要掌握计算的方法就行，计算时需要特别特别主要矩阵首元素的下标值以及存储空间首元素的下标值。四、练习题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为(B)。A.13B.33C.18D.402.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(B)。A.BA+141B.BA+180C.BA+222D.BA+2253.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=(B)。A.808B.818C.1010D.10204.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665(即该元素下标i=66，j=65)，在B数组中的位置K为(B)。A.198B.195C.197D.1965.二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中()内的正确答案。(1)存放A至少需要(E)个字节;(2)A的第8列和第5行共占(A)个字节;(3)若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素(B)的起始地址一致。(1)A.90B.180C.240D.270E.540(2)A.108B.114C.54D.60E.150(3)A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]6.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1?i，j?n，且i?j)在B中的位置为(B)。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-1第6章树和二叉树一、考研知识点(一)树的概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造(三)树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树与二叉树的应用哈夫曼(Huffman)树和哈夫曼编码二、考研真题(一)选择题1.(09年)给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是()。A.LRNB.NRLC.RLND.RNL分析:答案是D，此题考查二叉树的遍历。2.(09年)已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则完全二叉树的结点个数最多是()。A.39B.52C.111D.119分析:答案是C，此题考察二叉树的性质2以及完全二叉树的概念。3.(09年)将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是()。I.父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III分析:答案是B，此题考查树与二叉树的转换，因为u是v的父结点，若v是u的左子树，则u与v是父子关系，若v是u的右子树，则u与v是兄弟关系。4.(10年)下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是()。分析:答案是D，此题考查二叉树的线索化。5.(10年)在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是()。A.41B.82C.113D.122分析:答案是B，此题考查二叉树的性质，利用二叉树的性质3的证明思路进行求解。6.(10年)对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是()。A.该树一定是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值分析:答案是A，此题考查哈夫曼树的构造，以及哈夫曼树的特点。7((11年)若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是()。A.257B.258C.384D.385分析:答案是C，考查二叉树的性质，叶结点个数为你n则度为2的结点个数为n-1，总结点个数为偶数，则度为1的结点个数为1，因此2n=768。8((11年)若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是()。A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1分析:答案是C，考查二叉树的遍历。此题可以用画图的方式进行判断。9((11年)已知一棵有2011个结点的树，其叶结点个数116，该树对应的二叉树中无右孩子的结点个数是()。A.115B.116C.1895D.1896分析:答案是D，此题考查二叉树和树的转换。考虑一种特殊的情况，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子。(二)综合题近两年没有考查二叉树的题目，如果考的话一般应该是二叉树的遍历和哈夫曼树以及哈夫曼编码。三、考查重点1(二叉树的定义与特点;2(二叉树的性质及应用;3(二叉树的遍历(遍历过程及算法实现);4(线索二叉树的构造;5(树的存储及树与二叉树的转换;6(哈夫曼树构造和哈夫曼编码。分析:此章知识点比较多，并且每个知识点都可能出题，因此要做到对每一个知识点的理解和掌握，选择题和综合题都可以出。虽然近两年没有出综合题，同学们也不要忽视，综合题一般会现在二叉树的遍历及其应用、树与二叉树的转换和哈夫曼树的构造及哈夫曼编码。四、练习题(一)选择题1.一个具有1025个结点的二叉树的高h为(C)。A(11B(10C(11至1025之间D(10至1024之间2(一棵二叉树高度为h，所有结点的度或为0或为2，则这棵二叉树最少有(B)结点。A(2hB(2h-1C(2h+1D(h+13.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(C)次序的遍历实现编号。A(先序B(中序C(后序D(从根开始按层次遍历4.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是(C)的二叉树。A(空或只有一个结点B(任一结点无左子树C(高度等于其结点数D(任一结点无右子树5.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为(C)。A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点6.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是(B)。A.0B.1C.2D.不确定(二)综合题1.二叉树的基本遍历算法(1)二叉树前序、中序、后序和层次遍历的非递归算法前序voidPreOrder(BitreeT){InitStack(S);Push(S,T);while(!StackEmpty(S)){pop(S,p);visit(p->data);if(p->rchild!=NULL)push(S,p->rchild);if(p->lchild!=NULL)push(S,p->lchild);}}中序voidInOrder(BitreeT){InitStack(S);p=T;while(!StackEmpty(S)||p!=NULL){while(p!=NULL){push(S,p);p=p->lchild;}if(!StackEmpty(S)){pop(S,p);visit(p->data);p=p->rchild;}}}后序voidPostOrder(BitreeT){Bitreestack[],p;inttag[],top=0;p=T;while(top>0||p!=NULL){while(p!=NULL){top++;stack[top]=p;tag[top]=0;p=p->lchild;}if(top>0){p=stack[top];while(tag[top]==1){top--;visit(p->data);p=stack[to}if(top>0){p=stack[top];p=p->rchild;tag[top]=1;}}}}层次voidLayerOrder(BitreeT){InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p->data);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}(2)二叉树遍历递归算法的应用求二叉树中叶子结点的数目intLeafCount_BiTree(BitreeT){if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;elsereturnLeaf_Count(T->lchild)+Leaf_Count(T>rchild);}交换所有结点的左右子树。voidBitree_Revolute(BitreeT){if(T!=NULL)T->lchild<->T->rchild;if(T->lchild)Bitree_Revolute(T->lchild);if(T->rchild)Bitree_Revolute(T->rchild);}求二叉树中以值为x的结点为根的子树深度。intGet_Sub_Depth(BitreeT,intx){if(T->data==x){printf("%d\n",Get_Depth(T));exit1;}else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);}}intGet_Depth(BitreeT){if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}判断两棵树是否相似的递归算法。intBitree_Sim(BitreeB1,BitreeB2){if(!B1&&!B2)return1;elseif(B1&&B2)return(Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))elsereturn0;}2.二叉树非递归遍历算法的应用(1)判断一二叉树是否为完全二叉树。intFull_Bitree(BitreeT){InitQueue(Q);flag=0;EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else{EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);}}return1;}(2)在二叉树中查找值为x的结点，编写算法输出x的所有祖先。voidPostOrder(BitreeT，intx){Bitreestack[],p;inttag[],top=0;p=T;while(top>0||p!=NULL){while(p!=NULL&&p->data!=x){top++;stack[top]=p;tag[top]=0;p=p->lchild;}if(p->data==x){printf(“”);for(i=1;i<=top;i++)printf(stack[i]->data);return;}while(tag[top]==1&&top>1)top--;if(top>0){p=stack[top];p=p->rchild;tag[top]=1;}}}分析:二叉树遍历算法的应用中关键的一个环节是分析要实现相关功能应该选择二叉树的哪一种遍历方式有利于实现，如以上两个例子中分别选用二叉树的层次遍历和后序遍历实现具体操作，主要对遍历算法稍加处理就可以实现了。3(从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。分析:树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。4(如果给出了一个二叉树结点的前序序列和中序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。分析:给定二叉树结点的前序序列和对称序(中序)序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边(设l个元素)表示左子树，若左边无元素，则说明左子树为空;右边(设r个元素)是右子树，若为空，则右子树为空。根据前序遍历中“根-—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。5(给定一组数列(15,8,10,21,6,19,3)分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。分析:考查哈夫曼树的构造和哈夫曼编码，过程略。编码的优点是采用前缀编码，出现频度最高的字符编码最短，减少编码长度，减少出错率。第7章图一、考研知识点(一)图的基本概念(二)图的存储及基本操作1.邻接矩阵法2.邻接表法(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用1.最小(代价)生成树2.最短路径3.拓扑排序4.关键路径二、考研真题(一)选择题1.(09年)下列关于无向连通图特性的叙述中，正确的是()。I.所有顶点的度之和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III分析:答案是A，此题考查无向连通图的特性。2.(10年)若无向图G-(V.E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是()。A.6B.15C.16D.21分析:答案是C，此题考查无向连通图的特点，解题时需要注意保证图G在任何情况下都是连通的这句话，这是关键。因为要保证图在任何情况下都连通，先考虑6个顶点全连通需要15条边，加上一个顶点后，加上一条边保证第七个顶点与图连通，因此至少需要16条边。3.(10年)对下图进行拓补排序，可以得到不同的拓补序列的个数是()。A.4B.3C.2D.1分析:答案是B，此题考查图的拓扑排序。4((11年)下列关于图的叙述中，正确的是()。I(回路是简单路径II(存储稀疏图，用邻接矩阵比邻接表更省空间III(若有向图中存在拓扑序列，则该图不存在回路A.仅IIB.仅I、IIC.仅IIID.仅I、III分析:答案是C，此题考查图的基本概念。回路对应于路径，简单回路对应于简单路径;II刚好说反了，III是拓扑有序的必要条件。(二)综合题1.(09年)带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法:(1)设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;(2)选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v;(3)重复步骤(2)，直到u是目标顶点为止。请问上述方法能否求得最短路径,若该方法可行，请证明之;否则，请举例说明。分析:此题考查最短路径的求解思路，只是没有直接考书上的最短路径的求解过程，而是换个角度考查对最短路径求解的理解。解答:该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A->B->C，事实上其最短路径为A->D->C。2((11年)已知有6个顶点(顶点编号为0-5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行优先为主序保存在如下的一维数组中。46???5???43??33要求:(1)写出图G的邻接矩阵A。2)画出有向带权图G。((3)求图G的关键路径，并计算该关键路径的长度。解答:此题考查图的邻接矩阵的存储以及关键路径的求解，同时考查了特殊矩阵的压缩存储，主要是考查的图的基本知识。(1)图G的邻接矩阵A如下所示。(2)有向带权图G如下图所示。(3)关键路径为0->1->2->3->5(如下图粗线所示)，长度为16。三、考查重点1(图的基本概念及特点;2.图的存储结构(邻接矩阵和邻接表);3(图的深度优先和广度优先遍历;4(图的应用(最小生成树的构造过程、拓扑序列的生成、最短路径和关键路径的求解过程)。分析:这一章的内容也比较多，尤其大的知识点比较多，容易出综合题，特别是图的应用。在理解最小生成树、拓扑排序、最短路径和关键路径的求解的同时要注意和具体问题结合，一般不会直接考，会和具体问题结合来考，例如09年的考研题。这一章考算法的可能性不大，但那两个最基本的遍历算法最好掌握。四、练习题(一)选择题1.无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，由顶点a开始对该图进行深度优先遍历，得到的顶点序列正确的是(D)。A(a,b,e,c,d,fB(a,c,f,e,b,dC(a,e,b,c,f,dD(a,e,d,f,c,b2.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是(D)。A(G中有弧<Vi，Vj>B(G中有一条从Vi到Vj的路径C(G中没有弧<Vi,Vj>D(G中有一条从Vj到Vi的路径3.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(B)。A(逆拓扑有序B(拓扑有序C(无序的4.下面哪一方法可以判断出一个有向图是否有环(回路)(AB)。A(深度优先遍历B.拓扑排序C.求最短路径D.求关键路径5.下面关于求关键路径的说法不正确的是(C)。A(求关键路径是以拓扑排序为基础的B(一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C(一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D(关键活动一定位于关键路径上(二)综合题1(给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?分析:每个顶点到其余各顶点的最短路径中最长的有n条，求这n条中最短的一条。2(设顶点a,b,c,d,e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离;?求每个村庄到其它村庄的最短距离;?乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近。分析:每个顶点到其余各顶点最短路径之和最短的一个。3(已知有6个村子，相互间道路的距离如图所示。拟合建一所小学，已知A处有小学生50人，B处40人，C处60人，C处20人，E处70人，F处90人，问小学应该建在哪个村子，是学生上学最为方便(走的总路程最短)。6261481733分析:此问题还是归为最短路径问题，考虑路径的总体状况。解答:先求出任意两点间的最短路径下表所示:ABCDEFA0267811B204569C640125D751014E862103F1195430将每行数字分别乘以各村小学生人数得下表:ABCDEFA0100300350400550B800160200240360C360240060120300D1401002002080E560420140700210F9908104503602700按列相加其总和最小的列所对应村子即是所求村子。4(某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的设备。若购置新设备，就要支付一定的购置费用;若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划使得总支付费用最小。表1设备年初价格第1年第2年第3年第4年第5年1111121213表2维修费用使用年数0-11-22-33-44-5维修费用5681118分析:此问题同样可以归为最短路径问题，假定每年年初都购置新设备，可以把每年年初作为一个顶点，任意两个顶点之间的连线表示设备的使用情况，权值用使用过程中的费用表示，这样可以构造一个图，在图中求从第一年年初到第五年末的最短路径，路径上的顶点就是设备更新计划。解答:设vi表示第i年购进一台新设备，(vi，vj)表示设备由第i年初使用到第j年初，权值表示使用费用，得到下图:594130221817161716232223313041在图中求由v1到v6的最短路径得到两条:v1-v3-v6和v1-v4-v6，因此设备的更新计划为在第1年和第3年年初更新设备或者是在第1年和第4年年初更新设备，总费用是53。5(下表给出了某工程各工序之间的优先关系和各工序所需时间(1)画出相应的AOE网(2)列出各事件的最早发生时间,最迟发生时间(3)找出关键路径并指明完成该工程所需最短时间.工序代号ABCDEFGHIJKLMN所需时间15105081540300151206015302040先驱工作----A,BBC,DBEG,IEIF,IH,J,KLG分析:此题考查关键路径的求解过程，求解过程略。第9章查找一、考研知识点(一)查找的基本概念(二)顺序查找法(三)折半查找法(四)二叉排序树(五)平衡二叉树+(六)B树及其基本操作、B树的基本概念(七)散列(Hash)表(八)查找算法的分析及应用二、考研真题(一)选择题1.(09年)下列二叉排序树中，满足平衡二叉树定义的是()。分析:答案是B，此题考查平衡二叉树的定义。2((09年)下列叙述中，不符合m阶B树定义要求的是()。A.根结点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接-分析:答案是D，此题考查B树的定义，题目出的不太严格，但是利用排除法可以得到答案。3.(10年)在下列所示的平衡二叉树中插入关键字48后得到新平衡二叉树，在新平衡二叉树中，关键字37所在节点的左、右结点中保存的关键字分别是()。A.13,48B.24,48C.24,53D.24,90分析:答案是C，此题考查平衡二叉树的调整过程。4.(10年)已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是()。A.4B.5C.6D.7分析:答案是A，此题考查有序表的折半查找的思想。5((11年)对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是()。A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,34分析:答案为A，此题考查二叉排序树的查找。在答案A中档找到91后向24查找，说明后面的数都比91小，而后面序列中出现了94，显然不对。6((11年)为提高散列表的查找效率，可以采取的正确措施是()。I(增大装填(载)因子II(设计冲突(碰撞)少的散列函数III(处理冲突(碰撞)时避免产生聚集(堆积)现象A.仅IB.仅IIC.仅IIID.仅II、III分析:答案是B，此题考查哈希表的构造和查找。I显然不对，III中的避免是不可能的，只能是减少。(二)综合题1.(10年)将关键字序列(7、8、30、11、18、9、14)散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列函数维:H(key)=(key×3)MODT，处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。问题:(1)请画出所构造的散列表;(2)分别计算等概率情况下，查找成功和查找不成功的平均查找长度。分析:此题考查哈希表的构造和冲突解决，以及装填因子的计算。解答:(1)由装载因子0.7，数据总数7个，得一维数组大小为7/0.7=10，存储空间长度为10，采用线性探测再散列法处理冲突，所构造的散列表为:01234567893071411818.9..(2)查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2三、考查重点1(顺序表的查找及平均查找长度;2(有序表的查找(折半查找)及平均查找长度;3(二叉排序数的构造及查找效率分析;4(平衡二叉树的构造;-+5(B树与B树的定义和特点;6(哈希表的构造(哈希函数构造方法:除留余数法，处理冲突的方法:开放定址法和链地址法)及平均查找长度。分析:这一章可以认为是线性表和二叉树在查找中的应用，利用前面所学知识来解决新的问题，重点是分析各种查找方式下的时间效率，选择题和综合题都可以出。综合题出哈希表的可能性比较多，也有可能出算法题，这样会和第2章线性表和第6章二叉树结合来考，总之是和前面的内容有联系的，一定要掌握各种查找方法的思想并能进行分析。四、练习题(一)选择题1(当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度(C)。A(必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减2.具有12个关键字的有序表，折半查找的平均查找长度(B)。A.3.1B.4C.2.5D.53(二叉查找树的查找效率与二叉树的((1)A)有关,在((2)C)时其查找效率最低。(1):A.高度B.结点的多少C.树型D.结点的位置(2):A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。4.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)。A.(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)5(假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测,(D)A(k-1次B.k次C.k+1次D.k(k+1)/2次6.散列表的地址区间为0-17，散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。(1)元素59存放在散列表中的地址是(D)。A.8B.9C.10D.11(2)存放元素59需要搜索的次数是(C)。A.2B.3C.4D.5(二)综合题1.采用哈希函数,(k)=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间,0..12,中对关键字序列22,41,53,46,30,13,1,67,51(1)构造哈希表(画示意图);(2)装填因子;(3)等概率下查找成功的和不成功的平均查找长度。分析:考查哈希表的构造过程。(1)散列地址0123456789101112关键字13225314167465130比较次数111212111(2)装填因子=9/13=0.7(3)ASLsucc=11/9ASLunsucc=29/132(已知长度为11的表(xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon)，按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。分析:考查平衡二叉树的构造过程，注意在构造时结点失去平衡先调整最下层的失衡结点。答案略。第10章内部排序一、考研知识点(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)气泡排序(bubblesort)(四)简单选择排序(五)希尔排序(shellsort)(六)快速排序(七)堆排序(八)二路归并排序(mergesort)(九)基数排序(十)各种内部排序算法的比较(十一)内部排序算法的应用二、考研真题(一)选择题1.(09年)已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后的小根堆是()。A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19分析:答案是A，此题考查堆得构造与调整。2.(09年)若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的