资源描述：
《习题5树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1填空题(1)树是n（n≥0）个结点的有限集合。在一棵非空树中，有（且仅有一个）根结点，其余结点分成m（m>=0）个(互不相交)的有限集合，每个集合又是一棵树。(2)树中某结点的子树的个数称为该结点的（度），子树的根结点称为这个结点的(孩子结点),该结点称为其子树根结点的（双亲结点）.(3)一棵二叉树的第i（i≥1）层上最多有(2i-1)个结点,一棵有n(n>0)个结点的满二叉树共有((n+1)/2)个叶子结点和((n-1)/2)个非终端结点。(4)设高度为h的二叉树只有度为0的和度为2的结点，该二叉树的结点数可能达到的最大值是(2h
2、-1),最小值是（2h-1）。(5)深度为k的二叉树中，所含叶子的个数最多为(2k-1).(6)具有100个结点的完全二叉树的叶子结点数为(50)。(7)已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树有(12)个叶子结点。(8)某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是(CDBGFEA)。(9)在具有n个结点的二叉链表中，共有（2n)个指针域，其中(n-1)个指针域用于指向其左右孩子，剩下的(n+1)个指针域则是空的。(10)在有n个叶子的哈夫曼树中，叶子
3、结点总数为(n),分支结点总数为（n-1）。1填空题(续)(1)如果结点A有3个兄弟，B是A的双亲，则B的度是(D)。A．1B．2C．3D．42选择题(2)设二叉树有n个结点，则其深度为(D)。A．n一1B．nC．D．不能定(3)二叉树的前序序列和后序序列正好相反，则该二叉树一定是(B)的二叉树。A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子(4)线索二叉树中某结点R没有左孩子的充要条件是(C)。A.R.child=NULLB.R.ltag=0C.R.ltag=1D.R.child=NULL(5)深度
4、为k的完全二叉树至少有(B)个结点，至多有(C)个结点。A．2k-2+1B．2k-1C．2k-1D．2k-1-1一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有(D)成立。A．n＝h+mB．h+m＝2nC．m＝h-1D．n＝2m一1(7)任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序(A)。A.肯定不发生改变B.肯定发生改变C.不能确定D．有时发生变化(9)设森林中有4棵树，树中结点的个数依次为n1,n2,n3,n4,则把森林转换成二叉树后，其根结点的右子树上有(D)个结点。根结点的左子树上有(A)个结点。
5、A．n1-1B．nlC．nl+n2+n3D．n2+n3+n4(8)如果T'是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T'中结点的(A)序列，T中结点的后序序列就是T'中结点的(B)序列。A．前序B．中序C．后序D．层序(10)讨论树、森林和二叉树的关系，目的是为了(B)。A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C.将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义(11)下列编码中，(B)不是前缀编码。A.(00,01,10,11)B.
6、(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001)(12)为5个使用频率不等的字符设计哈夫曼编码，不可能的方案是(C).A.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,000,01,11,10(13)为5个使用频率不等的字符设计哈夫曼编码，不可能的方案是(D).A.000,001,010,011,1B.0000,0001,001,01,1C.000,001,01,10,11D.00,100,101,110,111(14)设哈夫曼编码
7、的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为(C)个字符编码.A.2B.3C.4D.5(3)已知一棵度为m的树中：n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问该树中共有多少个叶子结点？解：设该树中共有n0个叶子结点。则该树中总结点个数为n=n0+n1+…+nm.而分支数为n-1=n1+2n2+3n3+…+mnm,所以n0=1+n2+2n3+…+(m-1)nm4.解答下列问题(1)证明：任何满二叉树的分支数B=2(n0-1).(2)证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。(
8、4)已知一棵二叉树的中序和后序序列为CBEDAFIGH和CEDBIFHGA,试构造该二叉树。AEBGCHFDI(5)给出叶子结点的权值集合为W={5,2,9,11,8,3,7}的哈夫曼树的构造过程。95235101911
