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

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

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

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

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

閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題3，將解答寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
某應(yīng)用中需要對(duì)100000個(gè)整數(shù)元素進(jìn)行排序，每個(gè)元素的取值在0～5之間。排序算法的基本思想是：對(duì)每一個(gè)元素x，確定小于等于x的元素個(gè)數(shù)(記為m)，將x放在輸出元素序列的第m個(gè)位置。對(duì)于元素值重復(fù)的情況，依次放入第m-l、m-2、…個(gè)位置。例如，如果元素值小于等于4的元素個(gè)數(shù)有10個(gè)，其中元素值等于4的元素個(gè)數(shù)有3個(gè)，則4應(yīng)該在輸出元素序列的第10個(gè)位置、第9個(gè)位置和第8個(gè)位置上。算法具體的步驟為：
步驟1：統(tǒng)計(jì)每個(gè)元素值的個(gè)數(shù)。
步驟2：統(tǒng)計(jì)小于等于每個(gè)元素值的個(gè)數(shù)。
步驟3：將輸入元素序列中的每個(gè)元素放入有序的輸出元素序列。
【C代碼】
下面是該排序算法的C語(yǔ)言實(shí)現(xiàn)。
(1)常量和變量說(shuō)明
R: 常量，定義元素取值范圍中的取值個(gè)數(shù)，如上述應(yīng)用中R值應(yīng)取6
i：循環(huán)變量
n：待排序元素個(gè)數(shù)
a：輸入數(shù)組，長(zhǎng)度為n
b：輸出數(shù)組，長(zhǎng)度為n
c：輔助數(shù)組，長(zhǎng)度為R，其中每個(gè)元素表示小于等于下標(biāo)所對(duì)應(yīng)的元素值的個(gè)數(shù)。
(2)函數(shù)sort
1    void sort(int n，int a[]，int b[]){
2       int c[R]，i；
3   for (i=0；i< (1) ：i++){
4     c[i]=0；
5       }
6       for(i=0；i7     c[a[i]] =   (2)  ；
8       }
9   for(i=1；i10    c[i]=  （3）
11      }
12  for(i=0；i13    b[c[a[i]]-1]=  (4)   ；
14    c[a[i]]=c[a[i]]-1；
15      }
16    }
?【問(wèn)題1】（8分）
根據(jù)說(shuō)明和C代碼，填充C代碼中的空缺(1)～(4)。
?【問(wèn)題2】（4分）
根據(jù)C代碼，函數(shù)的時(shí)間復(fù)雜度和空間復(fù)雜度分別為 (5) 和 (6) （用O符號(hào)表示）。
?【問(wèn)題3】（3分）
根據(jù)以上C代碼，分析該排序算法是否穩(wěn)定。若穩(wěn)定，請(qǐng)簡(jiǎn)要說(shuō)明（不超過(guò)100字）；若不穩(wěn)定，請(qǐng)修改其中代碼使其穩(wěn)定（給出要修改的行號(hào)和修改后的代碼）。
信管網(wǎng)試題答案與解析：www.jazzmuze.com/exam/ExamDayAL.aspx?t1=4&day=2025/4/27

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

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

关闭