2008年上半年軟件設(shè)計(jì)師下午試卷II[2]

軟件設(shè)計(jì)師 責(zé)任編輯:xzj1013 2008-09-18

添加老師微信

備考咨詢

加我微信

摘要:QUICKSORT(A,p,r){if(p<r){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)答案可

  QUICKSORT(A, p, r){

if (p < r){

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】(5分)

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

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

【問題3】(4分)

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

RANDOMIZED-PARTITION(A,p,r){

i = RANDOM(p,r);

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

return PARTITION(A,p,r);

}

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

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  

更多資料
更多課程
更多真題
溫馨提示:因考試政策、內(nèi)容不斷變化與調(diào)整,本網(wǎng)站提供的以上信息僅供參考,如有異議,請考生以權(quán)威部門公布的內(nèi)容為準(zhǔn)!

軟考備考資料免費(fèi)領(lǐng)取

去領(lǐng)取

!
咨詢在線老師!