2. 从业资格
  3. 堆数据结构定义如下： 对于n个元素的关键字序列{a1，a2，...,an}，当

堆数据结构定义如下： 对于n个元素的关键字序列{a1，a2，...,an}，当

最全题库2022-08-02  32
问题 堆数据结构定义如下：对于n个元素的关键字序列{a1，a2，...,an}，当且仅当满足下列关系时称其为堆。在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若顶堆元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1是一个大顶堆的例子。图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=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开始）。
选项
答案
解析 【问题1】
（1）A->int_array[0]
（2）A->int_array[0]=A->int_array[A->array_size-1]
（3）A->array_size-1
（4）A->int_array[PARENT(i)]＜key
（5）A->int_array=key
【问题2】
（6）O(1)（7）O(lgn)（8）O(lgn)
【问题3】
（9）3

【问题1】
本题考查堆数据结构的相关内容。题目告诉我们函数heapMaximum（A）的功能返回大顶堆A中的最大元素；函数heapExtractMax（A）的功能是去掉并返回大顶堆A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆；而函数maxHeaplnsert（A，key）的功能是把元素key插入到大顶堆A的最后位置，再将A调整成大顶堆。
第（1）空在函数heapMaximum（A）中，而且从程序中可以看出，是返回的结果，那么应该是大顶堆中最大元素，就应该是A->int_array[0]。
第（2）空在函数heapExtractMax（A）中，根据该函数的功能描述，并结合程序可以看出，第（2）空是在将最大元素移出后，那么接下了来应该处理将最后一个元素“提前”到堆顶位置，那么就应该是A->int_array[0]=A->int_array[A->array_size-1]。
第（3）（4）（5）空都在函数maxHeaplnsert（A，key）中。从程序和函数的功能我们可以知道，从程序第（3）空最后，其作用是找到元素key的插入位置并插入该元素。第（3）空是给变量i赋值，从后面的程序中我们可以看出i是做为数组下标的；而查找元素插入的位置应该从后往前的顺序，因此i的初值应该为A->array_size–1，从循环中也可以看出i的值在逐渐变小。
第（4）空是循环的一个条件，而循环的作用是找到合适的插入位置，由于大顶堆的特点是根节点的值大于左右子树节点上的值，那么找到比待插入元素大的父节点时，应该就找到了它插入的合适位置，而每次操作后i的值被赋值为PARENT（i），很显然这是找到其父节点的存储位置，因此循环结束的一个条件就是找到一个比key值大的父节点，那么循环继续的条件就是父节点的值小于key的值，所以本空的答案为A->int_array[PARENT(i)]＜key。＜key。
第（5）空就是插入元素，所以应该填A->int_array=key。
【问题2】
根据题目描述，heapMaximum用来返回大顶堆A中的最大元素，而且大顶堆已经建成，只需要通过一步操作就能取到。因此时间复杂度是O（1），
而对于heapExtractMax是用来去掉大顶堆A的根，然后重新建堆，当输出堆顶结点并将堆中最后一个结点设置为根结点之后，根结点将有可能不再满足堆的性质，所幸的是整个序列也只有根结点一处的堆结构可能被破坏，其余结点仍然满足堆性质，故可利用性质进行堆调整，算法的基本思想为：将新堆顶沿着其关键字较大的孩子结点向下移动，直到叶子结点或者满足堆性质为止。因此相对于有N个元素的堆，只需要log2n次比较即可完成，因此时间复杂度是O（log2n），这与书本说堆排序的算法时间复杂度是：O(nlog2n)不冲突，因为书本上是对堆中所有元素进行操作，而这里其实相当于只将一个元素入堆，因此少了一个n。同样的道理可以得到maxHeaplnsert的时间复杂度O（log2n）。
【问题3】
这个我们可以结合题目给出的那个大顶堆的图来看，首先将key插入在最后，应该是8这个节点的右子树，由于10比8大，所以应该互换，再与节点9比较，由于10仍然大于9，所以也应该互换，这个时候再与其父节点15比较，由于小于15，所以不需要再调整，那么调整后的结果就是10这个元素应该作为根节点15的右子树。那么很显然10应该是在堆A中第3个位置。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2410282.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)