《树和二叉树》习题

一、选择题

1．对于先序遍历和中序遍历结果相同的二叉树为（ BF ）；对于先序遍历和后序遍历结果相同的二叉树为（ B ）

A.一般二叉树 B.只有根结点的二叉树 C.根结点无左孩子的二叉树 D.根结点无右孩子的二叉树 E.所有结点只有左孩子的二叉树 F.所有结点只有右孩子的二叉树。

2．下列关于哈夫曼树的叙述错误的是( D)。

A．哈夫曼树的根结点的权值等于所有叶结点的权值之和 B．具有n个叶结点的哈夫曼树共有2n-l个结点 C．哈夫曼树是带权外路径长度最短的二叉树 D．哈夫曼树一个结点的度可以是0、1或2

3．设T2是由树T转换得到的二叉树，则T中结点的后序序列是T2结点的( B )。 A．先序序列 B．中序序列 C．后序序列 D．层次序列 4．设有一个度为3的树，其叶结点数为n0，度为1的结点数为nl，度为2的结点数为n2， 度为3的结点数为n3，则n0与nl，n2，n3满足关系（ B ）。 A． n0 =n2+1 B．n0=n2+2*n3+1 C．n0=n2+n3+1 D．n0= nl+n2+n3

二、填空题

1．一棵有124个叶结点的完全二叉树，最多有______248__个结点。 在有n个结点的哈夫曼树中，其叶子结点数为__2/N+1_______。

2．若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是_____13__。

3．已知某二叉树的先序序列为ABDECF，中序序列为DBEAFC。则其后序序列为_____DEBFCA_____。

4. 二叉树结点数n与边数e的关系为__N=E+1__________。

5. 己知二叉排序树的先序序列，___能_____唯一确定该二叉排序树。

6. 完全二叉树采用_顺序__存储结构，满足存储空间少，方便的查找任意结点的双亲与孩子。

三、综合题

1．设有n个结点的二叉树，度为2的结点数为n2,度为l的结点数为n1，叶结点数为n0，试分别写出哈夫曼树、完全二叉树和单枝二叉树n1的取值。

答案：哈夫曼树：0 在哈夫曼树中，只能有度为0或2 的结点是严格二叉树 完全二叉树：当n为奇数时，度为1的结点树为0 当n为偶数时，度为1的结点树为1 单支二叉树：n1=n-1

2．找出满足下列条件的二叉树： （1）先序和中序的访问序列相同；

根节点没有左孩子的二叉树或者只有根结点 （2）中序和后序的访问序列相同； 只有左孩子的二叉树

（3）先序和后序的访问序列相同； 只有根节点的二叉树

3．已知二叉树的中序遍历序列为DEBAFCG，后序遍历序列为EDBFGCA，试画出该二叉树。 A

B C

D G F E

4. 可以生成下图所示的二叉排序树的关键字初始序列有几种？试写出其中的任意4种。

分析过程：{8，4，？，？，？}2^3=6 {8,9,4,?,?}2 2+6=8

5. 设al，a2，a3是不同的关键字，且al

6．以权值分别为3,4,7,9,20的a,b,c,d,e五个元素作为叶结点构造二叉树，回答：

（1）如何构造路径长度最短的二叉树，图示出一棵路径长度最短二叉树，并计算出路径长度

分析过程：最短路径长度，所以为完全二叉树：（不考虑权值） 3 4 7

9 20

（9+20）*3+（3+4+7）*2=115

（2）如何构造带权路径长度最短的二叉树，图示出一棵带权路径长度最短的二叉树，并计算出带权路径长度 43 23 20

14 9

7 7

3 4

最短带权路径：3*4+4*4+7*3+9*2+20*1=87

7．已知4个字符A,B,C,D的哈夫曼编码分别是1，01，000，001。下列01串是由以上4个字母构成的一

段文本的哈夫曼编码：1001000011011010011010011。请将上述01串还原为编码前的文本，以字符在文本中出现的次数为权值，求出这棵树的带权路径长度。 1 001 000 01 1 01 1 01 001 1 01 001 1 A D C B A B A B D A B D A A:5 B:4 C:1

13 D:3

8 5

4 4

1 3

带权路径长度：1*3+3*3+4*2+5*1=25

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