得分 评卷人 三、综合题（每小题10分，共30分）》 l.(1)已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树。 (2)若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该 树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。 (3)给出该树的前序遍历序列。 2.（1)设有一个整数序列{40,28,6,72,100,3,54}依次取出序列中的数，构造一棵二叉排 序树。 (2)对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度。 3.（1)利用筛选过程把序列{42,82,67,102,16,32,57,52}建成堆（小根堆），画出相应的完 全二叉树（不要求中间过程）。 (2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列。 得 分 评卷人 四、程序填空题（每空2分，共16分） 1.以下函数在a[0]到a[n一l]中，用折半查找算法查找关键字等于k的记录，查找成功 返回该记录的下标，失败时返回一1，完成程序中的空格。 typedef struct int key; 40000 )NODE; int Binary_Search(NODE a[],int n,int k) int low,mid,high; low=0; high=n-1; while((1) 1365得分|评卷人 三、综合题(每小题 0分，共 0分) 1. (1)已知某二叉树的后序遍历序列是 a，中序遍历序列是 c，试画出该二叉树。 (2) 述二叉 各个结 字符分别代表不 相等 ，并恰好使该 树成为一棵二叉排序树，试给出 a、 b、 c、 d， e的大小关系。 (3) 序遍历 2. (1)设有一个整数序列 0，钮， 6， 7 2， 0， 3， }依次取出序列中的数，构造一棵二叉排 序树。 (2) 叉排 在等 条件 平均 3. (1) 利用 程把 列{42 ，82 ，67 ，102 ，16 ，32 ，57 ，52} 建成堆 根堆 相应 全二叉树(不要求中间过程)。 (2) 述堆对 全二叉 进行 遍历 得分|评卷人 四、程序填空题(每空 2分，共 6分} 1.以下函数在 ]到 ]中，用折半查找算法查找关键字等于 k的记录，查找成功 返回该记录的下标，失败时返回 I，完成程序中的空格。 typedef struct { int key; ••• •• • }NODE; int Binary_Search(NODE ，int n , int k) int low ,mid ,high; low=O; high=n-l; while( (1) 1365