赫夫曼树练习题

《赫夫曼树练习题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、精品文档赫夫曼树练习题一、选择题1、二叉树的深度为k，则二叉树最多有个结点。A.kB.k-1C.k-1D.k-12、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是。A.R[2i-1]B.R[2i+1]C.R[2i]D.R[2/i]3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是。A.a在b的右方B.a在b的左方C.a是b的祖先D.a是b的子孙4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca

2、，则二叉树先序遍历序列为。A.adbceB.decabC.debacD.abcde5、在一棵具有5层的满二叉树中结点总数为。A.1B.C.D.166、由二叉树的前序和后序遍历序列惟一确定这棵二叉树。A.能B.不能7、某二叉树的中序序列为ABCDEF2016全新精品资料-全新公文范文-全程指导写作–独家原创17/17精品文档G，后序序列为BDCAFGE，则其左子树中结点数目为。A.B.C.D.8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为。A.B.8C.9D.09、将一棵有100个结点的

3、完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为。A.B.9C.0D.810、表达式a*-d的后缀表达式是。A.abcd+-B.abc+*d-C.abc*+d-D.-+*abcd11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是。A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC12、树最适合用来表示。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数

4、据13、表达式A*/的后缀表达式是A.A*B+C/D-E+FB.AB*C+D/E-F+C.ABC+*DE-F+/ABCDED*+/-+D.2016全新精品资料-全新公文范文-全程指导写作–独家原创17/17精品文档14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。A.不发生改变B.发生改变C.不能确定D.以上都不对15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为个。A.1B.1C.1D.716、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径

5、长度为。A.1B.3C.3D.4二、判断题1、存在这样的二叉树，对它采用任何次序的遍历，结果相同。2、中序遍历一棵二叉排序树的结点，可得到排好序的结点序列。3、对于任意非空二叉树，要设计其后序遍历的非递归算法而不使用堆栈结构，最适合的方法是对该二叉树采用三叉链表。4、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。5、一个含有n个结点的完全二叉树，它的高度是?log2n?＋1。2016全新精品资料-全新公文范文-全程指导写作–独家原创17/17精品文档6、完全二叉树的某结点若无

6、左孩子，则它必是叶结点。三、填空题1、具有n个结点的完全二叉树的深度是?log2n?+1。2、哈夫曼树是其树的带权路径长度最小的二叉树。3、在一棵二叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有n0=N2+1。4、树内各结点度的最大值称为树的度。四、综合题1、假设用于通讯的电文仅由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这8个字母设计哈夫曼编码。10001B101A0003800

7、1C10000121G0321ED1001E11F10001G2016全新精品资料-全新公文范文-全程指导写作–独家原创17/17精品文档01H0017A10H0116D19B5012C3F2、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。301218743125116WPL=12*1+*3+*4=12+45+12=693、已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。ABDEGJCFHIKL《数据结构》课程设计报

8、告课程名称：2016全新精品资料-全新公文范文-全程指导写作–独家原创17/17精品文档课程设计题目：姓名：院系：专业：年级：学号：指导教师：《数据结构》课程设计2011年月日目录1、程序设计的目的2、设计题目3、分析4、设计思想5、算法6、测试结果7、调试分析8、小结1、课程设计的目的2、3、4、熟练使用C++语言编写程序，解决实际问题；了解并掌握数据结构与算法的设计方