以下程序中的变量已正确定义 for（int i=0;i＜4;i++,i++） for（int k="1;k<3;k++）;printf（“*”）;"＞ A、********

试题二

下面程序中函数fun的功能是：在含有10 个元素的s数组中查找最大数，及最大数所在位置(即，下标值)，最大数可能不止一个。最大数作为函数值返回，最大数的个数通过指针变量n传回，所在位置由数组pos传回。

例如：

若输入 2 8 5 7 8 4 5 3 2 8

则应输出：

The max: 8

Total: 3 //最大数出现次数

The positions： 1 4 9

请补充下列空缺:

include<stdio.h>

include<conio.h>

define M 10

int fun(int *a, int *n, int pos[])

{int i, k,max=-32767;

(1)

for(i=0; i<M; i++)

if( (2) ) max=a[i];

for(i=0; i<M; i++)

if( (3) )pos[k++]=i;

*n=k;

return max;

}

main()

{int a[M], pos[M], i=0, j, n;

clrscr();

printf("Enter 10 number :");

for(i=0; i<M; i++)scanf("%d", （4）);

j=fun( (5) );

printf("The max: %d\n", j);

printf("Total: %d",n);

printf("The position:");

for(i=0; i<n; i++ ) printf("%4d", pos[i]);

printf("\n");

}

试题四（共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) （能或否）

已知i，j，k为int型变量，若从键盘输入：1，2，3<回车>，使i的值为1，j的值为2，k的值为3，以下选项中正确的输入语句是

A．scanf ("%2d%2d%2d"，＆i，＆j，＆k)；

B．scanf ("%d %d %d"，＆i，＆j，＆k)；

C．scanf ("%d，%d，%d"，＆i，＆j，＆k)；

D．scanf ("i=%d，j=%d，k=%d"，＆i，＆j，＆k)；

已知i、j、k为int型变量，若从键盘输入：1，2，3<回车>，使i的值为1、J的值为2、k。的值为3，以下选项中正确的输入语句是

阅读下列说明和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）。

【题目描述】

第 6 题已知i、j、k为int型变量，若从键盘输入：1，2，3<回车>，使i的值为1、J的值为2、k。的值为3，以下选项中正确的输入语句是

【我提交的答案】：C

【参考答案与解析】： 正确答案：C

答案分析：

【我的疑问】（如下，请求专家帮助解答）

A选项答案为何是010203？谢谢咯！

●试题一

阅读下列算法说明和算法，将应填入(n)处的字句写在答卷的对应栏内。

【算法说明】

某英汉词典文件包含N个记录(N>1)，每个记录有两个字段：一个是英文单词，另一个是相应的汉语解释。各个记录按英文单词的词典顺序排列，各英文单词并不重复。

本算法用于维护、更新该英汉词典文件。维护、更新的方法是：首先输入一个英文单词及其汉语解释，然后在该词典中查找输入的英文单词，若找到，则用输入的汉语解释更新原有的解释；若找不到，则需要将输入的英文单词及其汉语解释插入到该词典的适当位置，使各记录仍按英文单词的词典顺序排列。

【算法】

第一步读入英汉词典文件，并将读入的N个英文单词依次存放在字符串数组ENG中，将相应的汉语解释依次存放在字符串数组CN中。数组元素CN(i)给出了数组元素ENG(i)的解释。

第二步输入英文单词及其汉语解释，将它们分别存放在字符串变量E和C中。若E为空串或都是空格，则转向第四步。

第三步根据变量E的值，用二分法在数组ENG中查找。具体步骤如下：

1.1→L，N→H

2.INT((L+H)／2)→K

3.若E=ENG(K)，则C→CN(K)，转向第二步

若E<ENG(K)，则K-1→ (1) ；若E＞ENG(K)，则K+1→ (2)

4.若H<L则

对I=N，L，-1(始值，终值，增量)循环执行：

ENG(I)→ENG(I+1)

CN(I)→CN(I+1)

然后，将E和C分别存入 (3) 和 (4) ，N+1→N最后转向第二步

否则，转向 (5)

第四步将数组ENG和CN输出，形成新的英汉词典文件，算法结束。

试题四（共15分）

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

【说明】

用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间（所有作业被处理的时间之和）最少。

算法步骤：

（1）确定候选解上界为R短的单台处理机处理所有作业的完成时间m，

（2）用p（x,y,k）=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间 内处理完成，则p（x,y,k）=p（x-ak,y,k-1）||p（x,y-bk,k-1）（||表示逻辑或操作）。

（3）得到最短处理时问为min（max（x，y））。

【C代码】

下面是该算法的C语言实现。

（1）常量和变量说明

n: 作业数

m: 候选解上界

a: 数组，长度为n，记录n个作业在A上的处理时间，下标从0开始

b: 数组，长度为n，记录n个作业在B上的处理时间，下标从0开始

k: 循环变量

p: 三维数组，长度为（m+1）*（m+1）*（n+1）

temp: 临时变量

max: 最短处理时间

（2）C代码

include<stdio.h>

int n, m;

int a[60], b[60], p[100][100][60];

void read(){ /*输入n、a、b，求出m，代码略*/}

void schedule(){ /*求解过程*/

int x,y,k;

for（x=0；x<=m；x++）{

for(y=0；y<m；y++）{

（1）

for（k=1；k<n；k++）

p[x][y][k]=0；

}

}

for（k=1；k<n；k++）{

for（x=0；x<=m；x++）{

for（y=0；y<=m；y++）{

if（x - a[k-1]>=0） （2） ；

if（ （3） ）p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]);

}

}

}

}

void write(){ /*确定最优解并输出*/

int x，y，temp，max=m;

for（x=0；x<=m；x++）{

for（y=0;y<=m;y++）{

if( （4） ）{

temp=（5） ；

if（temp< max）max = temp;

}

}

}

printf("\n%d\n"，max）,

}

void main(){read();schedule();write();}

【问题1】 （9分）

根据以上说明和C代码，填充C代码中的空（1）～（5）。

【问题2】（2分）

根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。

【问题3】（4分）

考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x1,x2,x3,x4,x5,x6）表示，其中若第i个作业在A上赴理，则xi=l，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。

fun(a，i，j)； } } main { int K[]={2，6，1，8}，i； fun(x，0，3)； for(i=0；i<1；i++)printf("％2d"，x[i])； printf("＼n")； }

A.1，2，6，8

B.8，6，2，1

C.8，1，6，2

D.8，6，1，2

B、3

C、2

D、1