数据结构作业：第6章二叉树作业答案.docx

第6章树和二叉树姓名班级,

（注：原题为选择题：A. 32
B. 33
C. 34
D. 15)
一、下面是有关二叉树的叙述，请判断正误（V ） 3.二叉树中每个结点的两棵子树是有序的。
题号
—-

三
四
五
六
总分
题分
10
15
11
20
20
24
100
得分

（X ） 4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（X ） 6.-叉树中所有结点个数是2k ,-l,其中k是树的深度。（应2"）（X ） 7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（X ） 8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2」1个结点。（应2"）二、填空2.【计算机研2000] 一棵深度为6的满二叉树有2的=32个叶子。
3. 一棵具有2 5 7个结点的完全二叉树，它的深度为 9 （注：用Llog2（n） J+l=|_8.xx _|+1=94.【计算机研2001】用5个权值｛3, 2,4,5, 1｝构造的哈夫曼（Huffman）树的带权路径长度是33 。
解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL= （4+5+3） X24- （1+2） X3=33
（注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）5.在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0二一N2+1。
四、单项选择题（每小题1分，共11分）（C ） 1.不含任何结点的空树o（A）是一棵树；（B ）是一棵二叉树；（C）是一棵树也是一棵二叉树；（D ）既不是树也不是二叉树
答：以前的标答是B,因为那时树的定义是nNl（C ） 2.二叉树是非线性数据结构，所以。
（A）它不能用顺序存储结构存储；（B ）它不能用链式存储结构存储；
（C）顺序存储结构和链式存储结构都能存储；（D）顺序存储结构和链式存储结构都不能使用（C ） 3. K01年计算机研题』具有n（n>0）个结点的完全二叉树的深度为°（A）Flog2（n）l （B） L log2（n）J （C） L log2（n） J+l （D）「log2（n）+ll注1：「x]表示不小于x的最小整数；Lx」表示不大于x的最大整数，它们与■含义不同！ 注2：选（A）是错误的。例如当n为2的整数昴时就会少算一层。似乎Llog2（n）+1」是对的？
4.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（C ）
A）l/2 倍B）1 倍C）2 倍D）3 倍5.权值为｛1,2,6,8｝的四个结点构成的哈夫曼树的带权路径长度是（D ）。
A) 18
B)28
C) 19
D) 29
5.【94程PH］从供选择的答案中，选出应填入下面叙述二_内的最确切的解答，把相应编号写在 答卷的对应栏内。
树是结点的有限集合，它L根结点，记为T。其余的结点分成为m （mNO）个K的集合Tl, T2,…，Tm,每个集合又都是树，此时结点T称为T的父结点，Ti称为T的子结点（iWi<m）。一个结点的子结点个数为该结点的 _ 供选择的答案A： ①有。个或1个
B：①互不相交
C：①权

<m）。一个结点的子结点个数为该结点的 _ 供选择的答案A： ①有。个或1个
B：①互不相交
C：①权
A： ①有。个或1个
B：①互不相交
C：①权

A： ①有。个或1个
B：①互不相交
C：①权
②有0个或多个
②允许相交
②维数
③有且只有1个
③允许叶结点相交
③次数（或度）
④有1个或1个以上
④允许树枝结点相交
④序

答案：ABC=1, 1, 3五、阅读分析题（每题5分，共20分）
（1）己知一棵二叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。
前序:
A,B,D,G,C,E,F,H
中序:
D,G,B,A,E,C,H,F
后序:
G,D,B,E,H,F,C,A
层次:
A,B,C,D,E,F,G,H
六、算法设计题（前5题中任选2题，第6题必做，每题8分，共24分）
1.【严题集6.26®】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频
率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这8个字母设计哈夫曼编码。使用0〜7 的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

解：方案1;哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。
6], (7,10)】，……19,21,32w={7,19,2,6,32,3,21,10},按哈夫曼规则：【[(2,3),方案比较:
字母编号
对应编码
出现频率
1
1100
0.07
2
00
0.19
3
11110
0.02
4
1110
0.06
5
10
0.32
6
11111
0.03
7
01
0.21
8
1101
0.10
2 3
字母编号
对应编码
出现频率
1
000
0.07
2
001
0.19
3
010
0.02
4
011
0.06
5
100
0.32
6
101
0.03
7
110
0.21
8
111
0.10

方案 1 的 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 方案 2 的 WPL=3(0.19+0.32+0.21 +0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码

2.有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,347,8,9,试构造一棵哈夫曼树，并求

试画出用Huffman算法建造的哈夫曼树
（4分）】
2
3.给定一组权值2,3,5,7,11,13,17,19,23,29, 31, 37, 41, 树。【吉林大学2000 一、2