軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2024/6/16）在線測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/6/16

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2024/6/16）

閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
堆數(shù)據(jù)結(jié)構(gòu)定義如下：
對(duì)于n個(gè)元素的關(guān)鍵字序列{a1，a2，...,an}，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)稱其為堆。

在一個(gè)堆中，若堆頂元素為最大元素，則稱為大頂堆；若頂堆元素為最小元素，則稱為小頂堆。堆常用完全二叉樹表示，圖4-1是一個(gè)大頂堆的例子。

堆數(shù)據(jù)結(jié)構(gòu)常用于優(yōu)先隊(duì)列中，以維護(hù)由一組元素構(gòu)成的集合。對(duì)應(yīng)于兩類堆結(jié)構(gòu)，優(yōu)先隊(duì)列也有最大優(yōu)先隊(duì)列和最小優(yōu)先隊(duì)列，其中最大優(yōu)先隊(duì)列采用大頂堆，最小優(yōu)先隊(duì)列采用小頂堆。以下考慮最大優(yōu)先隊(duì)列。
假設(shè)現(xiàn)已建好大頂堆A，且已經(jīng)實(shí)現(xiàn)了調(diào)整堆的函數(shù)heapify（A,N,INDEX）。
下面將C代碼中需要完善的三個(gè)函數(shù)說明如下：
（1）heapMaximum(A)：返回大頂堆A中的最大元素。
（2）heapExtractMax(A)：去掉并返回大頂堆A的最大元素，將最后一個(gè)元素“提前”到堆頂位置，并將剩余元素調(diào)整成大頂堆。
（3）maxHeapInsert(A,key)：把元素key插入到大頂堆A的最后位置，再將A調(diào)整成大頂堆。
優(yōu)先隊(duì)列采用順序存儲(chǔ)方式，其存儲(chǔ)結(jié)構(gòu)定義如下：
#define PARENT(i)   i/2
typedef struct array{
int*int_array;  //優(yōu)先隊(duì)列的存儲(chǔ)空間首地址
int array_size;  //優(yōu)先隊(duì)列的長(zhǎng)度
int capacity;  //優(yōu)先隊(duì)列存儲(chǔ)空間的容量
}ARRAY;
【C代碼】
（1）函數(shù)heapMaximum
int heapMaximum(ARRAY*A){  return  (1)  ;  }
（2）函數(shù)heapExtractMax
int heapExtractMax(ARRAY*A){
int max;
max=A->int_array[0];
（2）;
A->array_size --;
heapify(A,A->array_size,0);  //將剩余元素調(diào)整成大頂堆
return max;
}
（3）函數(shù)maxHeapInsert
int maxHeapInsert(ARRAY *A,int key){
int  i,*p;
if  (A->array_size == A->capacity)    {  //存儲(chǔ)空間的容量不夠時(shí)擴(kuò)充空間
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;
}
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/6/16

信管網(wǎng)考友試題答案分享：

信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/6/16