数据结构考研知识点总结.doc

数据结构考研真题及知识点解析考察目标1.理解数据结构的基本概念、基本原理和基本方法。 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3.能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C+或Java语言设计与实现算法的能力。第2章 线性表一、考研知识点（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、考研真题（一）选择题近两年第2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、第9章和第10章的内容结合来出题。1（11年）设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。 x=2; while(xk时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。（3）算法描述：int locate(Linklist list, int k)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个结点else printf(“%n”,p-data); return 1;2.（10年）设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P（0Pn）个位置，即将R中的数据由（X0 X1 Xn-1）变换为（Xp Xp+1 Xn-1 X0 X1 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）算法描述：void reverse(int R, int low, int high)/将数组中从low到high的元素逆置 int temp; for(i=0;i=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中较小的一半，要求舍弃的长度相等；在保留的两个升序序列中，重复过程1）-3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。（2）算法实现如下：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) m1=(s1+d1)/2; m2=(s2+d2)/2; if(Am1=Bm2) return Am1; else if(Am1Bm2) 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; return As10）。 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)。A. O(0) B. O(1) C. O(n) D. O(n2) 7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)8线性表（ a1,a2,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）。AO（i） BO（1） CO（n） DO（i-1）（二）综合题1掌握线性表中几个最基本的操作算法（1）逆置操作顺序表的就地逆置void reverse(SqList &A) for(i=1,j=A.length;ij;i+,j-)A.elemiA.elemj; /元素交换链表的就地逆置void LinkList_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的元素仍非递减有序。分析：从后往前插入，避免移动元素void union (Sqlist la, Sqlist lb)m=la.length; n=lb.length;k=m+n; i=m; j=n; /循环指针赋值，从后往前比较while (i0&j0)if (la.elemi=lb.elemj)la.elemk=la.elemi; k-; i-;elsela.elemk=lb.elemj; k-; j-; if(j0) /判断lb是否为空 la.elemk=lb.elemj; k-; j-; la.length=m+n;链表的合并：把元素递增排列的链表A和B合并为C，且C中元素递减排列，使用原结点空间。分析：本算法的思想是，按从小到大的顺序依次把A和B的元素插入新表的头部pc处，因为合并以后是逆序，因此采用头插法，最后处理A或B的剩余元素。LinkList Union( LinkList A, LinkList B, LinkList C) pa=A-next; pb=B-next; C=A;A-next=null; while(pa!=null & pb!=null) if(pa-datadata) 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; return C;（3）链表的拆分：设L为一单链表的头指针，单链表的每个结点由一个整数域 data和指针域next组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，算法中不得申请新的结点空间。 分析：利用原链表空间，在原链表的分解过程中新建链表。void discreat( linklist L)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）试编写在带头结点的单链表中删除最小值结点的高效算法。void delete ( linklist L)p=L-next; pre=L; q=p;while (p-next!=NULL) /找最小值元素，pre指向最小值的前驱if (p-next-datadata) 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都是中心对称。分析：判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。int dc（Linklist h,int n） h是带头结点的n个元素单链表，链表中结点的数据域是字符。char s; int i=1;i记结点个数， s字符栈p=h-next;p是链表的工作指针，指向待处理的当前元素。for（i=1;idata; p=p-next; i-; 恢复最后的i值if（n%2=1）p=p-next;若n是奇数，后移过中心结点。while（p!=null & si=p-data）i-; p=p-next;测试是否中心对称。if（p=null）return 1;链表中心对称else return 0;链表不中心对称算法结束。（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的合法性。Linklist DelInsert（Linklist heada, Linklist headb,int i,j,len）heada和headb均是带头结点的单链表。if（i1 | len1 | j1）printf（“参数错误n”）；exit（0）；参数错，退出算法。p=heada；p为链表A的工作指针，初始化为A的头指针k=0；计数while（p!=null & knext；if（p=null）printf（“给的%d太大n”,i）；exit（0）； i太大，退出算法q=p-next；q为工作指针，初始指向A链表第一个被删结点。k=0；while（q!=null & knext；free（u）； 删除结点，后移指针。if（knext=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 & knext；查找成功时，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.1 B.2 C.3 D.4分析：答案是C，此题考查栈的入栈和出栈操作和队列的入队和出队操作。3.（10年）若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（ ）。A.dcebfa B.cbdaef C.dbcaef D.afedcb分析：答案是D，此题考查栈的入栈和出栈操作，但题目出的不是太严谨，严格说应该是CD两个答案。4.（10年）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ C ）A.bacde B.dbace C.dbcae D.ecbad分析：答案是C，此题考查队列的入队和出队操作。5（11年）元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可进栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A.3 B.4 C.5 D.6分析：答案是B，出栈序列必为d_c_b_a.e的顺序不定，在任意一个“_”上都有可能。6（11年）已知循环队列存储在一维数组A0.n-1中，且队列非空时front和rear分别指向队头元素和对位元素。若初始时队列为空，且要求低1个进入队列的元素存储在0处，则初始时front和rear的值分别是A.0,0 B.0，n-1 C.n-1,0 D.n-1,n-1分析：答案是B，插入元素时，front不变，rear+1，而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1，front为0（二）综合题10年考研综合题的第二题如果用解法二，可以认为考查了队列的基本操作，因为栈和队列本身是线性结构，所以考试时可以综合来考，和第2章的内容没有太明显的界限。三、考查重点1栈和队列的特点，及其应用2栈的顺序存储和链式存储的入栈和出栈操作，以及判断栈的空和满的条件；3队列的顺序存储和链式存储的入队和出队操作，以及判断队列空和满的条件；4理解栈与递归的关系，利于对以后章节（树和图）的学习和复习。分析：此章内容是线性表的深化，如果线性表理解的好，这一章就比较容易。这一章小的知识点比较多，一般容易出选择题，从09和10年的考研真题来看，主要是考查站和队列的特点及其应用、栈的入栈出栈操作和队列的入队出对操作、判断栈和队列的空与满的条件。一般不会单独出综合题，如果出综合题会将栈和队列作为其他结构中一个小环节出题，比如和线性表结合，作为实现递归的工具和二叉树结合等。四、练习题（一）选择题1. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=idata); if (p-rchild!=NULL) push(S,p-rchild); if (p-lchild!=NULL) push(S,p-lchild); 中序void InOrder(Bitree T)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; 后序void PostOrder(Bitree T)Bitree stack, p; int tag, top=0; p=T; while(top0|p!=NULL) while(p!=NULL) top+; stacktop=p; tagtop=0; p=p-lchild; if(top0) p=stacktop; while(tagtop=1) top-; visit(p-data); p=stackto if(top0) p=stacktop; p=p-rchild; tagtop=1; 层次void LayerOrder(Bitree T) 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）二叉树遍历递归算法的应用求二叉树中叶子结点的数目int LeafCount_BiTree(Bitree T)if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; else return Leaf_Count(T-lchild)+Leaf_Count(Trchild);交换所有结点的左右子树。void Bitree_Revolute(Bitree T) if(T!=NULL) T-lchildT-rchild; if(T-lchild) Bitree_Revolute(T-lchild); if(T-rchild) Bitree_Revolute(T-rchild); 求二叉树中以值为x的结点为根的子树深度。int Get_Sub_Depth(Bitree T,int x)if(T-data=x) printf(%dn,Get_Depth(T); exit 1; elseif(T-lchild) Get_Sub_Depth(T-lchild,x);if(T-rchild) Get_Sub_Depth(T-rchild,x); int Get_Depth(Bitree T)if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; 判断两棵树是否相似的递归算法。int Bitree_Sim(Bitree B1,Bitree B2)if(!B1&!B2) return 1; else if(B1&B2) return(Bitree_Sim(B1-lchild,B2-lchild) &Bitree_Sim(B1-rchild,B2-rchild)else return 0;2.二叉树非递归遍历算法的应用（1）判断一二叉树是否为完全二叉树。int Full_Bitree(Bitree T)InitQueue(Q); flag=0; EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); return 1;（2）在二叉树中查找值为x的结点，编写算法输出x的所有祖先。void PostOrder(Bitree T，int x)Bitree stack, p;int tag, top=0; p=T;while(top0|p!=NULL)while(p!=NULL&p-data!=x) top+; stacktop=p; tagtop=0; p=p-lchild; if(p-data=x) printf(“”);for(i=1;idata);return;while(tagtop=1&top1)top-;if(top0) p=stacktop; p=p-rchild; tagtop=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.只有I B.只有II C.I和II D.I和III分析：答案是A，此题考查无向连通图的特性。2.（10年）若无向图G-（V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（ ）。A.6 B.15 C.16 D.21分析：答案是C，此题考查无向连通图的特点，解题时需要注意保证图G在任何情况下都是连通的这句话，这是关键。因为要保证图在任何情况下都连通，先考虑6个顶点全连通需要15条边，加上一个顶点后，加上一条边保证第七个顶点与图连通，因此至少需要16条边。3.（10年）对下图进行拓补排序，可以得到不同的拓补序列的个数是（ ）。A.4 B.3 C.2 D.1分析：答案是B，此题考查图的拓扑排序。4（11年）下列关于图的叙述中，正确的是（ ）。I回路是简单路径II存储稀疏图，用邻接矩阵比邻接表更省空间III若有向图中存在拓扑序列，则该图不存在回路A.仅II B.仅I、II C.仅III D.仅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为上三角矩阵，按行优先为主序保存在如下的一维数组中。4654333要求：（1）写出图G的邻接矩阵A。（2）画出有向带权图G。（3）求图G的关键路径，并计算该 关键路径的长度。解答：此题考查图的邻接矩阵的存储以及 关键路径的求解，同时考查了特