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

1、第6章 树和二叉树 姓名 班级 题号一二三四五六总分题分101511202024100得分一、下面是有关二叉树的叙述，请判断正误（ ）3.二叉树中每个结点的两棵子树是有序的。 （ × ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （ × ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （ × ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ × ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。（应2i-1）二、填空2. 【计算机研2000】 一棵深度为6的满二叉

2、树有26-1 =32 个叶子。3 一棵具有个结点的完全二叉树，它的深度为 9 。（ 注：用ë log2(n) û+1= ë 8.xx û+1=94. 【计算机研2001】 用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 33 。解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL（453）×2（12）×3=33 (15)(9) (6) （注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一） 4 5 3 (3) 1 2（注：原题为选择题：32 33 34 15）5. 在一棵二叉树中，度为

3、零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =_N2+1。四、单项选择题（每小题1分，共11分）（ C ）1 不含任何结点的空树 。（）是一棵树; （）是一棵二叉树; （）是一棵树也是一棵二叉树; （）既不是树也不是二叉树答：以前的标答是B，因为那时树的定义是n1（ C ）2二叉树是非线性数据结构，所以 。（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结构都不能使用 （ C ）3. 01年计算机研题 具有n(n>0)个结点的完全二叉树的深度为 。() élog2(n)ù

4、 () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù注1：éx ù表示不小于x的最小整数；ë xû表示不大于x的最大整数，它们与 含义不同！注2：选（A）是错误的。例如当n为2的整数幂时就会少算一层。似乎ë log2(n) +1û是对的？4. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的（C）A)1/2倍B)1倍C) 2倍D) 3倍5. 权值为1,2,6,8的四个结点构成的哈夫曼树的带权路径长度是（ D ）。A) 18 B)

5、28 C) 19 D) 295. 【94程P11】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。树是结点的有限集合，它A 根结点，记为T。其余的结点分成为m（m0）个 B 的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1im）。一个结点的子结点个数为该结点的 C 。供选择的答案A： 有0个或1个 有0个或多个 有且只有1个 有1个或1个以上 B: 互不相交 允许相交 允许叶结点相交 允许树枝结点相交C： 权 维数 次数（或度） 序答案：ABC1，1，3五、阅读分析题（每题5分，共20分）(1) 已知一棵二

6、叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。ABECFHDG前序：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个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码先将概率

7、放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比较：字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母编号对应编码出现频率111000.072000.193111100.02411100.06

8、5100.326111110.037010.21811010.10方案1的WPL2(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的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码331518789945232. 有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，并求其加权路径长度WPL，字符c的编码。解：哈夫曼树如右：WPL=(7+8+9)×2+4×3+（2+3）