二叉树练习题及答案.doc

选择题 1．关于二叉树的下列说法正确的是（ B ） A． 二叉树的度为2 B． 二叉树的度可以小于2 C． 每一个结点的度都为2 D ．至少有一个结点的度为2 2．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为（ C ） A． 3 B． 4 C．5 D ．6 3．若一棵完全二叉树中某结点无左孩子，则该结点一定是（D ） A． 度为1的结点 B． 度为2的结点 C． 分支结点 D ．叶子结点 4．深度为k的完全二叉树至多有（ C ）个结点，至少有（ B ）个结点。 A． 2k-1-1 B． 2k-1 C． 2k-1 D ．2k 5．在具有200个结点的完全二叉树中，设根结点的层次编号为 1，则层次编号为60的结点，其左孩子结点的层次编号为（ C 2i ），右孩子结点的层次编号为（ D 2i+1），双亲结点的层次编号为（ 60/2=30 A ）。 A． 30 B． 60 C． 120 D ．121 6．一棵具有124个叶子结点的完全二叉树，最多有（B ）个结点。 A． 247 B． 248 C． 249 D ．250 填空题 1． 树中任意结点允许有 零个或多个 孩子结点，除根结点外，其余结点 有且仅有一个 双亲结点。 2．若一棵树的广义表表示法为A（B（E，F），C（G（H，I，J，K），L），D（M（N））），则该树的度为 4 ，树的深度为 4 ，树中叶子结点的个数为 8 。 3．若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数为 14 。 n=n0+n1+n2+n3+n4=n0+4+3+2+2=n0+11 n=1+孩子=1+4+6+6+8+25 n0+11=25 n0=14 4．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是 n-2m+1 。 5．深度为k（k0）的二叉树至多有 2k -1 个结点，第i层上至多有 2i-1 个结点。 6．已知二叉树有52个叶子结点，度为1的结点个数为30，则总结点个数为 133 。 7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是 30+29+0=59 。 8．高度为6的完全二叉树至少有 32 个结点。 9．一个含有68个结点的完全二叉树，它的高度是 7 。 10．已知一棵完全二叉树的第6层上有6个结点，则总的结点个数至少是 37 ，其中叶子结点个数是 19 。 解析：（1） 5：31 6：6 （2）第5层上的叶子节点为：24-3=13 第6层上的叶子节点为：6 总的叶子节点个数为：13+6=19 11．已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是 107 。 解析：由题意得：这棵二叉树最多有7层 在第6层满的情况下，有26-1=32，其中非叶子节点有32-10=22，而非叶子节点最多有两个孩子从而第七层上共有22*2=44个节点。 又前6层的节点数为：26-1=63 所以这棵二叉树的节点数最多为63+44=107个