《树和二叉树》习题

本文格式为Word版，下载可任意编辑——《树和二叉树》习题一、选择题

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+1B．n0=n2+2*n3+1C．n0=n2+n3+1D．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

BC

DGFE

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

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

5.设al，a2，a3是不同的关键字，且al6．以权值分别为3,4,7,9,20的a,b,c,d,e五个元素作为叶结点构造二叉树，回复：

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

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

920

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

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

149

77

34

最短带权路径：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串还原为编码前的文本，以字符在文本中出现的次数为权值，求出这棵树的带权路径长度。1001000011011010011010011ADCBABABDABDAA