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

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

1、数据结构考研真题及知识点解析考察目标1.理解数据结构的基本概念、基本原理和基本方法。 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3.能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C+或Java语言设计与实现算法的能力。第2章 线性表一、考研知识点（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、考研真题（一）选择题近两年第2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、第9章和第10章的内容结合来出题。1（11

2、年）设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,

3、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转化成数组

4、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)/将数组中从

5、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语言描述算法，关键之处给出注释。解答：此题考查线性表的顺序存储，主要是线性表的基本操作的应用。做此题时

6、要把握算法的效率。（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) m

7、1=(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某线性表中最常用的操作是在

8、最后一个元素之后插入一个元素和删除第一个元素，则采用（ 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

9、）。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）线性表的合并顺序表

10、的合并：顺序存储的线性表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

11、=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-

12、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组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，算法中不得申请新的结点空

13、间。 分析：利用原链表空间，在原链表的分解过程中新建链表。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-

14、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都是中心对称。分析：判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈

15、。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。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

16、;若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个

17、结点。这时应继续查到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）prin

18、tf（“给的%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）pri

19、ntf（“给的%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.图分析：答案是

20、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，此题考查栈的入栈和出栈操作，但题目出

21、的不是太严谨，严格说应该是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

22、和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栈的顺序存储和链式存储的入栈和出栈操作，以及判断栈的空和满

23、的条件；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;