答案及解析：[问答题]堆数据结构定义如下：对于n个元素的关键字序列{a1，a2，...,an}，当且仅当满足下列关系时称其为堆。在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若顶堆元素为最小元素，则称为小顶堆。堆常用完全

问题：

[问答题] 堆数据结构定义如下：对于n个元素的关键字序列{a1，a2，...,an}，当且仅当满足下列关系时称其为堆。中级软件设计师,历年真题,2010年下半年（下午）《软件设计师》真题

在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若顶堆元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1是一个大顶堆的例子。中级软件设计师,历年真题,2010年下半年（下午）《软件设计师》真题

图4-1大顶堆示例堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小顶堆。以下考虑最大优先队列。假设现已建好大顶堆A，且已经实现了调整堆的函数heapify（A,n,index）。下面将C代码中需要完善的三个函数说明如下：（1）heapMaximum(A)：返回大顶堆A中的最大元素。（2）heapExtractMax(A)：去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。（3）maxHeapInsert(A,key)：把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。优先队列采用顺序存储方式，其存储结构定义如下：#define PARENT(i)i/2typedef struct array{int*int_array;//优先队列的存储空间首地址int array_size;//优先队列的长度int capacity;//优先队列存储空间的容量}ARRAY;【C代码】（1）函数heapMaximumint heapMaximum(ARRAY*A){return(1);}（2）函数heapExtractMaxint heapExtractMax(ARRAY*A){int max;max=A->int_array[0];（2）;A->array_size--;heapify(A,A->array_size,0);//将剩余元素调整成大顶堆return max;}（3）函数maxHeapInsertint maxHeapInsert(ARRAY*A,int key){int i,*p;if(A->array_size==A->capacity){//存储空间的容量不够时扩充空间p=(int*)realloc(A->int_array,A->capacity*2*sizeof(int));if(!p)return-1;A->int_array=p;A->capacity=2*A->capacity;}A->array_size++;i=（3）;while(i>0&&（4）){A->int_array[i]=A->int_array[PARENT(i)];i=PARENT(i);}（5）;return 0;}【问题1】（10分）根据以上说明和C代码，填充C代码的空（1）~（5）。【问题2】（3分）根据以上C代码，函数heapMaximum、heapExtractMax和maxHeapInsert的时间复杂度的紧致上界分别为（6）、（7）、（8）（用O符号表示）。【问题3】（2分）若将元素10插入到堆A={15，13，9，5，12，8，7，4，0，6，2，1}中，调用maxHeapInsert函数进行操作，则新插入的元素在堆A中的第（9）个位置（从1开始）。

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题