数据结构考研知识点总结培训讲学

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

2、而且可以和第3 章、第 9 章和第 10 章的内容结合来出题。1（ 11 年）设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。x=2;while(x<n/2) x=2*x;A. O(logn)B. O(n)C. O(nlogn)D. O(n2)分析：答案是 A，此题考查的是算法时间复杂度的计算。可以放在第二章，实际这内容贯穿每一章内容中算法的度量。（二）综合题1. （ 09 年）已知一个带有表头结点的单链表结点结构为(data,link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点 （ k 为

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

4、 指向当前遍历的结点，指针p 指向 p1 所指向结点的前k 个结点，如果p1 之前没有k个结点，那么p 指向表头结点。用整型变量i 表示当前遍历了多少结点，当i>k 时，指针 p随着每次遍历，也向前移动一个结点。当遍历完成时，p 或者指向表头结点，或者指向链表中倒数第k 个位置上的结点。（ 3）算法描述：word 可编辑资料收集于网络，如有侵权请联系网站删除int locate(Linklist list, int k)p1=list->link;p=list;i=1;while(p1)p1=p1->link;i+;if(i>k)p=p->next;/如果 i&g

5、t;k ，则 p 也后移if(p=list)return 0;/链表没有k 个结点elseprintf(“ %n”,p->data);return 1;2. （ 10 年）设将 n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R 中保有的序列循环左移P（ 0 P n）个位置，即将R 中的数据由（X0 X1Xn -1 ）变换为（ Xp Xp+1Xn -1X0X1Xp-1 ）要求：（ 1）给出算法的基本设计思想。（ 2）根据设计思想，采用 C或 C+或 JAVA语言表述算法，关键之处给出注释。（ 3）说明你所设计算法的时间复杂度和空间复杂度分析：此题考查

6、的是数组的操作， 线性表的顺序存储的核心就是数组， 因此此题实质上是考查的线性表的顺序存储的操作及其应用。做此题时要考虑算法的时间和空间复杂度。解法一：（ 1）算法的基本设计思想：可以将这个问题看做是把数组ab 转化成数组ba（ a 代表数组的前 p 个元素， b 代表数组中余下的 n-p个元素），先将 a 逆置得到 a-1 b，再将 b 逆置得-1 -1-1 -1-1 -1-1函数执行将数组元素逆置的到 a b ，最后将整个a b 逆置得到（ a b） =ba。设 reverse操作，对 abcdefgh 向左循环移动3（ p=3）个位置的过程如下：reverse(0,p-1)得到 cbad

7、efgh ；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<=(high-low)/2;i+)temp=Rlow+i;Rl0ow+i=Rhigh-i;word 可编辑资料收集于网络，如有侵权请联系网站删除Rhigh-i=temp;void converse(int R, int n, in

8、t 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) ，故所设计算法的时间复杂度为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 个位置的数称

9、为 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）算法的基本设计思想如下

10、：分别求出序列A 和 B 的中位数，设为a 和 b，求序列A 和 B 的中位数过程如下：1）若 a=b，则 a 或 b 即为所求中位数，算法结束；2）若 a<b，则舍弃序列A 中较小的一半，同时舍弃序列B 中较大的一半，要求舍弃的长度相等；3）若 a>b，则舍弃序列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,

11、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)word 可编辑资料收集于网络，如有侵权请联系网站删除if(s1+d1)%2=0s1=m1;d2=m2;elses1=m1+1;d2=m2;elseif(s1+d1)%2=0d1=m1;s2=m2;elsed1=m1+1;s2=m2;return As1<Bs2? As1:Bs2;（ 3）算法的时间复杂度为 O(logn) ，空间负责杂度为 O(1) 。三

12、、考查重点1线性结构的特点；2线性表在顺序存储及链式存储方式下的基本操作及其应用；3线性表的顺序存储及链式存储情况下，其不同和优缺点比较，及其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处；4能分析所写算法的时间和空间复杂度。分析：线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。线性表一章小的知识点比较少，一般会出一个综合题，并且容易和第三章、第九章和第十章的内容结合来考， 注意对基本知识的理解， 能够利用书上的理论解决具体问题。 学习过程中要注意多积累，多看、多写一些相关算法。四、练习题（一）选择题1下述哪一条是顺序存储结构的优

13、点？（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某线性表中最常用的操

14、作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（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）。word 可编辑资料收集于网络，如有侵权请联系网站删除A O(n) O(n)B. O(n) O(1)C. O(1) O(n)D. O(1) O(1)8线性表（ a1,a2,an ）以

15、链接方式存储时， 访问第 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.length;i<j;i+,j-)A.elemi<->A.elemj; /元素交换链表的就地逆置void LinkList_reverse(Linklist &L)p=L->next; q=p->next;while (q)r=q->next;q->next=p;p=

16、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 (i>0&&j>0

17、)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.length=m+n;word 可编辑资料收集于网络，如有侵权请联系网站删除链表的合并：把元素递增排列的链表A 和 B 合并为 C，且 C 中元素递减排列，使用原结点空间。分析：本算法的思想是， 按从小到大的顺序依次把A和 B 的元素插入新表的头部pc 处，因为合并以后是逆序，因此采用头插法，最后处理A 或 B 的剩余元素。L

18、inkList 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->data<=pb->data)r=pa->next; pa->next=C->next;C->next=pa; pa=r;elser=pb->next; pb->next=C->next;C->next=pb; pb=r;while(pa!=null

19、)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

20、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)word 可编辑资料收集于网络，如有侵权请联系网站删除p=L->next; pre=L

21、; 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 个字符是否中心对称。

22、例如xyx, xyyx都是中心对称。分析： 判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等， 则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。 这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。int dc（ Linklist h,int n） h 是带头结点的 n 个元素单链表，链表中结点的数据域是字符。char s; int i=1;i记结点个数，s 字符栈p=h->next;p是链表的工作指针

23、，指向待处理的当前元素。for （ i=1;i<=n/2;i+） 链表前一半元素进栈。 si=p->data; 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，编写一个过程

24、从单链表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（ Linkli

25、st heada, Linklist headb,int i,j,len） heada 和 headb 均是带头结点的单链表。if （ i<1 | len<1 | j<1）word 可编辑资料收集于网络，如有侵权请联系网站删除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 ）； e

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

27、;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 表头结点。第

28、 3章 栈和队列一、考研知识点（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用二、考研真题（一）选择题1. （ 09 年）为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区， 主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A.栈B.队列C.树D.图分析：答案是B，此题可以认为考查队列的特点，也可以看做是考查四种数据结构的特点。2. （ 09 年）设栈 S 和队列 Q的初始状态均为空，元素abcdefg 依次进入栈S。若每个元word 可编辑资料收集于网络，如有侵权请联系网

29、站删除素出栈后立即进入队列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 年）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（

30、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.n-1中，且队列非空时front和 rear分别指向队头元素和对位元素。 若初始时队列为空， 且要求低 1 个进入队列的元素存储在 0 处，则初始时 front

31、 和 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理

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

33、+1C.iD.n-i2. 若一个栈的输入序列为 1,2,3, ,n ，输出序列的第一个元素是 i ，则第 j 个输出元素是（ D ）。A. i-j-1B. i-jC. j-i+1D.不确定的3.输入序列为ABC，可以变为CBA时，经过的栈操作为（B）。word 可编辑资料收集于网络，如有侵权请联系网站删除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. 循环队列存储在数组A0.m中，则入队时的操作为（D）。A

34、. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. 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 章 数组和广义表一、考研知识点特殊矩阵的压缩存储二、考研真题近两年此知识点没有出题。三、考查重点分析：重点考查特殊矩阵的

35、压缩存储中矩阵中元素于在存储空间中地址的计算，只要掌握计算的方法就行， 计算时需要特别特别主要矩阵首元素的下标值以及存储空间首元素的下标值。四、练习题1. 设有一个 10 阶的对称矩阵 A，采用压缩存储方式， 以行序为主存储， a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则a85 的地址为（ B ）。A.13B.33C.18D.402.设有数组 Ai,j，数组的每个元素长度为3 字节， i 的值为 1到 8 ，j 的值为 1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A5 ，8 的存储首地址为(B) 。A.BA+141B.BA+180C.BA+222D

36、.BA+2253.假设以行序为主序存储二维数组A=array1.100， 1.100 ，设每个数据元素占2个存储单元，基地址为10，则 LOC5，5= （ B）。A.808B.818C.1010D.10204.将一个 A1.100， 1.100 的三对角矩阵，按行优先存入一维数组B1298 中， A中元素A6665（即该元素下标i=66 ， j=65 ），在 B 数组中的位置 K 为（ B ）。A. 198B. 195C. 197D. 1965.二维数组 A 的元素都是 6 个字符组成的串，行下标i 的范围从0 到 8，列下标 j的范圈从 1 到 10。从供选择的答案中选出应填入下列关于数组存

37、储叙述中（）内的正确答案。（ 1）存放 A 至少需要（ E ）个字节；（ 2）A 的第 8 列和第 5 行共占（ A ）个字节；（ 3）若 A 按行存放，元素 A8 ， 5 的起始地址与 A 按列存放时的元素（ B ）的起始地址一致。（ 1） A.90 B.180 C.240 D.270 E.540（ 2） A.108 B.114 C.54D.60E.150（ 3） A.A8,5 B.A3,10C.A5,8D. A0,9word 可编辑资料收集于网络，如有侵权请联系网站删除6. 设 A 是 n*n 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组B1.n(n+1)/2

38、中，对上述任一元素aij(1i ，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 代表

39、根结点的左子树，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的父结点

40、与v 的父结点是兄弟关系A. 只有 IIB.I和 IIC.I和 IIID.I、II和 III分析：答案是B，此题考查树与二叉树的转换，因为u 是 v 的父结点，若v 是 u 的左子树，则 u 与 v 是父子关系，若v 是 u 的右子树，则u 与 v 是兄弟关系。word 可编辑资料收集于网络，如有侵权请联系网站删除4. （ 10 年）下列线索二叉树中（用虚线表示线索） ，符合后序线索树定义的是（）。分析：答案是D，此题考查二叉树的线索化。5. （ 10 年）在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点， 10 个度为 3 的结点， 1个度为 2 的结点， 10 个度为 1 的结

41、点，则树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

42、.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，此

43、题考查二叉树和树的转换。考虑一种特殊的情况，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115 个叶结点有右孩子。word 可编辑资料收集于网络，如有侵权请联系网站删除（二）综合题近两年没有考查二叉树的题目， 如果考的话一般应该是二叉树的遍历和哈夫曼树以及哈夫曼编码。三、考查重点1二叉树的定义与特点；2二叉树的性质及应用；3二叉树的遍历（遍历过程及算法实现）；4线索二叉树的构造；5树的存储及树与二叉树的转换；6哈夫曼树构造和哈夫曼编码。分析：此章知识点比较多，并且每个知识点都可能出题，因此要做到对每一个知识点的理解和掌握，选择题和综合题都可以出。 虽然近两年没有出综合题，同学们也不要

44、忽视，综合题一般会现在二叉树的遍历及其应用、树与二叉树的转换和哈夫曼树的构造及哈夫曼编码。四、练习题（一）选择题1. 一个具有1025 个结点的二叉树的高h 为（ C）。A11B10C11 至 1025 之间D10 至 1024 之间2一棵二叉树高度为h，所有结点的度或为0 或为 2，则这棵二叉树最少有( B )结点。A 2hB 2h-1C 2h+1D h+13. 对二叉树的结点从1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(C)次序的遍历实现编号。A先序B中序C后序D从根开始按层次遍历4. 某二叉树的前序序列和

45、后序序列正好相反，则该二叉树一定是（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）二叉树前序、中序、后序和层次遍历的非递归算法word 可编辑资料收集于网络，如有侵权请联系网站删除前序void PreOrder(Bitr

46、ee T)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);中序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

47、,p);visit(p->data);p=p->rchild;后序void PostOrder(Bitree T)Bitree stack, p;int tag, top=0; p=T;while(top>0|p!=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=stackto if(top>0)word 可编辑资料收集于网络，如有侵权请联系网站删除 p=sta

48、cktop; 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;elsereturn Leaf_Count(T->lchild)+Leaf_Count(T>rchild);交换所有结点的左右子树。void Bitree_Revolute(Bitree T)if(T!=NULL)T->lchild<->T->rchild;if(T->lchild) Bitr