得分 评卷人 三、综合题（每小题10分，共30分）】 1.设查找表为(7,15,21,22,40,58,68,80,88,89,120)，元素的下标依次为1,2,3，…，11。 (1)画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） (2)说明成功查找到元素40需要经过多少次比较？ (3)求在等概率条件下，成功查找的平均比较次数？ 2.(1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二 叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。 (2)设有数据集合{40,29,7,73,101,4,55,2,81,92,39}，依次取集合中各数据，构造一棵 二叉排序树。 3.(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈 夫曼编码。 (2)一棵哈夫曼树有个叶结点，它一共有多少个结点？简述理由？ 得 分 评卷人 四、程序填空题（每空2分，共16分） 1.设线性表为(6,10,16,4)，以下程序用说明结构变量的方法建立单向链表，并输出链表 中各结点中的数据。 #define NULL 0 void main() (NODE a,b,c,d,head,p; a.data=6; b.data=10; c.data=16; d,data=4;/d是尾结点*/ head=(1) a.next=&.b; b.next=&c; c.next=&.d; 1354得 分 评卷人 三、综合题(每小题 10分，共 30分) 1.设查找表为(7,15,21,22,40,58,68,80,88,89,120)，元素的下标依次为 1,2,3,"""""",11, (1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示) (2)说明成功查找到元素 40需要经过多少次比较? (3)求在等概率条件下，成功查找的平均比较次数? 2. (1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二 叉排序树，这种说法是否正确?若认为正确，则回答正确，若认为不正确，则举例说明。 (2)设有数据集合{40,29,7,73,101,4,55,2,81,92,39)，依次取集合中各数据，构造一棵 二叉排序树。 3. (1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈 夫曼编码。 (2)一棵哈夫曼树有 n个叶结点，它一共有多少个结点?简述理由? 得 分 评卷人 四、程序填空题(每空 2分，共 16分) 1.设线性表为(6,10,16,4)，以下程序用说明结构变量的方法建立单向链表，并输出链表 中各结点 中的数据 。 #define NULL 0 void main() (NODE a, b，c, d, * head，‘P; a. data= 6; b. data= 10; c. data= 16; d. data= 4;/‘d是尾结点，/ head= (1) ; a. next=乙b; b. next=&c; c. next=乙d; 1354