在一个长度为n的数组中找到第k大的数字，平均的算法时间复杂度最低的是（）

阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。

[说明]

函数int psort(int a[],int n)实现将含n个整数的数组a[]的不同元素按从小到大顺序存于数组a[]中。实现方法是从未确定的元素列中找到最小元素并将a[]的第i最小元素交换至a[i]位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。

[C函数]

int psort(int a[],int n)

{int i,J,k,P;

for(i=0,k=0;i＜(1);i++){

for(j=i+1, (2) ;j＜n; j++)

if(a[p]＞a[j])

p=j;

if(p!=i){

t=a[p];

a[p]=a[i];

a[i]=t;

}

if((3) ) k++;

else if((4) ＜a[i])

(5)=a[i];

}

return k;

}

int a[]={5,7,5,6,4,3,4,6,7};

main()

{int k,n;

for(k=0;k＜(Sizeof a)/Sizeof(int);k++)

printf("%5d",a[k]);

printf ("\n\n");

n=psort(a,(sizeof(a))/sizeof(int));

for(k=0;k＜n;k++)

printf("%5d",a[k]);

printf("\n\n");

}

A.访问第i个元素和求第i个元素的直接前趋(2≤i≤n)

B.在第i(1≤i≤n)个元素后面插入一个新元素

C.删除数组第i个元素

D.顺序查找与给定值k相等的元素

试题四（共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上处理。

阅读以下说明和C函数，将应填入(n)处对应栏内。

[说明]

基于管理的需要，每本正式出版的图书都有一个ISBN号。例如，某图书的ISBN号为“978-7-5606-2348-1”。

ISBN号由13位数字组成：前三位数字代表该出版物是图书(前缀号)，中间的9个数字分为三组，分别表示组号、出版者号和书名号，最后一个数字是校验码。其中，前缀号由国际EAN提供，已经采用的前缀号为978和979；组号用以区别出版者国家、地区或者语言区，其长度可为1～5位；出版者号为各出版者的代码，其长度与出版者的计划出书量直接相关；书名号代表该出版者该出版物的特定版次；校验码采用模10加权的算法计算得出。

校验码的计算方法如下：

第一步：前12位数字中的奇数位数字用l相乘，偶数位数字用3相乘(位编号从左到右依次为13到2)。

第二步：将各乘积相加，求出总和S。

第三步：将总和S除以10，得出余数R。

第四步：将10减去余数R后即为校验码V。若相减后的数值为10，则校验码为0。

例如，对于ISBN号“978-7-5606-2348-1”，其校验码为1，计算过程为：

S=9×1+7×3+8×1+7×3+5×1+6×3+0×1+6×3+2×1+3×3+4×1+8×3=139

R=139mod 10=9

V=10-9=1

函数check(char code[])用来检查保存在code中的一个ISBN号的校验码是否正确，

若正确则返回true，否则返回false。例如，ISBN号“978-7-5606-2348-1”在code中的

存储布局如表3-1所示(书号的各组成部分之间用“-”分隔)：

表3-1 数组code的内容示例

在函数check(char code[])中，先将13位ISBN号放在整型数组元素tarr[0]～tarr[12]中(如表3-2所示，对应ISBN号的位13～位1)，由tarr[0]～tarr[11]计算出校验码放入变量V，再进行判断。

表3-2 数组tarr的内容示例

[C函数]

boo1 cheCk(char code[])

{

int i，k=0;

intS=0，temp=0；

int V；

int tarr[13]={0};

if (Strlen(code) ＜17} return falSe;

for(i=0; i＜17; i++) /*将13位ISBN号存入tarr*/

if(code[i]!='-')

tarr (1)____ =code[i]-'0';

for(i=0; (2)_____ ; i++ ); {

if (i%2)

S+= (3)______ ;

else

S+= (4)______ ;

}

v=((5)______ ==C)？0:10-s%10;

if(tart[12]==v)

return true ;

return false;

}

define N 4

void sort(int a[][N])

{ int i, j, k, t;

for (i=0; i＜N;i++)

for (j=0; j＜N-1:j++)

for (k= 【 13 】 ; k＜N;K++)

/* 判断行下标是否为偶数来确定按升序或降序来排序 */

if (【 14 】 ？ a[i][j]＜a[i][k]); a[i][j]＞a[i][k])

{ t = a[i][j];

a[i][j]=a[i][k];

a[i][k] = t;

}

}

void outarr(int a[N][N])

{ …… }

main()

{ int aa[N][N]={{2,3,4,1},{8,6,5,7},{11,12,10,9},{15,14,16,13}};

outarr(aa); /* 以矩阵的形式输出二维数组 */

sort(aa);

outarr(aa);

}

A.分治

B.动态规划

C.贪心

D.回溯

【流程图】注:循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为: 循环控制变量=初值，终值