為幫助廣大軟考中級(jí)軟件設(shè)計(jì)師考生更好備考，信管網(wǎng)特整理匯總了軟件設(shè)計(jì)師部分下午真題、答案及解析供考生查閱，并提供免費(fèi)在線模擬答題、歷年真題免費(fèi)下載等服務(wù)，了解軟件設(shè)計(jì)師更多備考信息請(qǐng)關(guān)注信管網(wǎng)。

相關(guān)推薦：

點(diǎn)擊查看/下載：軟件設(shè)計(jì)師歷年真題匯總

點(diǎn)擊查看：軟件設(shè)計(jì)師在線培訓(xùn)課程 丨 免費(fèi)試聽課程

免費(fèi)練習(xí)：軟件設(shè)計(jì)師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)

閱讀下列說明，回答問題1至問題3，將解答填入對(duì)應(yīng)欄內(nèi)。

【說明】

快速排序是一種典型的分治算法。采用快速排序?qū)?shù)組a[p..r]排序的3個(gè)步驟如下。

1.分解：選擇一個(gè)樞軸(pivot)元素劃分?jǐn)?shù)組。將數(shù)組a[p..r]劃分為兩個(gè)子數(shù)組 (可能為空)a[p..q-1]和a[q+1..r]，使得a[q]大于等于a[p..q-1)中的每個(gè)元素，小于 a[q+1..r]中的每個(gè)元素。q的值在劃分過程中計(jì)算。

2.遞歸求解：通過遞歸的調(diào)用快速排序，對(duì)子數(shù)組a[p..q-1]和a[q+1..r]分別排序。

3.合并：快速排序在原地排序，故不需合并操作。

【問題1】

下面是快速排序的偽代碼，請(qǐng)?zhí)钛a(bǔ)其中的空缺;偽代碼中的主要變量說明如下。

a：待排序數(shù)組

p，r: 數(shù)組元素下標(biāo)，從p到r

q: 劃分的位置

x：樞軸元素

i：整型變量，用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于i的元素的值小于或等于樞軸元素的值

j：循環(huán)控制變量，表示數(shù)組元素下標(biāo)

quicksort (a，p，r){

if (p

q=partition(a，p，r) ;

quicksort(a，p，q-1);

quicksort(a，q+1，r);

}

}

partition(a，p，r){

x=a[r];i=p-1;

for(j=p;j≤r-1;j++){

if (a[j]≤x){

i=i+1;

交換a[i]和a[j]

}

}

交 (1) 和 (2) //注：空(1)和空(2)答案可互換，但兩空全部答對(duì)方可得分 return (3)

}

【問題2】

(1)假設(shè)要排序包含n個(gè)元素的數(shù)組，請(qǐng)給出在各種不同的劃分情況下，快速排序的時(shí)間復(fù)雜度，用o記號(hào)。最佳情況為 (4) ，平均情況為 (5) ，最壞情況為 (6) 。

(2)假設(shè)要排序的n個(gè)元素都具有相同值時(shí)，快速排序的運(yùn)行時(shí)間復(fù)雜度屬于哪種情況? (7) 。(最佳，平均、最壞)

【問題3】

(1)待排序數(shù)組是否能被較均勻地劃分對(duì)快速排序的性能有重要影響，因此樞軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機(jī)地取出一個(gè)元素作為樞軸元素，下面是隨機(jī)化快速排序劃分的偽代碼——利用原有的快速排序的劃分操作，請(qǐng)?zhí)畛淦渲械目杖碧?。其中，random(i，j)表示隨機(jī)取i到j(luò)之間的一個(gè)數(shù)，包括i和j。

randomized- partition(a，p，r){

i=random(p，rl);

交換 (8) 和 (9) ;//注：空(8)和空(9)答案可互換，但兩空全部答對(duì)方可得分

return partition (a，p，r);

}

(2)隨機(jī)化快速排序是否能夠消除最壞情況的發(fā)生? (10) 。(是或否)

信管網(wǎng)參考答案：

(1)A[i+1]

(2)A[r]

注：空(1)和空(2)答案可以互換，但兩空全部答對(duì)方可給分。

(3)i+1

(4)O(nlgn)或O(nlg2n)或O(nlbn)

(5)O(nlgn)或O(nlg2n)或O(nlbn)

(6)O(n2)

(7)最壞

(8)A[i]

(9)A[r]

注：空(8)和空(9)答案可以互換，但兩空全部答對(duì)方可給分。

(10)否

查看解析：www.jazzmuze.com/st/2456720911.html