2008年上半年软件设计师下午试卷II[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) 假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。最佳情况为 (4)，平均情况为 (5) ，最坏情况为 (6) 。

(2) 假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳、平均、最坏)

【问题3】(4分)

(1) 待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码—利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i,j)表示随机取i到j之间的一个数，包括i和j。

RANDOMIZED-PARTITION(A,p,r){

i = RANDOM(p,r);

交换(8)和(9);//注：空(8)和空(9)答案可互换，但两空全部答对方可得分

return PARTITION(A,p,r);

}

(2) 随机化快速排序是否能够消除最坏情况的发生? (10) 。(是或否)

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