●试题一阅读以下算法说明和流程图，回答问题1和问题2。【算法说明】下面是一段插入排序的程序，将R[k+1]插入到R[1…k]的适当位置。R[0]=R[k+1]；j=k；while (R[j]>R[0]){R[j+1]=R[j]；j--；}R[j+1]=R[0]；【流程图】【测试用例设计】(while循环次数为0、1、2次)【问题1】指出算法的流程图中 (1) ～ (3) 处的内容。【问题2】指出测试用例设计中 (4) ～ (9) 处的内容。

A.R_SDHTRIPARA

B.R_SDHOPTPARA

C.R_SDTB

D.R_SDH

以下程序的输出结果是_______。 main() {union { char i[2]； int k； }r； r.i[0]=2； r.i[1]=0； printf("%d\n",r.k)； }

A．2

B．1

C．0

D．不确定

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

【说明】

假设一个剧场有N*N个座位，顾客买票时可以提出任意有效的座号请求。下面用二维数组a[N][N]模拟剧场中的座位，a[i][j]圆等于0表示

第i排第j列(0≤i，j≤N-1)的票尚未售出。

函数int Find(int a[][N]，int R，int*row，int*col)的功能是：在部分票已售出的情况下，找出剧场中的R*R个空座位，要求这些座位

的排列形成一个正方形。若找到满足要求的一个座位排列，则函数返回1，并算出该正方形左上角的行、列号；若未找到，则返回0。

例如，一个7X7个座位的剧场如下图(a)所示，已售出部分座位的剧场如下图(b)所示，图中阴影部分表示已售出的座位，从下图(b)中找出

的3X3正方形空座位如下图(c)中斜线区所示。

【函数】

int Find(int a[][N] int R,int*row,iht*col)

{int i，j，k，c，t；int FOUND=0；

for(i=0；!FOUND&&i＜N-R+1；i++) { /*从第0排开始查找*/

(1)；

while (j＜N-R+1&&!FOUND) {

for (k=0；(2)&&a[i][j+k]==0；k++)； /*查找第i排连续的R个空座位*/

if (k＞=R) { /*找到第i排连续的R个空座位*/

for (c=0；c＜R；c++) { /*查找其余的R*(R-1)个座位*/

for (t=1；t＜R；t++)

if (a[(3)][j+c]!=0) break；

if (t＜R) break；

}/*for*/

if ((4)) FOUND=1；

}/*if*/

(5；

}/*while*/

}/*fori*/

if (FOUND) {

*row=i-1； *col=j-1； /*计算正方形区域的左上角坐标*/

return 1；

}

return 0；

}

阅读以下说明和流程图，回答问题1-2，将解答填入对应的解答栏内。

[说明]

下面的流程图采用欧几里得算法，实现了计算两正整数最大公约数的功能。给定正整数m和 n，假定m大于等于n，算法的主要步骤为：

(1)以n除m并令r为所得的余数；

(2)若r等于0，算法结束；n即为所求；

(3)将n和r分别赋给m和n，返回步骤(1)。

[流程图]

[问题1] 将流程图中的(1)～(4)处补充完整。

[问题2] 若输入的m和n分别为27和21，则A中循环体被执行的次数是(5)。

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

【说明】

为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)

[算法]

1．变量声明

X: Data Type

i,j,low, high,mid,r:0..n

2．每循环一次插入一个R[i]

循环：i以1为步长，从2到n，反复执行。

(1)准备

X←R[i];(1); high←i-1;

(2)找插入位置

循环：当(2)时，反复执行。

(3)

若X.key＜R[mid].key

则high←mid-1;

否则 (4)

(3)后移

循环：j以-1为步长，从(5)，反复执行。

R[j+1]←R[j]

(4)插入

R[low]←X

3．算法结束

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

【说明2.1】

以下C语言函数用二分插入法实现对整型数组a中n个数的排序功能。

【函数2.1】

void fun1 (int a[])

{ int i,j,k,r,x,m;

for(i=2;i＜=n;i++)

{ (1);

k=1;r=i-1;

while(k＜=r)

{ m=(k+r)/2;

if(x＜a[m])r=m-1;

else (2);

}

for(j=i-1;j＞=k;j--)

a[j+l]=a[j];

(3);

}

}

【说明2.2】

以下程序可以把从键盘上输入的十进制数(long型)以二～十六进制形式输出。

【程序2.2】

include＜stdio.h＞

main()

{ charb[16]={'0','l','2','3 ,4,'5','6','7','8','9','A','B','C','D','E','F'};

int c[64],d,i=0,base;

long n;

printf("enter a number:\n");

scanf("%1d",&n);

printf("enter new basc:\n");

scanf("%d", &base);

do

{ c[i]=(4);

i++; n=n/base;

} while(n!=0);

printf("transmite new base:\n");

for(--i;i＞=0;--i)

{ d=c[i];

printf("%c",(5));

}

}

阅读以下说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

说明

某单位举办了一场知识竞赛，参加竞赛的选手为300名，依次从1～300进行编号。竞赛时间为9:00～11:00。8道竞赛题目依次从“A”～“H”编号，选手可按任意次序答

题，每完成一道题目，可立即提交答案。若答案正确(Y)，则选择其他题目进行解答，否则，可继续做该题目或选择其他题目进行解答，直至竞赛结束。

选手提交答案的情况及判定结果由专人即时录入，录入的数据如表1所示，对竞赛情况进行统计和排名的结果如表2所示。

统计和排名的规则如下：

1．若选手X在竞赛时提交的题目P解答正确，则解答该题目所用时间如下计算；

解答题目P的用时=提交题目P正确的时间-竞赛的开始时间+罚时

罚时=提交题目P错误解答的次数×20

例如=表1中14号选手在10:27提交了题目A的正确解答，因此该选手正确解答该题目所用时间为87分钟，由于之前的两次提交错误解答，罚时为2×20=40分钟，所以14号选手解答题目A的用时=87+40=127(分钟)。

2．已经提交正确答案的题目再次提交时不再计算。

3．竞赛结束时，选手的总用时为所有解答正确的题目用时累加所得，解答不正确的题目不计时。

4．排名时，完成题目数量多者排名靠前；若完成的题目数相同，则用时少者排名靠前；若完成的题目数和所用时间均相等，则名次相同；完成题目数为。的选手不参加排名。

函数void Statistic()的功能是：读取输入数据，进行统计、排名并输出结果。

define MAXN 300

typedef stmct{

int no； /*选手编号*/

int num; /*完成的题目数量*/

int time; /*完成题目的总用时*/

int d[8]; /*d[i]用于记录提交第i个题目错误答案的次数*/

int a[8]; /*a[i]用于记录第i个题目是否已经提交正确答案*/

}Info;

void Statistic() {

char ch,pass;

int i,j,k,h,m,t,time,Maxlndex;

Info R[MAXN+1 ];

for(i=1; i＜=MAXN; i++){ /*数组R的元素置初值0*/

R[i].no = 0;R[i].num = 0; R[i].time = 0;

for(j=0; j＜8; j++) {R[i].d[j] = 0; R[i].a[j] = 0;}

}/*for*/

MaxIndex = 0;

while (1){

/*录入一名选手提交答案的信息(小时：分钟，选取手编号，题目号，是否正确)*/

scanf("%d:%d,%d,%c,%c",&h,&m,&k,&ch,&pass);

if(h==0) break;

R[k].no = k; /*k为选手编号码*/

time=(1); /*计算答题时间，以分钟为单位*/

if(isupper(ch)) ch = 'a' + ch- 'A';

if(pass != 'Y' && pass != 'y') {R[k].d[ch-'a']++; continue;}

if (R[k].a[ch-'a']==1) continue;

R[k].a[ch-'a'] = 1;

R[k] .num++;

R[k].time +=(2);

if (k ＞ MaxIndex) Maxlndex = k;

}/*while*/

for(i=l; i＜MaxIndex; i++) { /*选取择排序*/

for(t=i,j=i+1; j＜=Maxlndex; j++)

if(R[t].num＜R[j].num|| (3))t=j;

if((4)) {R[0]=R[t];R[t]=R[i];R[i]=R[0];}

}/*for*/

k=1; R[0] = R[l];

for(i=1; i＜=Maxlndex; i++) /*输出排名情况*/

if (R,[i].num ＞ 0) {

if(R[i].num!=R[0].num||R[i].time!=R[0].time) k++；

R[0]=(5)；

printf("%d：%3d %4d %5d\n",k,R[i].no,R[i]．num,R[i]．time)；

)/*if*l<

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

【说明】

下面的程序为堆排序程序，其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的，是在主函数中说明的结构数组，它含有要排序的n个记录。

【程序】

Void adjust(i，n)

Int i，n；

{

iht k,j;

element extr;

extr=r[i];

k=i;

j=2*i;

while (j＜=n )

{if ((j＜n) && (r[j].key＜r[j+1].key))

(1);

if (extr. key＜r[j].key)

{

r[k]=r[j];

k=j;

(2);

}

else

(3);

}

r[k]=extr;

}

/*让i从┗i/2┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。*/

void heapsort (r,n)

list r;

int n;

{

int i,1;

element extr;

for (i=n/2;i＞=1;- -i)

(4); /* 建立初始堆*/

for (k--n;k＞=2;k- -)

{

extr=r[1];

r[1]=r[k];

r[k]=extr;

(5);

}

}

阅读下列算法说明和流程图1，回答问题1至问题3，将解答填入答题纸的对应栏内。

【算法说明】

某旅馆共有N间客房。每间客房的房间号、房间等级、床位数以及占用状态分别存放在数组ROOM、RANK、NBED和STATUS中。房间等级值为1、2或3。房间的状态值为0(空闲)或1(占用)。客房是以房间(不是床位)为单位出租的。

本算法根据几个散客的要求预订一间空房。程序的输入为：人数M，房间等级要求R(R=0表示任意等级都可以)。程序的输出为：所有可供选择的房间号。

流程图1描述了该算法。

【问题1】

假设当前该旅馆各个房间的情况见表3。

当输入M=4，R=0时，该算法的输出是什么？

【问题2】

如果等级为r的房间每人每天的住宿费为RATE(r),RATE为数组。为使该算法在输出每个候选的房间号RM(J)后，再输出这批散客每天所需的总住宿费DAYRENT(J)，流程图1的β所指框中的最后处应增加什么处理？

【问题3】

如果限制该算法最多输出K个可供选择的房间号，则在流程图1的α所指的判断框应改成什么处理？

【流程图1】(如图2所示)

图2