2022年下半年軟件設(shè)計(jì)師下午案例分析真題答案解析（試題四）

【點(diǎn)擊查看：2022年下半年軟件設(shè)計(jì)師下午案例分析真題答案解析（完整版）】

【點(diǎn)擊查看：2022年下半年軟件設(shè)計(jì)師真題答案解析（上午綜合+下午案例）】

試題四（共15分）

閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

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

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

(2)將堆頂元素和堆中最后一個(gè)元素交換，最后一個(gè)元素脫離堆結(jié)構(gòu)，堆的規(guī)模減1，將堆中剩余的元素調(diào)整成大頂堆;

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

【C代碼】

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

(1)主要變量說明

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

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

(2)代碼

【問題1】(8分)

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

【問題2】(2分)

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

【問題3】(5分)

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

第一個(gè)元素脫離堆結(jié)構(gòu)，對(duì)剩余元素再調(diào)整成大頂堆后的數(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)