若k是int类型变量，且有以下for语句： for(k=-1；k ＜O；k++)printf("****\n")； 下面关于语句执行情况的叙述中正确的是（）。、

B、****

C、**

D、*

B、****

C、**

D、*

定义如下变量和数组：

int k;

int a［3］［3］={9,8,7,6,5,4,3,2,1};

则下面语句的输出结果是

for（k=0;k<3;k++）printf（"%d",a［k］［k］）;

A．7 5 3

B．9 5 1

C．9 6 3

D．7 4 1

B、4

C、6

D、12

试题四（共15分）

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

设有n个货物要装入若干个容量为C的集装箱以便运输，这n个货物的体积分别为{S1，S2，．．．，Sn}，且有si≤C(1≤i≤ n)。为节省运输成本，用尽可能少的集装箱来装运这n个货物。

下面分别采用最先适宜策略和最优适宜策略来求解该问题。

最先适宜策略( firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。

最优适宜策略( bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。

【C代码】

下面是这两个算法的C语言核心代码。

(1)变量说明

n：货物数

C：集装箱容量

s：数组，长度为n，其中每个元素表示货物的体积，下标从0开始

b：数组，长度为n，b[i]表示第i+1个集装箱当前已经装入货物的体积，下标从0开始

i，j：循环变量

k：所需的集装箱数

min:当前所用的各集装箱装入了第i个货物后的最小剩余容量

m:当前所需要的集装箱数

temp：临时变量

(2)函数firstfit

int firstfit(){

inti,j；

k=0：

for(i=0；i<n；i++){

b[i]=0；

}

for（i=0；i<n；i++）{

(1)；

while(C-b[j]<s[i]){

j++;

}

(2)；

k=k>(j+1)?k：(j+1)；

}

returnk；

}

(3)函数bestfit

int bestfit() {

int i，j，min，m，temp;

k=0；

for（i=0；i<n；i++）{

b[i]=0；

}

For (i=0；i<n；i++）{

min=C；

m=k+l；

for(j=O;j< k+l；j++){

temp=C- b[j] - s[i];

if(temp>0&&temp< min){

(3) ；

m=j,

}

}

(4)；

k=k>(m+1)?k:(m+1)；

}

return k；

}

【问题1】（8分）

根据【说明】和【C代码】，填充C代码中的空(1)～(4)。

【问题2】（4分）

根据【说明】和【C代码】，该问题在最先适宜和最优适宜策略下分别采用了(5) 和(6)算法设计策略，时间复杂度分别为 (7) 和 (8)（用O符号表示）。

【问题3】（3分）

考虑实例n= 10，C= 10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况，这两种求解策略能否确保得到最优解？(11) （能或否）

B、可以去调试来理解这个结果

C、9

D、11

E、12

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下： arr：待排序数组 p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r begin,end：待排序数组的起止位置 left,right：临时存放待合并的两个子数组 n1,n2：两个子数组的长度 i,j,k：循环变量 mid：临时变量 【C代码】

inciude<stdio.h> inciude<stdlib.h> define MAX 65536 void merge(int arr[],int p,int q,int r) { int *left, *right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } for(i=0;i<n1;i++){ left[i]=arr[p+i]； } left[i]=MAX； for(i=0; i<n2; i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0; j=0; for(k=p; （1） ; k++) { if(left[i]> right[j]) { （2） ; j++; }else { arr[k]=left[i]； i++； } } } void mergeSort(int arr[],int begin,int end){ int mid; if( （3） ){ mid=(begin+end)/2; mergeSort(arr,begin,mid); （4） ; merge(arr,begin,mid,end); } }

【问题1】 根据以上说明和C代码，填充1-4。 【问题2】 根据题干说明和以上C代码，算法采用了（5）算法设计策略。 分析时间复杂度时，列出其递归式位（6），解出渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。 【问题3】 两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。

编写一个程序，求出两个数m和n的最大公约数和最小公倍数。 编程提示：求最大公约数的方法有三种： 1．从两个数中较小数的开始向下判断，如果找到一个整数能同时被m和n整除，则终止循环。设n为m和n中较小的数，则如下程序段可实现： for(k=n; k>=1; k--) if(m%k==0 && n%k ==0) break; k即为最大公约数。/* c5-2.c 求最大公约数算法1 */ #include "stdio.h" #include <stdlib.h> int main( ) { return 0; } 2．从整数1开始向上找，直至m和n中较小的数，每找到一个能同时被m和n整除的整数，将其存入一个变量中，当循环结束时，变量中存放的即为最大公约数。设n为m和n中较小的数，则如下程序段可实现： for(k=1; k<=n; k++) if(m%k="=0" && n%k="=0)" x="k;" 变量x的值即为最大公约数。 * c5-3.c 求最大公约数算法2 #include> #include <stdlib.h> int main( ) { return 0; } 3．用辗转相除法，即将求m和n的最大公约数问题转化为求其中的除数和两个数相除所得余数的公约数。每次循环中，先求两个数的余数，然后以除数作为被除数，以余数作为除数，当余数为0时结束循环，此时除数即为最大公约数。设m和n中n为较小的数，则可用如下程序段实现： b=m%n; while(b!=0) { m=n; n=b; b=m%n;} printf("%d\n",n); /* c5-4.c 求最大公约数算法3 */ #include <stdio.h> #include <stdlib.h> int main( ) { return 0; } 两个数的最大公约数和最小公倍数的关系为：最小公倍数=m*n/最大公约数,可利用此关系进行程序设计。