三、综合题
1.(1)对给定权值 3,1 ,4,4,5,6,构造深度为 5 的哈夫曼树。(设根为第 1 层)。(2) 求树的带权路径长度。
(3)链接存储上述哈夫曼树,结点中共有多少个个指针域为空,说明理由.
23
答:(2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58
(3) 共 11 个结点,22 个指针域,除根结点外,
97
14
每个结点对应一个指针域.,共 10 个指针域非空,
故有 22-10=12 个空指针域,
2.
89 65 43 54
(1)以 2,3,4,7,8,9 作为叶结点的权,构造一棵哈夫曼树( 要求每个结点的左子树根结点的权小于等于右子树根结点
的权),给出相应权重值叶结点的哈夫曼编码。(2) 一棵哈夫曼树有 n 个叶结点,它一共有多少个结点?简述理由?
45 43
答:(1)
2:1110
3: 1111
3 12
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
A1
7
图 1 图 2
4.一组记录的关键字序列为(46,79,56,38,40,84)
A2
4 8
A3
(1)利用快速排序的方法,给出以第一个记录为基准得到的一次划分结果(给出逐次交换元素的过程,要求以升序排列)
(2)对上述序列用堆排序的方法建立大根堆,要求以二叉树逐次描述建堆过程。
(1)初始序列
A4 A6
2 9
46,79,56,38,40,84
A5
5
40,79,56,38,40,84
40,79,56,38,79,
A7 A8
1 3
84
A9
6
40,38,56,38,79,84
40,38,56,56,79,84
40,38,46,56,79,84
3.5
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 需要进行多少次元素间的比较?