问答题
试题四（共15分）
阅读下列说明和C代码，回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
堆数据结构定义如下：
对于n个元素的关键字序列｛al，a2，…，an｝,当且仅当满足下列关系时称其为堆。
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称
为小顶堆。堆常用完全二叉树表示，图4-1是一个大顶堆的例子。
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称
为小顶堆。堆常用完全二叉树表示，图4-1是一个大顶堆的例子。
问答题
【问题1】（10分）
根据以上说明和c代码，填充c代码中的空（1）~（5）。
【正确答案】（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)]int_array[i]=key
【答案解析】
问答题
【问题2】（3分）
根据以上c代码，函数heapMaximum, heapExtractMax和maxHeaplnsert的时间复杂度的紧致上界分别为（6）、（7）和（8）（用O符号表示）。
【正确答案】（6）O(1) （7）O(lgn) （8）O(lgn)
【答案解析】
问答题
【问题3】（2分）
若将元素10插入到堆A＝（15，13，9，5，12，8，7，4，0，6，2，1）中，调用maxHeaplnsert函数进行操作，则新插入的元素在堆A中第（9）个位置（从1开始）。
【正确答案】（9）3
【答案解析】