得分 评卷人 三、综合题(每小题10分,共30分) 28(1)利用筛选过程把序列{42,82,67,102,16,32,57,52}建成堆(小根堆),画出该堆(不 要求中间过程)。 (2)写出对上述堆对应的完全二又树进行中序遍历得到的序列。 29设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序(要求升序排列),要求写出每一趟的排序过程。 (2)在排序后的有序表的基础上,画出对其进行折半查找所对应的判定树。(要求以数据 元素作为树结点)。 (3)求在等概率条件下,对上述有序表成功查找的平均查找长度。 30(1)设有一个整数序列{50,38,16,82,110,13,64},依次取出序列中的数,构造一棵二 叉排序树。 (2)利用上述二叉排序树,为了查找110,经多少次元素间的比较能成功查到,为了查找 15,经多少次元素间的比较可知道查找失败? 得 分 评卷人 四、程序填空题(每空2分,共16分)】 31以下函数为链队列的人队操作,x为要人队的结点的数据域的值,front、rear分别是 链队列的队火、队尾指针 struct node ElemType data, struct node米next, }, struct node front,rear, void InQueue(ElemType x) { struct node p, p=(struct node *)(1) p->data=x, p->next=NULL, (2) rear=(3) } 1355得分|评卷人 三、综合题{每小题 0分,共 0分) 28 (1)利用筛选过程把序列 2, 8 2, 7, 0 2, 6, 2, 7, }建成堆(小根堆) ,画出该堆(不 要求中间过程)。 (2) 堆对应 完全 树进行 序遍历 29 找表为(16 ,15 ,20 ,53 ,64 ,7) (1)用冒泡法对该表进行排序(要求升序排列) ,要求写出每一趟的排序过程。 (2) 序后 有序 其进 半 查 所对应 判 定 元素作为树结点)。 (3) 求在 率条件下 对上 表成 查找 30 (1)设有一个整数序列 0, 8, 6, 2, 1 1 0, 3, },依次取出序列中的数,构造一棵二 叉排序树。 (2) 利用 排序 找110 多 少 次元 功 查 15 次元 间 的 可知 查找失 得分|评卷人 四、程序填空题{每空 2分,共 6分) 31 ,x 据域 front 、rear 分别是 链队列的队头、队尾指针 struct node { ElemType data , struct node 祷next struct node 祷front 赞rear VOId InQueue(ElemType x) struct node 赞p p= (struct node (1) p->data= x, P->next=NULL, (2) rear= (3) , , , 1355