得 分 评卷人 三、综合题（每小题10分，共30分） 1.（1)一组记录的关键字序列为{45,40,65,43,35,95}写出利用快速排序的方法，以第一 个记录为基准得到的一趟划分的结果（要求给出一趟划分中每次扫描和交换的结果）。 (2)同样对序列{45,40,65,43,35,95}利用直接插入排序，写出逐次插入过程（从第一个元 素一直到第六个元素)。 2.(1)利用筛选过程把序列{42,82,67,102,16,32,57,52}建成堆（小根堆），画出相应的完 全二叉树（不要求中间过程）。 (2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列。 3.(1)设有一个整数序列{50,38,16,82,110,13,64}，依次取出序列中的数，构造一棵二叉 排序树。 (2)利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到，为了查找 15,经多少次元素间的比较可知道查找失败。 得 分 评卷人 四、程序填空题（每空2分，共16分） 1.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针。 struct node { ElemType data; struct node next; }； struct node top void Push(ElemType x) { struct node p; p=(struct node *)malloc((1) p->data=x; 1357得分|评卷人 三、综合题(每小题 0分，共 0分) 1. (1)一组记录的关键字序列为 5， 40， 5， 4 3， 5， 9 5 }写出利用快速排序的方法，以第一 个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的结果)。 (2) ，40 ，65 ，43 ，35 ，95} 利用直 插入 第 一 素一直到第六个元素)。 2. (1)利用筛选过程把序列 2， 8 2， 7， 2， 6， 2， 7， }建成堆(小根堆儿画出相应的完 全二叉树(不要求中间过程)。 (2) 上述 全二叉树进行 序列 3. (1)设有一个整数序列 0， 8， 6， 2， 0， 3， }，依次取出序列中的数，构造一棵二叉 排序树。 (2) 上述二叉排 找110 次元 间 的 15 经多 可知道查找失 !得分|评卷人 四、程序填空题(每空 2分，共 6分) 1.以下函数为链校的进技操作， x是要进战的结点的数据域， top 找顶 struct node { ElemType data; struct node 铃next; struct node 祷top; void Push(ElemType x) struct node 铸p; p= (struct node 头)malloc«l) 一>data=Xj 1357