得分 评卷人 三、综合题（每小题10分，共30分） 1.(l)已知某二叉树的先序遍历序列是aecdb,中序遍历序列是eadcb,试画出该二叉树。 (2)给出上述二叉树的后序遍历序列。 (3)若上述二叉树的各个结点的字符分别是1,2,3,4,5，并恰好使该树成为一棵二叉排序 树，试问a、b、c、d、e的值各为多少？ 2.(1)给定数列{8,17,5,9,21,10,7,19,6}，依次取序列中的数构造一棵二叉排序树。 (2)对上述二叉树给出中序遍历得到的序列。 3.(1)以给定权重值1,2,12,13,20,25为叶结点，建立一棵哈夫曼树。 (②)若哈夫曼树有个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵 哈夫曼树是否一定唯一。 得 分 评卷人 四、程序填空题（每空2分，共16分） 1.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回 值是指向树结点的结构指针p(查找成功p指向查到的树结点，不成功P指向为NULL)完成 程序中的空格。 typedef struct Bnode int key; struct Bnode left; struct Bnode right; Bnode; Bnode BSearch(Bnode bt,int k) /bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/ Bnode p; if(bt==(1) return (bt); p=bt; 1369得 分 评卷人 三、综合题(每小题 10分，共 30分) 1. (1)已知某二叉树的先序遍历序列是 aecdb，中序遍历序列是 eadcb，试画出该二叉树。 (2)给出上述二叉树的后序遍历序列。 (3)若上述二叉树的各个结点的字符分别是 1,2,3,4,5，并恰好使该树成为一棵二叉排序 树，试问 a,b,c,d,e的值各为多少? 2.(l)给定数列{8,17,5,补21,10,7,19,6)，依次取序列中的数构造丫棵二叉排序树· (2)对上述二叉树给出中序遍历得到的序列。 3. (1)以给定权重值1,2,12,13,20,25为叶结点，建立一棵哈夫曼树。 (幻若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵 哈夫曼树是否一定唯一。 得 分 评卷人 四、程序填空题(每空 2分，共 16分) 1.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回 值是指向树结点的结构指针 P(查找成功 P指向查到的树结点，不成功 P指向为 NULL)完成 程序中的空格。 typedef struct Bnode 左 int key; struct Bnode * left; struct Bnode * right; }Bnode; Bnode二BSearch (Bnode二bt, int k) /二bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字 二/ 丈 Bnode，P; if(bt== (1) _) return (bt); v=bt; 1369