二叉树练习题及答案.doc

《二叉树练习题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、选择题1．关于二叉树的下列说法正确的是（B）A．二叉树的度为2B．二叉树的度可以小于2C．每一个结点的度都为2D．至少有一个结点的度为22．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为（C）A．3B．4C．5D．63．若一棵完全二叉树中某结点无左孩子，则该结点一定是（D）A．度为1的结点B．度为2的结点C．分支结点D．叶子结点4．深度为k的完全二叉树至多有（C）个结点，至少有（B）个结点。A．2k-1-1B．2k-1C．2k-1D．2k5．在具有200个结点的完全二叉树中，设根结点的层次编号为1，

2、则层次编号为60的结点，其左孩子结点的层次编号为（C2i），右孩子结点的层次编号为（D2i+1），双亲结点的层次编号为（60/2=30A）。A．30B．60C．120D．1216．一棵具有124个叶子结点的完全二叉树，最多有（B）个结点。A．247B．248C．249D．250二、填空题1．树中任意结点允许有零个或多个孩子结点，除根结点外，其余结点有且仅有一个双亲结点。2．若一棵树的广义表表示法为A（B（E，F），C（G（H，I，J，K），L），D（M（N））），则该树的度为4，树的深度为4，树中叶子结点的个数为

3、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+11n=1+孩子=1+4+6+6+8+25n0+11=25n0=144．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是n-2m+1。5．深度为k（k>0）的二叉树至多有2k-1个结点，第i层上至多有2i-1个结点。6．已知二叉树有52个叶子结点，度为1的结点个数为30，则总结点个数为133。7．已知二叉树中有30个叶子结点，则二叉

4、树的总结点个数至少是30+29+0=59。8．高度为6的完全二叉树至少有32个结点。9．一个含有68个结点的完全二叉树，它的高度是7。10．已知一棵完全二叉树的第6层上有6个结点，则总的结点个数至少是37，其中叶子结点个数是19。解析：（1）5：316：6（2）第5层上的叶子节点为：24-3=13第6层上的叶子节点为：6总的叶子节点个数为：13+6=1911．已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是107。解析：由题意得：这棵二叉树最多有7层在第6层满的情况下，有26-1=32，其中非

5、叶子节点有32-10=22，而非叶子节点最多有两个孩子从而第七层上共有22*2=44个节点。又前6层的节点数为：26-1=63所以这棵二叉树的节点数最多为63+44=107个