第6章 树和二叉树练习题及答案

一、判断题

（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个

非空指针域。

（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（×）5.二叉树中所有结点个数是2-1，其中k是树的深度。（应2-1） （×）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）

（√）8.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个

为空指针。

（√）9.具有12个结点的完全二叉树有5个度为2的结点。 (? ) 10、哈夫曼树中没有度为1的结点，所以必为满二叉树。 (? )11、在哈夫曼树中，权值最小的结点离根结点最近。 (? )12、线索二叉树是一种逻辑结构。

（√ ）13、深度为K的完全二叉树至少有2K-1个结点。

(√ )14、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。 (√ )15、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。 (╳ )16、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 （√）17、在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。 （√）18、二叉树的遍历操作实际上是将非线性结构线性化的过程 （√）19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。 （╳）20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。 二、填空

1． 由３个结点所构成的二叉树有 5 种形态。

2. 线索二叉树的左线索指向其_前驱_____，右线索指向其__后继____。 3． 一棵具有257个结点的完全二叉树，它的深度为 9 。

4、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_69_____。

5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.

6. 一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为 2 。

k-1

i

7. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。

8. 在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==null && p->rchlid==null 。 三、选择题

1．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为（C）

A）3 B）2 C）4 D）5 2．二叉树是非线性数据结构，所以（ C ）。

Ａ、它不能用顺序存储结构存储; Ｂ、它不能用链式存储结构存储; Ｃ、顺序存储结构和链式存储结构都能存储; Ｄ、顺序存储结构和链式存储结构都不能使用

3.具有n(n>0)个结点的完全二叉树的深度为（ C ）。

(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(n)+1? 4．把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。 （Ａ）唯一的 （Ｂ）有多种

（Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子 5.线索二叉树是一种（ C ）结构。

A． 逻辑 B． 逻辑和存储 C． 物理 D．线性

6、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（ A） A、98

B、99

C、50

D、48

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

8、将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（C） A、48

B、49

C、50

D、51

9、引入二叉线索树的目的是（ A ）

A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除 C、为了能方便的找到双亲 D、使二叉树的遍历结果唯一

10．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）

A．9 B．11 C．15 D．不确定 11． 一棵树深度为K的完全二叉树至少有（ C ）个结点 A．2 –1 B. 2 –1 C. 2 D. 2

k

k-1

k-1

k

12．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ） A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 13. 有关二叉树下列说法正确的是（ B ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 14. 一个具有1025个结点的二叉树的高h为（ C ）

A．11 B．10 C．11至1025之间 D．10至1024之间 15．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点

A．2h B．2h-1 C．2h+1 D．h+1 16．对于有n 个结点的二叉树, 其高度为（D ）

A．nlog2n B．log2n C．?log2n+1 D．不确定 17. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的先序遍历是（ D ）。

A．acbed B．decab C．deabc D．cedba 18．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( C )遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次 19．在下列存储形式中，哪一个不是树的存储形式？（ D ）

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 20． 在下列关于二叉树的叙述中，正确的是（ D ）

①只有一个结点的二叉树度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 21．若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C )

A.X的双亲 B.X的右子树中最左的结点

C.X的左子树中最右结点 D.X的左子树中最右叶结点

22.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ）

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

23.在线索化二叉树中，t所指结点没有右子树的充要条件是（A ）。 A、t->Rtag==1 B、t->Rchild==NULL C、t->Rtag==1且t->Rchild==NULL D、以上都不对

24、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点

数至少为（B）。 A．2h C．2h+1

B．2h-1 D．h+1

25、如右图所示二叉树的中序遍历序列是（B）。 A．abcdgef B．dfebagcC．dbaefcg

D．defbagc

26、设a和b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（D）。 A．a是b的左孩子

B．b是a的右孩子

D．以上三项均可

C．a是b左子树上结点或b是a右子树上结点

27、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（C）个。 A． 45

B．15

C．16

D．31

28、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的遍历策略分为先序、中序和后序遍历。这里把由树转化得到的二叉树叫做这棵树对应的二叉树。以下结论（A）是正确的。

A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C．树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D．以上都不对

29、如下图所示的4棵二叉树，（C）不是完全二叉树。

30、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。 A．2m-1 A．2k-1

B．2m

C．2m+1

D．4m D．2K-1

31、二叉树的第k层的结点数最多为（ D ）

B．2K+1

C．2K-1

32、设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。 A．9

B．10

C．11

D．12

33、一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有（ B ）个结点。 A．n-2

B．n-1

C．n+1

D．n+2

34、对于一棵深度为4的三叉树，最多有（ C ）个结点。

A．30

(A) 3

B．36 (C) 5

C．40 D．54

35、设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（B ）。

(B) 4

(D) 1

四、简答题

1.给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 2、已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 解：

3、给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。 解：

或：

WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2 =207 [注]：哈夫曼树的左右子树可以互换。

4. 把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B E C K F H D L G I M J

5、画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。

6、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。 解：哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32

（100） （40） （60） 19 21 32 （28）

（17） （11）

0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 7 10 6 0 1 2 3 7 10 6 （5） 2 3

WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61

本文来源：https://www.bwwdw.com/article/mimo.html