27.二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非 空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点 的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是·的。 (回答正确或不正确) 得 分 评卷人 三、综合题（每小题10分，共30分】 28.(1)以3,4,5,8,9,10作为叶结点的权，构造一棵哈夫曼树。 (2)给出相应权重值叶结点的哈夫曼编码。 (3)一棵哈夫曼树有2-1个结点，它是共有多少个权重值构造而成的？简述理由？ 29.(1)简述拓扑排序的步骤。 (2)说明有向图的拓扑序列不一定是唯一的原因。 (3)如何利用拓扑排序算法判定图是否存在回路。 (4)设有向图G如下，写出首先删除顶点1的3种拓扑序列。 图3 30.设有序表为(21,22,23,24,25,26,27,28,29,30,31,32)，元素的下标从0开始。 (1)说出有哪几个元素需要经过4次元素间的比较才能成功查到。 (2)画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示） (3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。 (4)求在等概率条件下，成功查找的平均比较次数？ 109527. 树或者是一 有 下 列 排z 空，则左子树的所有结点的值都小于它的根结点的值$若它的右子树非空， Jt~右子的所有结点 的值都大于(若允许结点有相同的值，则大于等于〉它的根结点的值。这种说法是--'"的。 〈回答正确或不正确〉 |得分|评卷人| I I I 三、综合题{每小题 28. (1)以 造一 (2) 应权 夫曼 (3) 一棵 夫曼树有 是共 构造而 29. (1)简述拓扑排序的步骤。 (2) 不一定 (3) 用拓扑 (4) 图G 点1 的3 扑序 30. 为(21 ，22 ，23 ，24 ，25 ，26 ，27 ，28 ，29 ，30 ，31 ，32) 从O 开 (1)说出有哪几个元素需要经过 4次元素间的比较才能成功查到。 (2) 表进行折半查 所对 定树 点用 (3) 为5 间 的 确定 (4) 求在 条件 功查 平均 1095