第六章
树和二叉树
一、选择题1．已知一算术表达式的中缀形式为ABCDE，后缀形式为ABCDE，其前缀形式为A．ABCDEBABCDEC．ABCDEDABCDE【北京航空航天大学1999一、3（2分】2．算术表达式ab（cde）转为后缀表达式后为（B）【中山大学1999一、5】A．abcdeB．abcdeC．abcdeD．abcde3设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（C）【南京理工大学1999一、20（2分）】CAABCDEFGBABCDEFGDEFGBACABCDE（FG）DABCDEFG4设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．8【南京理工大学2000一、8（15分）】5在下述结论中，正确的是（D）【南京理工大学1999一、4（1分）】①只有一个结点的二叉树的度为0②二叉树的度为2；③二叉树的左右子树可任意交换④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④6设森林F对应的二叉树为B，它有m个结点，B的根为pp的右子树结点个数为
森林F中第一棵树的结点个数是（A）A．m
B．m
1C．
1D．条件不足，无法确定【南京理工大学2000一、17（15分）】7树是结点的有限集合，它（1）根结点，记为T。其余结点分成为m（m0）个（2）的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的（3）。二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它（4）根结点。可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKiλKj│≤1一定成立时，则称T为一棵（5）。供选择的答案：（1）4A有0个或1个B有0个或多个C有且只有一个D有1个或1个以上（2）A互不相交B允许相交C允许叶结点相交D允许树枝结点相交（3）A权B维数C次数D序（5）A丰满树B查找树C平衡树D完全树【上海海运学院1999二、25分）】8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定【北京工商大学2001一73分】9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（r