树及二叉树-习题.doc

第六章 树和二叉树
一、 单项选择题
1. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )
A.DEBAFC B.DEFBCA
C.DEBCFA D.DEBFCA
2. 一棵含18个结点的二叉树的高度至少为( )
A.3 B.4
C.5 D.6
3. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的( )
A．1/2倍 B．1倍
C．2倍 D．3倍
4. 树最适合用来表示( )
A.有序数据元素 B.无序数据元素
C.元素之间具有分层次关系的数据 D.元素之间无联系的数据
5. 二叉树中第5层上的结点个数最多为( )
A.8 B.15
C.16 D.32
6. 线索二叉树是一种__结构( )
A.逻辑 B.逻辑和存储
C.物理 D.线性
7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至
少为( )
A.2h B.2h-1
C.2h+1 D.h+1
8. 在一棵非空二叉树的中序遍历序列中，根结点的右边 ( )
A.只有右子树上的所有结点 B. 只有右子树上的部分结点
C.只有左子树上的所有结点 D.只有左子树上的部分结点
9. 一棵二叉树的广义表表示为a(b(c,d)e(,f(g))),则得到的中序遍历序列为( )
A.a,b,c,d,e,f,g B.c,b,d,a,e,g,f
C.c,d,b,g,f,e,a D.a,b,e,c,d,f,g
10. 任何一颗二叉树的叶结点在先序，中序和后序遍历中的相对次序( )
A.不发生改变 B.发生改变
C.不能确定 D.以上都不对
11. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为( )
A.|_(n+1)/2_| B. |_(n-1)/2_|
C. D. |_n/2_|
12. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则右孩子结点的编号为( )
A.2i B.2i-1
C.2i+1 D.2i+2
13. 在一棵完全二叉树中，对于编号为i的结点(i>1)，其双亲结点的编号为( )
A. |_(i+1)/2_| B. |_(i-1)/2_|
C. D. |_i/2_|
14. 按照二叉树的定义，具有3个结点的二叉树有__种( )
A.3 B.4
C.5 D.6
15. 深度为5的二叉树至多有__个结点( )
A.16 B.32
C.31 D.10
16.利用n个值生成的哈夫曼树中共有___个结点( )
A.n B.n+1
C.2n D.2n-1
17. 利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为( A)
A.55 B.29
C.58 D.38
二、填空题
1．对于一棵具有n个结点的树，该树中所有结点的度数之和为 ________个。
2．一棵深度为8完全二叉树第8层有7个结点，则共有______个结点，其中度为1的结点有_______个，度为0的结点有_______个，度为2的结点有______个，编号最大的非叶子结点是______，编号最小的叶子结点是______。
3．一棵深度为6的完全二叉树的第6层有6个结点，则叶子结点有 个。
4．在一棵三叉树中，假定双分支结点数为5个，三分支结点数为6个，单分支结点数为6个，则叶子结点数为____个。
5．指出树和二叉树的三个主要差别
____________________________,__________________________,__________________________________.
三、应用题
1．如图所示的二叉树，回答以下问题。
（1）分别写出该二叉树的先序遍历序列，中序遍历序列，后序遍历序列
（2）画出该二叉树对应的森林。

2．某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，回答以下问题；
（1）画出该二叉树
（2）给出后序遍历序列。
(3) 将此二叉树还原成森林
3.有一份电文中 0使用5个字符：a、b、c、d、e,它们的出现频率依次为4,7,5,2,9,
（1）试画出对应的哈夫曼树，（按左子树根结点的权小于等于右子树根结点的权构造）
（2）求出每个字符的哈夫曼编码
（3）求出按出现的频率为权的WPL
四、算法设计题
1． 设以二叉链表为二叉树的存储结构，
lchild
data
rchild
其中data为整数，试设计一个算法void change(BiTree *r)，若结点左孩子的data域的值大于右孩子的data域的值，则交换其左右子树。
2． 设计一个算法，对具有n个结点的二叉树进行中序遍历，把遍历得到的结点值序列保存
到数组中void preserve(BiTree *r,ElemType a[],int n)。