《第6章树和二叉树(习题).doc》由会员分享，可在线阅读，更多相关《第6章树和二叉树(习题).doc（4页珍藏版）》请在金锄头文库上搜索。
1、1 第6章树和二叉树习题一、选择题1、如果T2是由树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）。A先序 B中序 C后序 D层次序2、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5 B6 C7 D83、由3 个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 4、二叉树在线索后，仍不能有效求解的问题是（ ）。A前（先）序线索二叉树中求前（先）序后继 B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱 D后序线索二叉树中求后序后继 5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（
2、 ）。A9 B11 C15 D不确定6、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。A n-1 Bn C n+1 D n+27、设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 。A不确定 B2n C2n+1 D2n-18、（ ）的遍历仍需要栈的支持.A前序线索树 B中序线索树 C后序线索树 9、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同 10、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）ACA
3、BDEFG BABCDEFG CDACEFBG DADCFEG 二、填空题1、已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_。2、树在计算机内的表示方式有 ， ， 。3、在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =_。4、如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_。5、设一棵完全二叉树叶子结点数为k,最后一层结点数2，则该二叉树的高度为_。6、具有256个结点的完全二叉树的深度为 。 7、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是_。 8、深度为k的完全二叉树至少有 个结点，至多有 个结点。9、利用树的孩子兄弟表
4、示法存储，可以将一棵树转换为_。10、先根次序周游树林正好等同于按_周游对应的二叉树；后根次序周游树林正好等同于_周游对应的二叉树。三、判断题1、 霍夫曼树的结点个数不能是偶数。2、 二叉树中序线索化后，不存在空指针域。3、深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 2k-2+1。4、深度为K的二叉树中结点总数2k-1。5、非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。6、 必须把一般树转换成二叉树后才能进行存储。 7、 二叉树的遍历只是为了在应用中找到一种线性次序。8、 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。 9、 一个树的叶结点，在先序遍历和
5、后序遍历下，皆以相同的相对位置出现。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）树的深度是多少？ （10）以结点c为根的子树的深度是多少？
6、 （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的结点的双亲结点（若存在）的编号是多少？（3）编号为n的结点的
7、第i个孩子结点（若存在）的编号是多少？（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？7试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同。8证明：一棵满k叉树上的叶结点数n0和非叶子结点数m之间满足下列关系： n0=(k-1)m+19已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。并写出其前序遍历序列。10. 一棵n个结点的完全二叉树以向量作为其存储结构，试编写非递归算法实现对该树进行前序遍历。将图6.32所示的森林转换为二叉树。 图6.3211写出图6.32
8、所示森林的前序序列和后序序列。12. 给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。五、算法设计题1假设二叉树T中至多有一个结点的数据域值为x，试编写算法拆去以该结点为根的子树，使原树分成两棵二叉树。例如x=E，二叉树的变化情况如图6.33所示。 （a）拆开前 （b）拆开后 图6.332 在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先。假设值为x的结点不多于1个。（提示：利用后序遍历非递归的算法，当找到值为x的结点时，打印X中有关内容。）
9、3以二叉链表为存储结构，分别写出求二叉树结点总数和叶子总数的算法。4设二叉树用二叉链表表示，编写求二叉树的高度的算法。5已知：深度为h的二叉树，以一维数组BT1.2h-1作为其存储结构。编写一算法，求该二叉树叶子结点的个数。6编写一个将二叉树中每个结点的左右孩子交换的算法。7写出在前序线索二叉树中查找给定结点P的前序后继的算法。8以二叉链表为存储结构，写一算法对二叉树进行层次遍历。提示：应使用队列来保存各层的结点。9写出在后序线索二叉树中查找给定结点P的后序前趋的算法。10试编写算法判断两棵二叉树是否等价。称二叉树T1和T2是等价的：如果T1和T2都是空的二叉树；或者T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1的右子树与T2的右子树是等价的。
