数据结构考研知识点总结-

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

2、出题。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;

3、 否则，只返回0。要求：(1) 描述算法的基本设计思想；(2) 描述算法的详细实现步骤；(3) 根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C+或 JAVA语 言实现)，关键之处给出简要注释。分析：此题考查线性表的链式存储，主要是线性表的基本操作的应用。做此题时要把握算法的效率。(1) 算法基本思想如下：从头到尾遍历单链表，并用指针p指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。(2) 详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针p1指向当前遍历的结点，指针 p指向p1所指向结点的前k个结点，如果p1之前没

4、有k 个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少结点，当i>k时，指针p随着每次遍历，也向前移动一个结点。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。(3) 算法描述：int locate(Li nklist list, i nt k)p1=list->li nk;p=list;i=1;while(pl)p1=p1->li nk;i+;if(i>k)p=p->next; /如果 i>k，贝U p 也后移if(p=list)return 0;/链表没有 k 个结点elseprintf(“ n” ,p->data

5、);return 1;2. ( 10年)设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移 P ( 0< P< n)个位置，即将 R中的数据由(XO X1Xn-1 )变换为(Xp Xp+1Xn -1 X0 X1Xp-1 )要求:(1) 给出算法的基本设计思想。(2) 根据设计思想，采用 C或C+或 JAVA语言表述算法，关键之处给出注释。(3) 说明你所设计算法的时间复杂度和空间复杂度分析：此题考查的是数组的操作，线性表的顺序存储的核心就是数组，因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时

6、间和空间复杂度。解法一：(1) 算法的基本设计思想： 可以将这个问题看做是把数组 ab转化成数组ba( a代表数 组的前p个元素，b代表数组中余下的 n-p个元素)，先将a逆置得到a-1 b，再将b逆置得 到a1 b，最后将整个a"b1逆置得到(a b1) 一1 =ba。设reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3 (p=3)个位置的过程如下: reverse(0,p-1)得至Ucbadefgh；reverse(p,n-1)得至Ucbahgfde;reverse(0,n-1)得至Udefghabc。注：reverse中，两个参数分别表示数组中待转换元

7、素的始末位置。(2) 算法描述:void reverse(i nt R, int low, int high)/将数组中从low到high的元素逆置int temp;for(i=0;i<=(high-low)/2;i+) temp=Rlow+i;Rl0ow+i=Rhigh-i;Rhigh-i=temp;void con verse(i nt R, int n, int p)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),故所

8、设计算法的时间复杂度为O(n)，空间复杂度为 O(1)。解法二：算法思想：创建大小为p的辅助数组S,将R中前p个整数依次暂存在 S中，同时将R中后n-p个整数左移，然后将 S中暂存的p个数依次放回到 R中的后续单元。时间复杂度为O(n)，空间复杂度为O(p) o3. (11年)一个长度为L ( L>=1 )的生序列S,处在第rL/2个位置的数称为 S的中位 数，例如，若序列 S仁(11,13,15,17,19),贝U S1的中位数是15,两个序列的中位数是含它 们所有元素的升序序列的中位数。例如，若S2= (2,4,6,8,20),则S1和S2的中位数是11。现在有两个等长升序序列A和B

9、，试设计一个在时间和空间方面都尽可能高效的算法，找出两个序列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

10、中较小的一半，要求舍弃的 长度相等；在保留的两个升序序列中，重复过程1) -3 ),直到两个序列中只含一个元素时为止，较小者即为所求的中位数。(2) 算法实现如下：int M_search(i nt A,i nt B.i nt n)in t 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(Am1<Bm2)if(s1+d1)%2=0s1=m1;d2=m2;elses 仁 m1

11、+1;d2=m2;elseif(s1+d1)%2=0d1=m1;s2=m2;elsed 仁 m1+1;s2=m2;return As1<Bs2? As1:Bs2;(3) 算法的时间复杂度为O(logn)，空间负责杂度为0(1)。三、考查重点1 线性结构的特点；2 线性表在顺序存储及链式存储方式下的基本操作及其应用；3.线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处；4能分析所写算法的时间和空间复杂度。分析：线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。线性表一章小的

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

13、3. 线性表是具有 门个(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<=

14、i<=n+1)。A. O(0) B. O(1)C. O( n)D. O(n2)7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(C )。A. O(n) 0(n)B. O(n) 0(1) C. O(1) O(n) D. O(1) O(1)&线性表(a1,a2,an )以链接方式存储时，访问第i位置元素的时间复杂性为(C )。A. O (i) B . O (1) C . O (n) D . O (i-1)(二) 综合题1掌握线性表中几个最基本的操作算法(1 )逆置操作顺序表的就地逆置void reverse(SqList &A)for(i=1,j=A.le

15、ngth;i<j;i+,j-)A. elemi<->A.elemj; /元素交换链表的就地逆置void Lin kList_reverse(L in klist &L)p=L->n ext; q=p->n ext;while (q)r=q->n ext;q->n ext=p;p=q; q=r;L-> next-next=NULL; /修改第一个元素的指针值L-> next=p; /修改表头结点指针值(2)线性表的合并顺序表的合并：顺序存储的线性表la , lb的关键字为整数，元素非递减有序，线性表空间足够大，试编写高效算法，将lb中

16、元素合并到la中，使新的la的元素仍非递减有序。分析：从后往前插入，避免移动元素void union (Sqlist la, Sqlist lb)m=laen gth; n=lb.len gth;k=m+n; i=m; j=n; /循环指针赋值，从后往前比较while (i> 0&&j>0)if (la.elemi>=lb.elemj)la.elemk=la.elemi; k-; i-;elsela.elemk=lb.elemj; k-; j-; if(j>0) / 判断lb是否为空 la.elemk=lb.elemj; k-; j-;la.le ngt

17、h=m+n;链表的合并：把元素递增排列的链表A和B合并为C,且C中元素递减排列，使用原结点空间。分析：本算法的思想是，按从小到大的顺序依次把A和B的元素插入新表的头部pc处,因为合并以后是逆序，因此采用头插法，最后处理A或B的剩余元素。LinkList Union( LinkList A, LinkList B, LinkList C)pa=A->n ext; pb=B->n ext; C=A;A- >n ext=n ull;while(pa!=null && pb!=null) if(pa->data<=pb->data)r=pa->

18、n ext; pa->n ext=C->n ext;C->n ext=pa; pa=r;else r=pb->n ext; pb->n ext=C->n ext; C->n ext=pb; pb=r;while(pa!=null)r=pa->n ext; pa->n ext=C->n ext; C->n ext=pa; pa=r; while(pb!=null)r=pb->n ext; pb->n ext=C->n ext; C->n ext=pb; pb=r; return C;(3) 链表的拆分：设L

19、为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链 和一个偶数链，算法中不得申请新的结点空间。分析：利用原链表空间，在原链表的分解过程中新建链表。void discreat( lin klist L)s=L->n ext; p=L;p->next=NULL; q->next=NULL;while(s!=NULL) r=s->n ext;if( s->data%2!=0) / 奇数链链接 s->n ext=p->n ext; p->n ext=s; else /

20、 偶数链链接s->n ext=q->n ext; q->n ext=s;s=r;2 算法练习(1) 试编写在带头结点的单链表中删除最小值结点的高效算法。void delete ( lin klist L)p=L->n ext; pre=L; q=p;while (p->next!=NULL) /找最小值元素，pre指向最小值的前驱if (p->n ext->data<q->data) pre=p; q=p->n ext;p=p->n ext;pre->n ext=q->n ext;free (q);分析：此算法的高效

21、在于在循环过程中利用最小值结点的前驱指针进行比较，比较结束后直接保留了最小值结点的前驱，方便进行删除操作。(2) 设单链表的表头指针为 h，结点结构由data和next两个域构成，其中data域为 字符型。写出算法 dc(h,n),判断该链表的前n个字符是否中心对称。例如 xyx, xyyx 都是 中心对称。分析：判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在 处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈

22、中弹出元素不等时，结论为链表非中心对称，结束算法的执行。int dc( Linklist h,int n ) / h是带头结点的n个元素单链表，链表中结点的数据域是字符。char s; int i=1;/i记结点个数，s字符栈p=h-> next; /p是链表的工作指针，指向待处理的当前元素。for (i=1;i<=n/2;i+)/链表前一半元素进栈。 si=p->data; p=p->n ext; i- ; /恢复最后的i值if (n%2=1 p=p->next; /若n是奇数，后移过中心结点。while (p!=null && si=p->

23、;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的尾结点，

24、得到删除元素后的 A链表。再查B链表的第j个元素，将A链表插入之。插入和删除中应注意前驱后继关系， 不能使链表“断链”。另外，算法中应判断i , len和j的合法性。Linklist DelInsert( Linklist heada, Linklist headb,int i,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 &

25、;& 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<le n)k+ ; u=q, q=q->next ; free (u) ; /删除结点，后移指针。if (k<len )printf("给的 d太大 n” ,len ); exit (0); p->next=q ;/

26、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-

27、>next=q->next ; /将 A 链表链入q-> next=heada-> next ;/A的第一元素结点链在 B的第j-1个结点之后/if free (heada); /释放 A表头结点。第3章栈和队列一、考研知识点(一) 栈和队列的基本概念(二) 栈和队列的顺序存储结构(三) 栈和队列的链式存储结构(四) 栈和队列的应用二、考研真题(一)选择题1. (09年)为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓 冲区，主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。A. 栈 B. 队列 C. 树

28、 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,此题考查栈的入

29、栈和出栈操作，但题目出的不是太严谨，严格说应该 是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年）已知循环队列存储在一维数组 A0.

30、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 , fro nt为0（二）综合题10年考研综合题的第二题如果用解法二，可以认为考查了队列的基本操作，因为栈和 队列本身是线性结构，所以考试时可以综合来考，和第2章的内容没有太明显的界限。三、考查重点1. 栈和队列的特点，及其应用2栈

31、的顺序存储和链式存储的入栈和出栈操作，以及判断栈的空和满的条件；3队列的顺序存储和链式存储的入队和出队操作，以及判断队列空和满的条件；4. 理解栈与递归的关系，利于对以后章节（树和图）的学习和复习。分析：此章内容是线性表的深化，如果线性表理解的好，这一章就比较容易。这一章小的知识点比较多，一般容易出选择题，从09和10年的考研真题来看，主要是考查站和队列的特点及其应用、栈的入栈出栈操作和队列的入队出对操作、判断栈和队列的空与满的条件。一般不会单独出综合题，如果出综合题会将栈和队列作为其他结构中一个小环节出题，比如和线性表结合，作为实现递归的工具和二叉树结合等。四、练习题（一）选择题1. 一个栈

32、的输入序列为 123n,若输出序列的第一个元素是n,输出第i （1<=i<=n ）个元素是（B ）。A.不确定 B.n-i+1 C.i D.n-i2. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（D ）。A. i-j-1 B. i-j C. j-i+1 D.不确定的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

33、,pop,pop4. 循环队列存储在数组A0.m中，则入队时的操作为( D ) oA. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)5. 若用一个大小为 6的数组来实现循环队列，且当前rear和front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为(B )?A. 1 和 5 B. 2和 4 C. 4和 2 D. 5 和 1(二)综合题这一章一般不会单独出综合题，和其他章节的结合在相关章节中有例题体现。第5章数组和广义表一、考研

34、知识点特殊矩阵的压缩存储二、考研真题近两年此知识点没有出题。三、考查重点分析：重点考查特殊矩阵的压缩存储中矩阵中元素于在存储空间中地址的计算，只要掌握计算的方法就行，计算时需要特别特别主要矩阵首元素的下标值以及存储空间首元素的下 标值。四、练习题1. 设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为(B )。A.13 B.33 C.18D.402. 设有数组Ai,j,数组的每个元素长度为 3字节，i的值为1到8 , j的值为1到10,数组从内存首地址 BA开始顺序存放，当用以列为主存放时，元素A5 , 8的

35、存储首地址为(B)。A.BA+141B.BA+180C.BA+222D.BA+2253. 假设以行序为主序存储二维数组A=array1.100 , 1.100，设每个数据元素占2个存储单元，基地址为10,则LOC5, 5= ( B )oA.808B.818C.1010D.10204. 将一个A1.100 , 1.100的三对角矩阵，按行优先存入一维数组B1298中，A中元素A6665 (即该元素下标i=66 , j=65 )，在B数组中的位置 K为(B )。A. 198 B. 195 C. 197 D. 1965. 二维数组A的元素都是6个字符组成的串，行下标 i的范围从0到8,列下标j的 范

36、圈从1到10o从供选择的答案中选出应填入下列关于数组存储叙述中()内的正确答案。(1) 存放A至少需要(E )个字节；(2) A的第8列和第5行共占(A )个字节；(3) 若A按行存放，元素 A8 , 5的起始地址与 A按列存放时的元素(B )的起始地 址一致。(1) A.90 B.180C.240D.270E.540(2) A.108 B.114C.54D.60E.150(3) A.A8,5 B.A3,10C.A5,8 D. A0,96. 设A是n*n的对称矩阵，将 A的对角线及对角线上方的元素以列为主的次序存放在 一维数组B仁n（n+1）/2中，对上述任一元素aij（1 <i , j

37、 <n,且i wj）在B中的位置为（B ）。A.i（i-l）/2+j B.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代表根结点的右子树。若遍历

38、后的结点序列为3,7,5,6,124，则其遍历方式是（）。A.LRN B.NRL C.RLN D.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和IIC和IIID、II和II

39、I分析：答案是B,此题考查树与二叉树的转换，因为u是v的父结点，若v是u的左子树，则u与v是父子关系，若 v是u的右子树，则u与v是兄弟关系。4. （10年）下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）。AiB；分析：答案是 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）个权值均不相同的字符构成哈

40、夫曼树，关于该树的叙述中，错误的是（）。A. 该树一定是一棵完全二叉树B. 树中一定没有度为1的结点C. 树中两个权值最小的结点一定是兄弟结点D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值分析：答案是 A此题考查哈夫曼树的构造，以及哈夫曼树的特点。7. （11年）若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）。A.257B.258C.384D.385分析：答案是C,考查二叉树的性质，叶结点个数为你n则度为2的结点个数为n-1 ,总结点个数为偶数，则度为 1的结点个数为1，因此2n=768。& （11年）若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3

41、,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个叶结点有右孩子。共116个叶弟卢（二）综合题近两年没有考查二叉树的题目，如果考的话一般应该是二叉树的遍历和哈夫曼树以及哈

42、夫曼编码。三、考查重点1. 二叉树的定义与特点；2. 二叉树的性质及应用；3二叉树的遍历（遍历过程及算法实现）；4. 线索二叉树的构造；5树的存储及树与二叉树的转换；6. 哈夫曼树构造和哈夫曼编码。分析：此章知识点比较多， 并且每个知识点都可能出题，因此要做到对每一个知识点的理解和掌握，选择题和综合题都可以出。虽然近两年没有出综合题，同学们也不要忽视，综合题一般会现在二叉树的遍历及其应用、树与二叉树的转换和哈夫曼树的构造及哈夫曼编 码。四、练习题（一）选择题1. 一个具有1025个结点的二叉树的高 h为（C ）。A. 11 B . 10 C . 11 至 1025 之间 D . 10 至 10

43、24 之间2. 一棵二叉树高度为 h,所有结点的度或为 0或为2，则这棵二叉树最少有（B ） 结 点。A. 2h B . 2h-1 C . 2h+1 D . h+13. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（C） 次序的遍历实现编号。A.先序B .中序 C .后序 D .从根开始按层次遍历4. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（C ）的二叉树。A.空或只有一个结点B .任一结点无左子树C.高度等于其结点数D .任一结点无右子树5. 若X是二叉中序线索树中一个有左孩子的结

44、点，且X不为根，则X的前驱为（C ）。A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点6. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是（B ）。A.0B.1C.2 D.不确定（二）综合题1.二叉树的基本遍历算法（1）二叉树前序、中序、后序和层次遍历的非递归算法前序void PreOrder(Bitree T)Ini tStack(S);Push(S,T);while(!StackEmpty(S)Pop(S,p);visit(p->data);if (p->rchild!=NULL) push(S,p->rchild)

45、;if (p->lchild!=NULL) push(S,p->lchild);中序void InO rder(Bitree T)Ini tStack(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(top>0|p!=

46、NULL)while(p!=NULL) top+; stacktop=p; tagtop=0; p=p->lchild; if(top>0)p=stacktop;while(tagtop=1) top-; visit(p->data); p=stacktoif(top>0) p=stacktop; p=p->rchild; tagtop=1;层次void LayerOrder(Bitree T)Ini tQueue(Q);En Queue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p->data);if(p-&g

47、t;lchild) En Queue(Q,p->lchild); if(p->rchild) En Queue(Q,p->rchild);(2) 二叉树遍历递归算法的应用 求二叉树中叶子结点的数目 int LeafCou nt_BiTree(Bitree T)if(!T) return 0; /空树没有叶子else if(!T->lchild && !T->rchild) return 1;elsereturn Leaf_Cou nt(T->lchild)+Leaf_Cou nt(T>rchild);交换所有结点的左右子树。void B

48、itree_Revolute(Bitree T)if(T!=NULL)T->lchild<->T->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) prin tf("%dn",Get_Depth(T);exit 1; elseif(T->lchild)

49、Get_Sub_Depth(T->lchild,x); if(T->rchild) Get_Sub_Depth(T->rchild,x);int Get_Depth(Bitree T)if(!T) return 0;elsem=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return (m>n?m:n )+1;判断两棵树是否相似的递归算法。int Bitree_Sim(Bitree B1,Bitree B2)if(!B1 &&!B2) retur n 1;else if(B1 &&B

50、2)return(Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild) else return 0;2. 二叉树非递归遍历算法的应用(1) 判断一二叉树是否为完全二叉树。int Full_Bitree(Bitree T)Ini tQueue(Q); flag=0;En Queue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);if(!p) flag=1;else if(flag) retur n 0;else En Queue(Q,p->

51、;lchild);En Queue(Q,p->rchild);return 1;x的所有祖先。(2) 在二叉树中查找值为x的结点，编写算法输出void PostOrder(Bitree T ， int x)Bitree stack, p;int tag, top=0; p=T;while(top>0|p!=NULL)while(p!=NULL&&p->data!=x) top+; stacktop=p; tagtop=0; p=p->lchild; if(p->data=x)printf(“”)；for(i=1;i<=top;i+) prin

52、 tf(stacki->data);return;while(tagtop=1 &&top>1)top-;if(top>0) p=stacktop; p=p->rchild; tagtop=1;分析：二叉树遍历算法的应用中关键的一个环节是分析要实现相关功能应该选择二叉树 的哪一种遍历方式有利于实现，如以上两个例子中分别选用二叉树的层次遍历和后序遍历实现具体操作，主要对遍历算法稍加处理就可以实现了。3. 从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。分析：树的孩子兄弟链表表示法和二叉树

53、二叉链表表示法，本质是一样的，只是解释不同，也就是说树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。4. 如果给出了一个二叉树结点的前序序列和中序序列，能否构造出此二叉树？若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树？若能，请证明之。若不能，请给出反例。分析：给定二叉树结点的前序序列和对称序(中序)序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边(设I个元素)表示左子树，若左边无元素，则说明左子树为空；右边(设r个元素

54、)是右子树，若为空，则右子树为空。根据前序遍历中“根-左子树一右子树”的顺序，则由从第二元素开始的I个结点序列和中序序列根左边的I个结点序列构造左子树，由前序序列最后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. 边数大于顶点个