2022年下半年軟件設計師下午案例分析真題答案解析（試題四）

【點擊查看：2022年下半年軟件設計師下午案例分析真題答案解析（完整版）】

【點擊查看：2022年下半年軟件設計師真題答案解析（上午綜合+下午案例）】

試題四（共15分）

閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應欄內。

【說明】

排序是將一組無序的數(shù)據(jù)元素調整為非遞減順序的數(shù)據(jù)序列的過程，堆排序是一種常用的排序算法。用順序存儲結構存儲堆中元素。非遞減堆排序的步驟是：

(1)將含n個元素的待排序數(shù)列構造成一個初始大頂堆，存儲在數(shù)組R(R[1]，R[2]，...，R[n])中。此時堆的規(guī)模為 n，堆頂元素R[1]就是序列中最大的元素，R[n]是堆中最后一個元素。

(2)將堆頂元素和堆中最后一個元素交換，最后一個元素脫離堆結構，堆的規(guī)模減1，將堆中剩余的元素調整成大頂堆;

(3)重復步驟(2)，直到只剩下最后一個元素在堆結構中，此時數(shù)組R是一個非遞減的數(shù)據(jù)序列。

【C代碼】

下面是該算法的C語言實現(xiàn)。

(1)主要變量說明

n:待排序的數(shù)組長度

R[]：待排序數(shù)組，n個數(shù)放在R[1]，R[2]，...，R[n]中

(2)代碼

【問題1】(8分)

根據(jù)以上說明和C代碼，填充C代碼中的空(1)～(4)。

【問題2】(2分)

根據(jù)以上說明和C代碼，算法的時間復雜度為(5)(用O符號表示)。

【問題3】(5分)

考慮數(shù)據(jù)序列R=(7，10，13，15，4，20，19，8)，n=8，則構建的初始大頂堆為(6)，

第一個元素脫離堆結構，對剩余元素再調整成大頂堆后的數(shù)組R為(7)。

【參考答案】

【問題1】

（1） R[i]＜R[i]

（2）Heapify(R,I,n)

（3）i>1

（4）R[1]=R[0]

【問題2】

（5）O(nlog2n)

【問題3】

（6）(20，15，19，10，4，13，7，8)

（7）(19，15，·7，·0，4，13，8)