文档介绍：第六章树和二叉树
一、选择题
A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为( )
A.-A+B*C/DE B. -A+B*CD/E C.-+*ABC/DE D. -+A*BC/DE
【北京航空航天大学 1999 一、3 (2分)】
+b*(c+d/e)转为后缀表达式后为( )【中山大学 1999 一、5】
E
F
D
G
A
B
/
+
+
*
-
C
*
+cde/* /+*+ /*++ */++
3. 设有一表示算术表达式的二叉树(见下图),
它所表示的算术表达式是( )
【南京理工大学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-G
4. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为( )
【南京理工大学 2000 一、8 ()】
5. 在下述结论中,正确的是( )【南京理工大学 1999 一、4 (1分)】
①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③ B.②③④ C.②④ D.①④
6. 设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是( )
-n -n-1 +1 ,无法确定【南京理工大学2000 一、17()】
7. 树是结点的有限集合,它( (1))根结点,记为T。其余结点分成为m(m>0)个((2))的集合T1,T2, …,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数称为该结点的( (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. 互不相交
(3) A. 权
(5) A. 丰满树 【上海海运学院1999二、2(5分)】
,5个度为1的结点,则度为0的结点个数是( )
【(3分)】
,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为( )个
【哈尔滨工业大学 2001 二、2 (2分)】
,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )。【北方交通大学 2001 一、16 (2分)】
+M2 +M3
( )个度为2的结点,【北京航空航天大学2000 一、5(2分)】
,其中叶子结点的个数是( )【西安交通大学 1996 三、2 (3分)】
A. 250 B. 500
13. 设给定权值总数有n 个,其哈夫曼树的结点总数为( ) 【福州大学 1998 一、5 (2分)】
+1 -1
14. 有n个叶子的哈夫曼树的结点总数为( )。【青岛大学 2002 二、1 (2分)】
+1 -1
,其叶结点个数为n,则非叶结点的个数为( )。【中科院计算所1999一、2(2分)】
-1 B.ën/mû-1 C.é(n-1)/(m-1)ù D. én/(m-1)ù-1 E.é(n+1)/(m+1)ù-1
16. 有关二叉树下列说法正确的是(