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

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

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

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

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2025/1/24）

試題四（共15分）
閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
排序是將一組無序的數(shù)據(jù)元素調(diào)整為非遞減順序的數(shù)據(jù)序列的過程，堆排序是一種常用的排序算法。用順序存儲結(jié)構(gòu)存儲堆中元素。非遞減堆排序的步驟是：
(1)將含n個元素的待排序數(shù)列構(gòu)造成一個初始大頂堆，存儲在數(shù)組R(R[1]，R[2]，...，R[n])中。此時堆的規(guī)模為 n，堆頂元素R[1]就是序列中最大的元素，R[n]是堆中最后一個元素。
(2)將堆頂元素和堆中最后一個元素交換，最后一個元素脫離堆結(jié)構(gòu)，堆的規(guī)模減1，將堆中剩余的元素調(diào)整成大頂堆;
(3)重復(fù)步驟(2)，直到只剩下最后一個元素在堆結(jié)構(gòu)中，此時數(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代碼，算法的時間復(fù)雜度為(5)(用O符號表示)。
【問題3】(5分)
考慮數(shù)據(jù)序列R=(7，10，13，15，4，20，19，8)，n=8，則構(gòu)建的初始大頂堆為(6)，
第一個元素脫離堆結(jié)構(gòu)，對剩余元素再調(diào)整成大頂堆后的數(shù)組R為(7)。
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2025/1/24

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

信管網(wǎng)cnit**************：
（1）r[j]＞r[2j]&&r[j]＞r[2j+1] （2） （3）i＞=1 （4）n-- （5）o（n^2） （6） （7）

信管網(wǎng)qcfn****：
一、 i＞2 r[1] ＝ r[0] 二 o（nlgn） 三、3 20 15 19 10 4 13 7 8 19 15 13 10 4 8 7

信管網(wǎng)cnit**************：
問題1 r[i] ＜ r[j] heapify（r,1,i-1） i＞=1 r[1]=r[0] 問題2 o（nlog2^n） 問題3 20 7 15 10 4 13 9 8 8 7 15 10 4 13 19

信管網(wǎng)cnit**************：
o（n） r（20,7,10,13,15,4,19,8） r（19,8,7,10,13,15,4）

信管網(wǎng)cnit**************：
（1）r[i] ＞ r[j]； （2）heapify（r,n/2,n-i）； （3）i ＞ n/ 2； （4）r[1] ＝ r[0] ； （5）o（n2）； （6）（20, 15, 19 , 13, 7, 4,10 , 8 ） （7）（）

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