数据结构-习题-第六章-树和二叉树.doc

《数据结构-习题-第六章-树和二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第六章树和二叉树一、选择题1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE【北京航空航天大学1999一、3（2分)】2．算术表达式a+b*（c+d/e）转为后缀表达式后为（）【中山大学1999一、5】EFDGAB/++*-C*A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++3.设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是

2、（）【南京理工大学1999一、20（2分）】A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G4.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．8【南京理工大学2000一、8（1.5分）】5.在下述结论中，正确的是（）【南京理工大学1999一、4（1分）】①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完

3、全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④6.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定【南京理工大学2000一、17（1.5分）】7.树是结点的有限集合，它（(1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称

4、为该结点的(（3）)。二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKi-λKj│≤1一定成立时，则称T为一棵（(5)）。供选择的答案：（1）(4)A.有0个或1个B.有0个或多个C.有且只有一个D.有1个或1个以上（2）A.互不相交B.允许相交C.允许叶结点相交D.允许树枝结点相交（3）A.权B

5、.维数C.次数D.序（5）A.丰满树B.查找树C.平衡树D.完全树【上海海运学院1999二、2(5分）】8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定【北京工商大学2001一.7(3分)】9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A．4B．5C．6D．7【哈尔滨工业大学2001二、2（2分）】10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F

6、对应的二叉树根结点的右子树上的结点个数是（）。【北方交通大学2001一、16（2分）】A．M1B．M1+M2C．M3D．M2+M311．具有10个叶结点的二叉树中有（）个度为2的结点，【北京航空航天大学2000一、5（2分)】A．8B．9C．10D．ll12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）【西安交通大学1996三、2(3分)】A．250B．500C．254D．505E．以上答案都不对13.设给定权值总数有n个，其哈夫曼树的结点总数为()【福州大学1998一、5(2分)】A．不确定B．

7、2nC．2n+1D．2n-114.有n个叶子的哈夫曼树的结点总数为（）。【青岛大学2002二、1（2分）】A．不确定B．2nC．2n+1D．2n-115．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。【中科院计算所1999一、2（2分）】A．n-1B．ën/mû-1C．é(n-1)/(m-1)ùD．én/(m-1)ù-1E．é(n+1)/(m+1)ù-116.有关二叉树下列说法正确的是（）【南京理工大学2000一、11（1.5分）】A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少

8、有一个结点的度为2D．二叉树中任何一个结点的度都为217．二叉树的第I层上最多含有结点数为（）【中山大学1998二、7（2分）】【北京理工大学2001六、5（2分）】A．2IB．2I-1-1C．2I-1D．2I-118.一个具有1025个结点的二叉树的高h为（）【南京理工大学1999一、19（2分）】A．11B．10C．11至1025之间D．10至1024之间19．一棵二叉树高度为h,