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

相關推薦：

點擊查看/下載：軟件設計師歷年真題匯總

點擊查看：軟件設計師在線培訓課程 丨 免費試聽課程

免費練習：軟件設計師考試題庫(模擬試題、章節(jié)練習、每日一練)

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

【說明】

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

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

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

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

【問題1】

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

a：待排序數(shù)組

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

q: 劃分的位置

x：樞軸元素

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

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

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)答案可互換，但兩空全部答對方可得分 return (3)

}

【問題2】

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

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

【問題3】

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

randomized- partition(a，p，r){

i=random(p，rl);

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

return partition (a，p，r);

}

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

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

(1)A[i+1]

(2)A[r]

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

(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)答案可以互換，但兩空全部答對方可給分。

(10)否

查看解析：m.xiexiliangjiufa.com/st/2456720911.html