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

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

题号
—-

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

下面是有关二叉树的叙述，请判断正误
）3.二叉树中每个结点的两棵子树是有序的。
）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
）6.二叉树中所有结点个数是2虹七1,其中k是树的深度。（应25）
）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有〉一1个结点。（应2耳）二、填空2.

2.
【计算机研2000] 一棵深度为6的满二叉树有,
个叶子。
3.
一棵具有2 5 7个结点的完全二叉树，它的深度为,
4.
【计算机研2001】用5个权值｛3,2,4,5, 1｝构造的哈夫曼（Huffman）树的带权路径长度是_
（注：原题为选择题：A. 32B. 33C. 34 D. 15）
5.
在一棵二又树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =.
四、单项选择题（每小题1分，共11分）
）1.不含任何结点的空树o
（A）是一棵树；
（C）是一棵树也是一棵二叉树；
（B ）是一棵二叉树；
（D）既不是树也不是二叉树
）2.二叉树是非线性数据结构，所以。
（A）它不能用顺序存储结构存储；（B）它不能用链式存储结构存储；
（C）顺序存储结构和链式存储结构都能存储；（D）顺序存储结构和链式存储结构都不能使用
）3. K01年计算机研题』具有n（n>0）个结点的完全二叉树的深度为。
（A）Flog2（n）_|（B） L log2（n）J （C）L log2（n） J+1（D）「log2（n）+1]
1：「x]表示不小于x的最小整数；Lx」表示不大于x的最大整数，它们与[]含义不同!
除第一层外，满二叉树中每一层结点个数是上一层结点个数的（
A）l/2 倍B）1 倍C）2 倍
5.权值为｛1,2,6,8｝的四个结点构成的哈夫曼树的带权路径长度是（
4.
）。
A) 18
B)28
C) 19
D) 3倍
D) 29
5.【94程PH] 从供选择的答案中，选出应填入下面叙述二_内的最确切的解答，把相应编号写在 答卷的对应栏内。
树是结点的有限集合，它根结点，记为T。其余的结点分成为m （mNO）个的集合Tl, T2,…，Tm,每个集合又都是树，此时结点T称为Ti的父结点，1称为T的子结点（l<i
Wm）。一个结点的子结点个数为该结点的供选择的答案
A： ①有。个或1个
B:①互不相交
C：①权
供选择的答案
A： ①有。个或1个
B:①互不相交
C：①权

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

五、阅读分析题（每题5分，共20分）
（1）已知一棵二叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。
六、算法设计题（前5题中任选2题，第6题必做，每题8分，共24分）【严题集6.26®］假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19,0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这8个字母设计哈夫曼编码。使用0〜7的二进制表示形式是另 一种编码方案。对于上述实例，比较两种方案的优缺点。
1. 有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,347,8,9,试构造一棵哈夫曼树，并求其加权路径长度WPL,字符c的编码。
2. 给定一组权值2,3,5,7,11,13,17,19,23,29, 31, 37, 41,试画出用Huffman算法建造的哈夫曼树 树。【吉林大学2000 —、2 （4分）】