数据结构第6章 树习题+答案

E F D G A B / + + * - C * 第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D )

A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE

2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G

3. 在下述结论中，正确的是（ D ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右

子树可任意交换;

④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③

B ．②③④

C ．②④

D ．①④

4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ）

A ．m-n

B ．m-n-1

C ．n+1

D ．条件不足，无法确定

5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。

A ．M1

B ．M1+M2

C ．M3

D ．M2+M3

6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D )

A ．不确定

B ．2n

C ．2n+1

D ．2n-1

7．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点

A ．2h

B ．2h-1

C ．2h+1

D ．h+1

8. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ）

A ．?logn ?+1

B ．logn+1

C ．?logn ?

D ．logn-1

9．深度为h 的满m 叉树的第k 层有（ A ）个结点。(1=

A ．m k-1

B ．m k -1

C ．m h-1

D ．m h -1

10. 一棵树高为K 的完全二叉树至少有（ C ）个结点

A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k

11. 利用二叉链表存储树，则根结点的右指针是（ C ）。

A ．指向最左孩子

B ．指向最右孩子

C ．空

D ．非空

12．树的后根遍历序列等同于该树对应的二叉树的( B ).

A. 先序序列

B. 中序序列

C. 后序序列

13．在下列存储形式中，哪一个不是树的存储形式？（ D ）

A ．双亲表示法

B ．孩子链表表示法

C ．孩子兄弟表示法

D ．顺序存储表示法

14．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK ；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： C

A 、 E

B 、 F

C 、 G

D 、 H

15．对于前序遍历与中序遍历结果相同的二叉树为（1）F;

对于前序遍历和后序遍历结果相同的二叉树为（2）B。

先序遍历序列与后序遍历序列正好相反的二叉树为（3）E,F。

A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉

树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所

有结点只有右子树的二叉树 G.只有一个叶子结点的二叉树

16在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺

序（ B ）

A．都不相同B．完全相同 C．先序和中序相同，而与后序不同 D．中

序和后序相同，而与先序不同

17．由3 个结点可以构造出多少种不同的二叉树？（ D ）

A．2 B．3 C．4 D．5

18．下面几个符号串编码集合中，不是前缀编码的是（ B ）。

A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}

19. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在

一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的

右孩子在数组A中的位置是（ D ）

A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，

无法确定

二、填空题

1．二叉树由(1)根结点(2)左子树(3)右子树三个基本单元组成。

2．在二叉树中，指针p所指结点为叶子结点的条件是__p->lchild==null &&

p->rchlid==null__。

3．深度为H 的完全二叉树至少有_(1) 2H-1__个结点；至多有_(2) 2H-1__个结

点；H和结点总数N之间的关系是 (3) H=?log2N?+1 __。

4．设只含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为__

2K-1____,最小结点数为___ k___。

5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是___99___。

6．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3

的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1) n1-1 _个结点，右

子树中有_(2)_ n2+n3 个结点。

7．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为

2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)80__，字符

c的编码是_(2)_001(不唯一)_。

8．下面是求二叉树高度的类C写的递归算法试补充完整

[说明] 二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh

和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树

的高，hi最后返回。

height(p)

{if ((1)p___)

{if(p->lchild==null) lh=(2)__0_; else lh=(3)_ height(p->lchild)_;

if(p->rchild==null) rh=(4)0_; else rh=(5) height(p->rchild)_;

if (lh>rh) hi=(6)_ lh+1_；else hi=(7)__rh+1_____;

}

else hi=(8)_0______;

return hi;

}//

9．下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为数据域 data，左、右孩子域 lchild、rchild和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。

inordethread(thr)

{p=thr->lchild;

while ((1) p<>thr ____)

{ while((2) p->ltag=0 _) p= (3) p->lchild ___;

printf(p->data);

while((4)p->rtag=1 && p->rchild!=thr) { p=(5)_p->rchild_；printf(p->data);}

p= (6)_ p->rchild;}

}

四、应用题

1．若一棵树中有度数为1至m的各种结点数为n

1,n

2

,…,n

m

(n

m

表示度数为m

的结点个数)请推导出该树中共有多少个叶子结点n

的公式。

设树的结点数为n，分枝数为B，则下面二式成立

n=n0+n1+n2+…+n m (1)

n=B+1= 1+n1+2n2+…+mn m (2)

由(1)和(2)得叶子结点数n

=1+0*n1+1*n2+2*n3+...(m-1)*n m

2. ①试找出满足下列条件的二叉树

1）先序序列与后序序列相同 2）中序序列与后序序列相同

3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同

先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：

（１）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树

（２）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．（３）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（４）若中序序列与层次遍历序列相同，则或为空树，

或为任一结点至多只有右子树的二叉树

3.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来。试求出空格处的内容，并画出该二叉树。

先序序列: _ B F I C E H G

中序序列：D K F I A E J C

后序序列： K F B H J G A

4.已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。

5．已知一棵树如图所示。要求：

（１）给出树的先根遍历序列和后根遍历序列；

（２）画出树的孩子-兄弟表示法；

（３）将该树转化为二叉树。

6.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。

字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，

D:001

A

B C D

H

G

F

E

K

J

I

数据结构复习题

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×） 第1章 （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（×）（3）数据元素是数据的最小单位。 （×）（4）数据项是数据的基本单位。 （×）（5）数据的逻辑结构和数据的存储结构是相同的。 （√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。（√）（7）数据的物理结构是指数据在计算机内实际的存储形式。 （√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（9）数据的存储结构是数据的逻辑结构的存储映像。 （√）（10）算法是对解题方法和步骤的描述。 第2章 （×）（1）链表的物理存储结构具有同链表一样的顺序。 （×）（2）链表的每个结点都恰好包含一个指针域。 （√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。 （×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （√）（6）数组元素的存储位置是下标的线性函数。 （√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。 （×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。 （×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。 （×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。 第3章 （√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。 （×）（2）快速排序在任何情况下都比其它排序方法速度快。 （√）（3）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。

数据结构-习题-第六章-树

数据结构-习题-第六章-树和二叉树

E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e ）转为后缀表达式 后为（ ）【中山大学 1999 一、5】 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的 结点个数分别为4，2，1，1 则T 中的叶子数 为（ ） A ．5 B ．6 C ．7

D．8 【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．② ④ D．①④ 6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】 7. 树是结点的有限集合，它（ (1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结

《园林树木学》复习题及答案

《园林树木学》复习题及答案 一、名词解释并举例 1.绿色叶类树木:指有些树种,其叶常年均为绿色。如小蜡树、柏木、女贞等 2.双色叶类树木:指有些树种,其叶背与叶表的颜色显著不同,在微风中常形成光影闪烁变化的观赏效果。例如:银白杨、胡颓子、广玉兰、沙棘、石灰花楸等。 3.秋色叶类树木:指凡在秋季叶色有显著变化的树种。例如:银杏、水杉、五角枫、枫香、南天竹、二球悬铃木等。 4.春色叶类树木:指凡就是新发出嫩叶均为异色的树木类。如石楠、香椿、天竺桂、桂花等。 5.常色叶类树木:指有些树的变种或变型,其叶常年均成异色。例如:紫叶李、金叶鸡爪槭、金心黄杨、变叶木、紫叶李、紫叶小檗等。 6、斑色叶类树木:绿叶上具有其她颜色的斑点或花纹。如变叶木、金边大叶黄杨、金心鹅掌柴、洒金桃叶珊瑚等。 7、星散花相:指花或花序数量较少,且散布于全树冠各部。例如:鹅掌楸、白兰花、六月雪等。 8、团簇花相:指花或花序形大而多,就全树而言,花感较为强烈,但每朵花或花序的花簇仍能充分表现其特色,如绣球、琼花等 9、独生花相:指花大而单一,着生在树干顶端。例如:苏铁、四川苏铁、凤尾丝兰等。 10、覆被花相:指花或花序着生于树冠的表层,形成覆伞状。例如:泡桐、广玉兰、凤凰木、栾树等。 11、密满花相:指花或花序数量较多,密生全树各小枝,使树冠形成一个整体的大花团,花感最为强烈。例如:梅、火棘、樱花、垂丝海棠、桃、李等。 12、线条花相:花排列于小枝上,形成长形的花枝,如紫荆、龙牙花等。 13、干生花相:花着生在茎干上,如棕榈类、可可、木菠萝等。 14、纯式花相:在开花时,叶尚未展开,全树只见花不见叶。如白玉兰、泡桐、紫荆等 15、衬式花相:在展叶后开花,全树花叶相衬。如桂花、女贞、广玉兰、木芙蓉等。 二、单项选择题 1.雄蕊不形成柱状或筒状的植物就是( A ); A.香樟Ｂ.扶桑Ｃ.吊钟花Ｄ.梧桐 2.紫薇的瓣爪就是指( B ); A.边缘皱波状Ｂ.基部具柄Ｃ.边缘具长刺Ｄ.边缘撕裂状 3.石榴原产地在( A )环境;

数据结构叉树习题含答案

第6章树和二叉树 1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A．唯一的Ｂ．有多种 C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子 （2）由3 个结点可以构造出多少种不同的二叉树？（） A．2 B．3 C．4 D．5 （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B． 500 C．254 D．501 （4）一个具有1025个结点的二叉树的高h为（）。 A．11 B．10 C．11至1025之间 D．10至1024之间（5）深度为h的满m叉树的第k层有（）个结点。(1=

数据结构和算法习题及答案解析

第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构 B．存储实现 C．逻辑结构 D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列 B. 链表 C.有序表 D. 链栈 （6）以下数据结构中，（）是非线性数据结构 A．树 B．字符串 C．队 D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i

树和二叉树习题数据结构

树和二叉树习题数据结 构 标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N]

习题六树和二叉树一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树

D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点

数据结构 习题 第六章 树和二叉树

第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为 ( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ ） A ．5 B ．6 C ．7 D ．8 【南京理工大学 2000 一、8 （1.5分）】 5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 【南京理工大学2000 一、 17（1.5分）】 7. 树是结点的有限集合，它（ (1）)根结点，记为T 。其余结点分成为m （m>0）个(（2）) 的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T 的子结点（1≤i ≤m ）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个 不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定 义为1，其他结点的层数等于其父结点所在层数加上1。令T 是一棵二叉树，Ki 和Kj 是T 中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi 和λKj ，当关系式│ λKi-λKj │≤1一定成立时，则称T 为一棵（(5)）。供选择的答案： （1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1 个以上 （2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A. 权 B.维数 C.次数 D.序 （5） A. 丰满树 B.查找树 C.平衡树 D.完全树 【上海海运学院1999二、 2(5分）】 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A ．9 B ．11 C ．15 D ．不确定 【北京工商大学2001一.7(3 分)】 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2

树结构习题及答案

第5章树 【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。 解： （1）叶子结点有：B 、D 、F 、G 、H 、I 、 J 。 （2）非终端结点有：A 、C 、E 。 （3）每个结点的度分别是：A 的度为4，C 的度为2，E 的度为3，其余结点的度为0。 （4）树的深度为3。 【例5-7】如图5-5所示的二叉树，要求： （1）写出按先序、中序、后序遍历得到的结点序列。 （2）画出该二叉树的后序线索二叉树。 解： （1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA b a c d e f 图5-5 A B C D E F G H I J 图5-4

（2）其后序线索二叉树如图5-6所示。 5％、、G 、H 的 3.假定一棵三叉树的结点数为50，则它的最小高度为（3.C ）。 A.3 B.4 C.5 D.6 4.在一棵二叉树上第4层的结点数最多为（4.D ）。 第六步： 25 30 9 9 18 7 12 8 15 27 43 图5-13

A.2 B.4 C.6 D.8 5.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（5.B）。 A.R[2i+1] B.R[2i] C.R[i/2] D.R[2i-1] 6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（6.D）。 A.24 B.48 C.72 D.53 7.线索二叉树是一种（7.C）结构。 A.逻辑 B.逻辑和存储 C.物理 D.线性 8.线索二叉树中，结点p没有左子树的充要条件是（8.B）。 A.p->lc=NULL B.p->ltag=1 C.p->ltag=1且p->lc=NULL D.以上都不对 9.设 10. A. 11. A. 12. A. B. C. D. 13. A. C. 14. A. 15. A. C. 1. 2. 3. 4. 5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（5.×） 6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（6.√） 7.根据任意一种遍历序列即可唯一确定对应的二叉树。（7.√） 8.满二叉树也是完全二叉树。（8.√） 9.哈夫曼树一定是完全二叉树。（9.×） 10.树的子树是无序的。（10.×） 三、填空题 1.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。1.3，4，6，1，1，2，A，F，G

数据结构第6章树练习

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 { InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 一、下面是有关二叉树的叙述，请判断正误 1.二叉树中每个结点的两棵子树的高度差等于1。（） 2.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（） 3.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i —1个结点。（） 4.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（） 5.具有12个结点的完全二叉树有5个度为2的结点。（） 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 6．二叉树是度为2的有序树（） 7．完全二叉树一定存在度为1的结点（） 8．深度为K的二叉树中结点总数≤2k-1（） 9．由一棵二叉树的先序序列和后序序列可以惟一确定它（） 10．完全二叉树中，若一个结点没有左孩子，则它必是树叶（）

11．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（）12．完全二叉树的存储结构通常采用顺序存储结构（） 13．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）14．在中序线索二叉树中，每一非空的线索均指向其祖先结点（） 二、填空 1. 一棵具有２５７个结点的完全二叉树，它的深度为。 2. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 3．深度为H 的完全二叉树至少有_____________个结点；至多有_____________个结点4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。 5. n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。 三、单项选择题 1．有关二叉树下列说法正确的是（） A）二叉树的度为2 B）一棵二叉树的度可以小于2 C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2 2．二叉树的第I层上最多含有结点数为（） A）2I B）2I-1-1 C）2I-1D）2I-1 3．具有10个叶结点的二叉树中有（）个度为2的结点 A）8 B）9 C）10 D）11 4．在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0； ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A）①②③B）②③④C）②④D）①④ 5．由3 个结点可以构造出多少种不同的二叉树？（） A）2 B）3 C）4 D）5 6．引入二叉线索树的目的是（）

数据结构第六章树和二叉树习题及答案

习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是

(完整版)数据结构练习题(含答案)

数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i

树结构习题及答案

第5章 树 【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。 解: (1)叶子结点有:B 、D 、F 、G 、H 、I 、J 。 (2)非终端结点有:A 、C 、E 。 (3)每个结点的度分别就是:A 的度为4,C 的度为2,E 的度为3,其余结点的度为0。 (4)树的深度为3。 【例5-2】一棵度为2的树与一棵二叉树有什么区别？ 解:度为2的树有两个分支,但分支没有左右之分;一棵二叉树也有两个分支,但有左右之 分,左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别？ 解:区别有两点: (1)二叉树的一个结点至多有两个子树,树则不然; (2)二叉树的一个结点的子树有左右之分,而树的子树没有次序。 : :空树或者任一结点均无左孩子的非空二叉树; :空树或者任一结点均无右孩子的非空二叉树; :空树或仅有一个结点的二叉树。 【例5-7】如图5-5所示的二叉树,要求: (1)写出按先序、中序、后序遍历得到的结点序列。 (2)画出该二叉树的后序线索二叉树。 解: b a c d e f 图5-5 A B C D E F G H I J 图5-1 图5-4

(1) 先序遍历序列:ABDEFC 中序遍历序列:DEFBAC 后序遍历序列:FEDBCA (2)其后序线索二叉树如图5-6所示。 C、D、 的结点 图5-13 第六步: 30 27 43

A、4 B、5 C、6 D、7 2、假设在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为(2、 B )个。 A、15 B、16 C、17 D、47 3、假定一棵三叉树的结点数为50,则它的最小高度为(3、C )。 A、3 B、4 C、5 D、6 4、在一棵二叉树上第4层的结点数最多为( 4、D)。 A、2 B、4 C、6 D、8 5、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1、、n],结点R[i]若有左孩子,其左孩子的编号为结点(5、B)。 A、 R[2i+1] B、 R[2i] C、 R[i/2] D、 R[2i-1] 6、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为(6、 D )。 A、24 B、48 C、72 D、53 7、线索二叉树就是一种( 7、C)结构。 A、逻辑 B、逻辑与存储 C、物理 D、线性 8、线索二叉树中,结点p没有左子树的充要条件就是( 8、B)。 A、 p->lc=NULL B、 p->ltag=1 C、 p->ltag=1 且p->lc=NULL D、以上都不对 9、设n , m 为一棵二叉树上的两个结点,在中序遍历序列中n在m前的条件就是(9、B)。 A、 n在m右方 B、 n在m 左方 C、 n就是m的祖先 D、 n就是m的子孙 10、如果F就是由有序树T转换而来的二叉树,那么T中结点的前序就就是F中结点的 (10、B )。 A、中序 B、前序 C、后序 D、层次序 11、欲实现任意二叉树的后序遍历的非递归算法而不必使用栈,最佳方案就是二叉树采用( 11、A)存储结构。 A、三叉链表 B、广义表 C、二叉链表 D、顺序 12、下面叙述正确的就是( 12、D)。 A、二叉树就是特殊的树 B、二叉树等价于度为2的树 C、完全二叉树必为满二叉树 D、二叉树的左右子树有次序之分 13、任何一棵二叉树的叶子结点在先序、中序与后序遍历序列中的相对次序(13、A )。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 14、已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为(14、B )。 A、1 B、2 C、3 D、4 15、根据先序序列ABDC与中序序列DBAC确定对应的二叉树,该二叉树( 15、A )。 A、就是完全二叉树 B、不就是完全二叉树 C、就是满二叉树 D、不就是满二叉树 二、判断题 1、二叉树中每个结点的度不能超过2,所以二叉树就是一种特殊的树。(1、×) 2、二叉树的前序遍历中,任意结点均处在其子女结点之前。( 2、√)

数据结构课后习题及解析第六章

第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7．n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。

9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。

数据结构-树练习题

数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74

数据结构第六章树和二叉树练习及答案

一、选择题 1、设T是一棵树，T’是对应于x的二叉树，则T的先根次序遍历和T’的（）次序遍历相同。 A、先根 B、中根 C、后根 D、以上都不是 2、 3、若二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（）。 A、acbed B、decab C、deabc D、cedba 4、具有35个结点的完全二叉树的深度为（） A、5 B、6 C、7 D、8 5、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子结点编号为（） A、98 B、99 C、50 D、48 6、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。 A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无左孩子 7、二叉树在线索化后，仍不能有效求解的问题是（） A、先根线索二叉树中求先根后继 B、中根线索二叉树中求中根后继 C、中根线索二叉树中求中根前驱 D、后根线索二叉树中求后根后继 8、在线索化二叉树中，t所指结点没有左子树的充足条件是（） A、t-lchild==NULL B、t->ltag==1 C、t->ltag==1&&t->lchild==NULL D、以上都不对 9、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（） A、2h B、2h-1 C、2h+1 D、h+1 10、深度为5的二叉树至多有（）个结点。 A、16 B、32 C、31 D、10 11、在一非空二叉树的中序遍历序列中，根结点的右边（） A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点 12、树最适合用来表示（） A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 13、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（） A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 14、设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（） A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙 15、线索二叉树是一种（）结构 A、逻辑 B、逻辑和存储 C、物理 D、线性 16、森林的后根遍历序列与其对应二叉树的（）遍历序列一致。 A、先根 B、后根 C、中根 D、不可能 二、填空题 1、由一棵二叉树后序序列和（中序）可唯一确定这棵二叉树。 2、含有n个结点的二叉树用二叉链表表示时，有（N+1）个空链域。 3、有m个叶子结点的哈夫曼树有（2*M-1）个结点。

树和二叉树练习题答案

第5章树和二叉树练习题答案 一、下面是有关二叉树的叙述，请判断正误 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.满二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.设一棵完全二叉树有700个结点，则共有350个叶子结点。 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6.一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。 7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按L R N次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B。 解：法1：先由已知条件画图，再后序遍历得到结果； 法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前 序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中， 根结点在最前面，是B；则后序遍历中B一定在最后面。 法3：递归计算。如B在前序序列中第一，中序中在中间（可知左 右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同 样处理，则问题得解。

数据结构习题第六章树和二叉树

一、选择题 1 .已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式 为（） ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A .①②③ B .②③④ C .②④ D .①④ 6. 设森林F 对应的二叉树为 B ，它有m 个结点，B 的根为p,p 的右子树结点个数为 n,森 林F 中第一棵树的结点个数是（ ） A . m-n B . m-n-1 C . n+1 D .条件不足，无法确定 【南京理工大学 2000 一、17 （1.5 分）】 7. 树是结点的有限集合， 它（（1 ））根结点，记为T 。其余结点分成为 m （m>0 ）个（（2）） 的集合T1 , T2 ,…，T m ，每个集合又都是树，此时结点 T 称为Ti 的父结点，Ti 称为T 的子结点（1 < i < m ）。一个结点的子结点个数称为该结点的 （（3））。二叉树与树是两个 不同的概念，二叉树也是结点的有限集合，它 （（4 ））根结点。可以把树的根结点的层数定 义为1，其他结点的层数等于其父结点所在层数加上 1。令T 是一棵二叉树，Ki 和Kj 是T 中子结点数小于 2的结点中的任意两个，它们所在的层数分别为入 Ki 和入Kj ，当关系式丨入 Ki-入Kj | < 1 一定成立时，则称 T 为一棵（（5））。供选择的答案： （1 ）⑷A.有0个或1个 B.有0个或多个 C.有且只有一个 D.有1个或1 个以上 C.允许叶结点相交 D .允许树枝结点相交 C.次数 D.序 C.平衡树 D.完全树【上海海运学院 1999 、2（5分）】 10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） C . 15 D .不确定 【北京工商大学 2001 .7(3分)】 第六章 树和二叉树 (2) A. 互不相交 B.允许相交 (3) A. 权 B.维数 (5) A. 丰满树 B.查找树 A . -A+B*C/DE -+A*BC/DE 【北京航空航天大 学 B. -A+B*CD/E -+*ABC/DE D. 1999 一、3 （2 分）】 2 .算术表达式a+b* （c+d/e ）转为后缀表达式后为（ A . ab+cde/* B . abcde/+*+ C . abcde/*++ 3. 设有一表示算术表达式的二叉树（见下图） ， 它所表示的算术表达式是（ ） 【南京理工大学1999 A. A*B+C/（D*E ）+（F-G ） C. （A*B+C ）/（D*E+ 4. 设树T 的度为4, 子数为（ ） A . 5 【南京理工大学 (F-G )) 其中度为1 , B . 6 2000 、20 (2分)】 B. (A*B+C)/(D*E)+(F-G) D. A*B+C/D*E+F-G 2, 3和4的结点个数分别为 5. 在下述结论中，正确的是（ ①只 有一个结点的二叉树的度为 交换； C . 7 （1.5分）】 ）【南京理工大学 1999 （1分）】 0;②二叉树的度为2 ; ③二叉树的左右子树可任意 8.若一棵二叉树具有 B . 11