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

第6章树和二叉树姓名班级,题号-三四五六总分题分101511202024100得分下面是有关二叉树的叙述，请判断正误）3.二叉树中每个结点的两棵子树是有序的。）4.二叉树中每个结点有两棵非空子树或有两棵空子树。）6.二叉树中所有结点个数是2虹七1,其中k是树的深度。（应25）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有一1个结点。（应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）+11：x表示不小于x的最小整数；Lx表示不大于x的最大整数，它们与含义不同!除第一层外，满二叉树中每一层结点个数是上一层结点个数的（A）l/2 倍B）1 倍C）2 倍5.权值为1,2,6,8的四个结点构成的哈夫曼树的带权路径长度是（4.）。A) 18B)28C) 19D) 3倍D) 295.【94程PH 从供选择的答案中，选出应填入下面叙述二_内的最确切的解答，把相应编号写在 答卷的对应栏内。树是结点的有限集合，它根结点，记为T。其余的结点分成为m （mNO）个的集合Tl, T2,，Tm,每个集合又都是树，此时结点T称为Ti的父结点，1称为T的子结点（l<iWm）。一个结点的子结点个数为该结点的供选择的答案A： 有。个或1个B:互不相交C：权供选择的答案A： 有。个或1个B:互不相交C：权有0个或多个允许相交维数有且只有1个允许叶结点相交次数（或度）有1个或1个以上允许树枝结点相交序五、阅读分析题（每题5分，共20分）（1）已知一棵二叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。六、算法设计题（前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的二进制表示形式是另 一种编码方案。对于上述实例，比较两种方案的优缺点。2. 有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,347,8,9,试构造一棵哈夫曼树，并求其加权路径长度WPL,字符c的编码。3. 给定一组权值2,3,5,7,11,13,17,19,23,29, 31, 37, 41,试画出用Huffman算法建造的哈夫曼树 树。【吉林大学2000 、2 （4分）】