三、综合题
1．（1）对给定权值3，1 ，4，4，5，6，构造深度为5的哈夫曼树。
(设根为第1层)。
(2) 求树的带权路径长度。
（3
答：（2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58 (3) 共11个结点,22个指针域,除根结点外, 每个结点对应一个指针域.,共10个指针域非空, 故有 22-10=12个空指针域, 2．
(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树( 要求每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。
(2) 一棵哈夫曼树有n 个叶结点，它一共有多少个结点？简述理由？
答：(1) 2：1110 3: 1111 4：110 7：
00 8：01 9：10
（2）2n-1个，因为非叶结点数比
叶结点数少一个。
3. (1) 如下的一棵树,给出先序遍历序列
(2) 把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树
提示：设图中的树是二叉排序树，找出中序遍历序列与 1，2，…9的对应关系 (3) 请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树 答：1 A1 A2 A4 A7 A8 A5 A9 A3 A6
（2）如图1
4．一组记录的关键字序列为（46，79，56，38，40，84）
（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列） （2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。
79，56，38
84 40
56，3884
405679，84 40，38
79，84 40，3856，79，84 40，3856，79，84
5．设查找表为(5,6,7,8,9,10,11,12,13,14)
（1）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2) 给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树 是否是二叉排序树(设树中没有相同结点)？
(3) 为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？ 答：(1)
如图
(2)二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排： 若它的左子树 非空，则左子树的所有结点的值都小于它的根结点的值； 若它的右子树非空，则右子树的所有结点的值都大于（ 若允许结点有相同的值，则大于等于）它的根结点的值; 左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。
(3). 3次
6．设查找表为(50,60,75,85,96,98,105,110,120,130)
(1) 说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？ (2) 为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？
（
3）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) 答：(1)3次
(2)4次
1. (1) 说明什么是顶点活动网(AOV 网)和拓扑序列 （2）设有向图G 如下，写出3种拓扑序列，
（3）在图G 中增加一条边，使图G 仅有一条拓扑序列 答：（1）顶点活动网(AOV 网)：顶点表示活动，
边表示活动间先后关系的有向图叫做顶点活动网(AOV 网)。
拓扑序列：在AOV 网中，若不存在回路，则所有活动可排列成一个线性序列， 使得每个活动的所有前驱活动都排在该活动的前面，此序列叫做拓扑序列。
（2）3种拓扑序列： a, b, d, c
a, d, b, c d, a, b, c
（3）仅有一条拓扑序列为：a, b, d, c
2．设查找表为(16,15,20,53,64,7),
(1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n 个元素进行冒泡排序要进行多少趟冒泡？第j 趟要进行多少次元素间的比较？
(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点) (1)原序列
16 15 20 53 64 7
15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j 次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64
(3)平均查找长度=（1*1+2*2+3*3）/6=14/6 3．如下是一棵二叉排序树，A1,A2, (9)
表1，2，3,…9中各个不同数字， （1）给出对该树中序遍历的结果 （2） A3,A5,A7的值各为多少？
（3）请在该树中再插入一个结点9 .5作为叶结点， 并使它仍然是一棵二叉排序树
答(1) 中序 A7, A4, A8, A2, A5, A9, A1, A3, A6 (2) A3,A5,A7的值分别为8, 5, 1
4．
(1) 设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树。
（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。
答案：(2)中序遍历
中序2，3，4，5，6，7，14，16，18
5.
(1) 设有查找表{17，26，14，16，15，30，18，19，28}，依次取表中数据构造一棵二叉
排序树.
(2) 对上述二叉树给出后序遍历的结果
(3). 对上述二叉树给出中后序遍历的结果
(4)) 在上述二叉树中查找元素15共要进行多少次元素的比较?
答（2）后序15, 16, 14, 19, 18, 28, 30, 26, 17
（3）中序14, 15, 16, 17, 18, 19, 26, 28, 30
（4）4次
6．（1）对给定权值2，1，3，3，4，5，构造哈夫曼树。
（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。
wp12=45
1．（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树。
（2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。
（3）给出该树的前序遍历序列。
答：（1）（2）d<b<e<a<c
（3）abdec
2．(1) 以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树。
(2) 给出相应权重值叶结点的哈夫曼编码。
(3) 一棵哈夫曼树有2n-1个结点，它是共有多少个权重值构造而成的？简述理由？
答：(2) 3 0000
4 0001
5 001
10 01
8 10
9 11
（3）n个，因为非叶结点数比叶结点数少一个,
而权值个数=叶结点数
3．（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）。
（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列。
3．（1）
（2）102，52，42，82，16，67，32，57
4．（1）简述拓扑排序的步骤。
（2）说明有向图的拓扑序列不一定是唯一的原因。
（3）如何利用拓扑排序算法判定图是否存在回路。
（4）设有向图G如下，写出首先删除顶点1的3种拓扑序列。
答：(1) 循环执行以下两步
选择一个度为0的顶点并输出
从网中删除此结点及所有出边
（2）因为选择一个度为0的顶点时不一定是唯一的
（3）由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱
5．设查找表为(11,12,13,14,15,16,17,18,19,20,21) ,元素的下标从0开始。
（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用数值表示）（2）说明成功查找到元素15，19各需要经过多少次比较？
（3）说明查找不到元素10，15.5各需要经过多少次比较？
（4）給出中序遍历判定树的序列。
答：
(2) 4次2次
（3）3次4次
（4）11，12，13，14，15，16，17，18，19，20，21
6．设有序表为（21，22，23，24，25，26，27，28，29，30，31,32），元素的下标从0开始。
（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到。
（2）画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示）
（3）设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。
（4）求在等概率条件下，成功查找的平均比较次数？
答（1）5
（2）
(3) 3
(4) ASL=(1+2*2+3*4+5*4)/12=37/12。