第6章树和二叉树(习题)

《第6章树和二叉树(习题)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4第6章树和二叉树习题一、选择题1、如果T2是由树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。A．先序B．中序C．后序D．层次序2、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．83、由3个结点可以构造出多少种不同的二叉树？（）A．2B．3C．4D．54、二叉树在线索后，仍不能有效求解的问题是（）。A．前（先）序线索二叉树中求前（先）序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。

2、A．9B．11C．15D．不确定6、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。A．n-1B．nC．n+1D．n+27、设给定权值总数有n个，其哈夫曼树的结点总数为()。A．不确定B．2nC．2n+1D．2n-18、（）的遍历仍需要栈的支持.A．前序线索树B．中序线索树C．后序线索树9、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同　　B．完全相同C．先序和中序相同，而与后序不同　D．中序和后序相同，而与先序不同10、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDE

3、FGB．ABCDEFGC．DACEFBGD．ADCFEG二、填空题1、已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。2、树在计算机内的表示方式有，，。3、在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______。4、如果结点A有3个兄弟，而且B是A的双亲，则B的度是______。5、设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为______。6、具有256个结点的完全二叉树的深度为。7、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是____。8、深度为k的完全二叉树至少有个结点，至多有个结点

4、。9、利用树的孩子兄弟表示法存储，可以将一棵树转换为______。410、先根次序周游树林正好等同于按______周游对应的二叉树；后根次序周游树林正好等同于______周游对应的二叉树。三、判断题1、霍夫曼树的结点个数不能是偶数。2、二叉树中序线索化后，不存在空指针域。3、深度为k具有n个结点的完全二叉树，其编号最小的结点序号为ë2k-2û+1。4、深度为K的二叉树中结点总数≤2k-1。5、非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。6、必须把一般树转换成二叉树后才能进行存储。7、二叉树的遍历只是为了在应用中找到一种线性次序。8、一棵树中的叶子数一定等于与其对应的

5、二叉树的叶子数。9、一个树的叶结点，在先序遍历和后序遍历下，皆以相同的相对位置出现。10、在二叉树的第i层上至少有2i-1个结点(i>=1)。四、应用题1．已知一棵树边的集合为{（i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j）(g，k)，(c，g)，(c，f)，(h，l)，(c，h)，(a，c)}用树型表示法画出此树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（

6、10）以结点c为根的子树的深度是多少？（11）树的度数是多少？2．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。3．已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问该树中有多少片叶子？4．已知某完全二叉树有100个结点，试求该二叉树的叶子数。5．已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点最多的那棵树的叶子数目。6．一个深度为L的满k叉树有如下性质，第L层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问（1）各层的结点数目是多少？（2）编号为n的结点的

7、双亲结点（若存在）的编号是多少？（3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？7．试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；4（2）中序序列和后序序列相同；（3）前序序列和后序序列相同。8．证明：一棵满k叉树上的叶结点数n0和非叶子结点数m之间满足下列关系：n0=(k-1)m+19．已知一棵二叉树的中序序列和后序序列分别