得分 评卷人 三、综合题（每小题10分，共30分） 28.(1)对给定权值3,1,4,4,5,6，构造深度为5的哈夫曼树。（设根为第1层） (2)求树的带权路径长度。 (3)链接存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由。 29.(1)如下的一棵树，给出先序遍历序列 (2)把1,2,3,4,5,6,7,8,9填人，使它成为一棵二叉排序树 提示：设图中的树是二叉排序树，找出中序遍历序列与1,2，…9的对应关系 (3)请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。 A2 A3 A4 A6 A5 A7 A8 A9 图3 30.设查找表为(5,6,7,8,9,10,11,12,13,14) (1)画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点） (2)给出二叉排序树的定义，针对上述折半查找所对应的判定树的构造过程，说明判定树 是否是二叉排序树（设树中没有相同结点）？ (3)为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？ 1032三、综合题{每小题 10 分，共 30 分) 28. (1)对给定权值 ，构造深度为 的哈夫曼树。(设根为第 层) (2) 求树的带权路径长度。 ( 3) 链接存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由。 29. (1)如下的一棵树，给出先序遍历序列 (2) 填人，使它成为一棵二叉排序树 提示:设图中的树是二叉排序树，找出中序遍历序列与 2. 的对应关系 (3) 请在该树中再插入一个结点 3. 作为叶结点，并使它仍然是一棵二叉排序树。 13 30. 设查找表为 (5 10 11 12 13 14) (1)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2) 给出二叉排序树的定义，针对七述折半查找所对应的判定树的构造过程，说明判定树 是否是二叉排序树(设树中没有相同结点)? (3) 为了查找元素 5.5 ，经过多少次元素间的比较才能确定不能查到? 1032