树和二叉树 习题.doc

文档介绍：第六章树和二叉树
单项选择题
1. 已知二叉树的先序序列为ABDECF,中序序列为DBEAFC,则后序序列为( )


2. 一棵含18个结点的二叉树的高度至少为( )


3. 除第一层外,满二叉树中每一层结点个数是上一层结点个数的( )


4. 树最适合用来表示( )


5. 二叉树中第5层上的结点个数最多为( )


6. 线索二叉树是一种__结构( )


7. 设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至
少为( )
-1
+1 +1
8. 在一棵非空二叉树的中序遍历序列中,根结点的右边( )
B. 只有右子树上的部分结点

9. 一棵二叉树的广义表表示为a(b(c,d)e(,f(g))),则得到的中序遍历序列为( )
,b,c,d,e,f,g ,b,d,a,e,g,f
,d,b,g,f,e,a ,b,e,c,d,f,g
10. 任何一颗二叉树的叶结点在先序,中序和后序遍历中的相对次序( )


11. 在一棵具有n个结点的完全二叉树中,分支结点的最大编号为( )
A.|_(n+1)/2_| B. |_(n-1)/2_|
C. D. |_n/2_|
12. 在一棵完全二叉树中,若编号为i的结点存在左孩子,则右孩子结点的编号为( )
-1
+1 +2
13. 在一棵完全二叉树中,对于编号为i的结点(i>1),其双亲结点的编号为( )
A. |_(i+1)/2_| B. |_(i-1)/2_|
C. D. |_i/2_|
14. 按照二叉树的定义,具有3个结点的二叉树有__种( )


15. 深度为5的二叉树至多有__个结点( )


( )
+1
-1
17. 利用3,6,8,12这四个值作为叶子结点的权,生成一棵哈夫曼树,该树的带权路径长度为( A)


二、填空题
,该树中所有结点的度数之和为________个。
,则共有______个结点,其中度为1的结点有_______个,度为0的结点有_______个,度为2的结点有______个,编号最大的非叶子结点是______,编号最小的叶子结点