– I feel awful. I’ve left your book somewhere. –()(A) Oh! How could you do that!(B) Don’t worry. I never liked it anyway.(C) Cheer up. I’ll buy anthor one.(D) It’s not your fault.

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。

【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot时，采用从left、right和mid=[(left+right)/2]中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为T，left和right是待排序子区间的最左端点和最右端点。

void quicksort (int a[], int left, int right) {

int temp;

if (left＜right) {

hat pivot = median3 (a, left, right); //三者取中子程序

int i = left, j = right-1;

for(;;){

while (i ＜j && a[i] ＜ pivot) i++;

while (i ＜j && pivot ＜ a[j]) j--;

if(i＜j){

temp = a[i]; a[j] = a[i]; a[i] = temp;

i++; j--;

}

else break;

}

if (a[i] ＞ pivot)

{temp = a[i]; a[i] = a[right]; a[right] = temp;}

quicksort( (1) ); //递归排序左子区间

quieksort(a,i+1 ,right); //递归排序右子区间

}

}

void median3 (int a[], int left, int right)

{ int mid=(2);

int k = left;

if(a[mid] ＜ a[k])k = mid;

if(a[high] ＜ a[k]) k = high; //选最小记录

int temp = a[k]; a[k] = a[left]; a[left] = temp; //最小者交换到 left

if(a[mid] ＜ a[right])

{temp=a[mid]; a[mid]=a[right]; a[right]=temp;}

}

消去第二个递归调用 quicksort (a,i+1,right)。 采用循环的办法:

void quicksort (int a[], int left, int right) {

int temp; int i,j;

(3) {

int pivot = median3(a, left, right); //三者取中子程序

i = left; j = righi-1;

for (;; ){

while (i＜j && a[i] ＜ pivot)i++;

while (i＜j && pivot ＜a[j]) j--;

if(i ＜j) {

temp = a[i]; a[j]; = a[i]; a[i]=temp;

i++; j--;

}

else break;

}

if(a[i]＞pivot){(4);a[i]=pivot;}

quicksoft ((5)); //递归排序左子区间

left = i+1;

}

}

B 宽度优先（种子染色法）

5．关键路径

几个定义： 顶点1为源点，n为汇点。

a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;

b. 顶点事件最晚发生时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);

c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表示，则Ee[I] = Ve[j];

d. 边活动最晚开始时间 El[I], 若边I由<j,k>表示，则El[I] = Vl[k] – w[j,k];

若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。

求解方法：

a. 从源点起topsort,判断是否有回路并计算Ve;

下列程序段的结果为______。 A="ABBACDDCBA" For I=6 To 2 Step-2 X=Mid(A,I,I) Y=Left(A,I) Z=Right(A,I) Z=X&Y&Z Next I Print Z

A．ABA

B．AABAAB

C．BBABBA

D．ABBABA

下列程序段的结果为

A="ABBACDDCBA"

For i=6 To 2 Step-2

X=Mid(A,i,i)

Y=Left(A,i)

Z=Right(A,i)

Z=X&Y&Z

Next

Print Z

A．ABC

B．AABAAB

C．BBABBA

D．ABBABA

下列程序段的结果为_______。 A="ABBACDDCBA" For I=6 To 2 Step -2 X=Mid(A，I，I) Y=Left(A，I) Z=Right(A，I) Z=X & Y & Z Next I Print Z

A．ABA

B．AABAAB

C．BBABBA

D．ABBABA