问题 填空题

根据以上说明和C代码,填充C代码中的空(1)~(5)。

答案

参考答案:A->int_array[i]=key

解析:本题考查算法设计与分析以及C程序设计语言的相关知识。
根据题干说明,函数heapMaximum返回大顶堆A的最大元素,即堆顶元素,因此空(1)处应填A->int_array[0]。
函数heapExtractMax(A)取出大顶堆A的最大元素,将最后一个元素“提前”到堆顶位置,并将剩余元素调整成大顶堆。因此在将堆顶元素赋给max后,应该将堆的最后一个元素移到堆顶位置,即空(2)处应填A->int_array[0]=A->int_array[A->array_size-1]。
函数maxHeapInsert(A,key)把元素key插入到大顶堆A的最后位置,再将A调整成大顶堆。该函数前面的代码行考虑的是当存储空间不够时扩展存储空间。而后面是根据该函数的定义实现的问题求解的算法表示,A->array_size ++;表示为堆的规模增加1,i表示堆的最后一个元素的下标,即新插入的元素的下标,应该为A->array_size-1。while循环是自下而上调整堆,当还没有到堆顶位置,且新插入的元素大于其父亲元素,即A->int_array[PARENT(i)] <key时,i变为其父亲元素的下标。直到i到达堆顶位置,说明新插入的元素为最大值,或者i的父亲元素大于新插入的元素,说明新插入的元素在i处,因此空(5)处填A->int_array[i]=key。

单项选择题 A1型题
判断题