以下程序段的输出结果是（)。 int k,n,m; n=10;m=1;k=1; while （k＜=n) {m="m*2;k=k+4;}" printf（"%d\n",m);＞ A、8

下面程序段中，search(a，n，k)的功能是在数组a的前n(n≥1)个元素中找出第k(1≤k≤n)小的值。这里假设数组a中各元素的值都不相同。 define MAXN 100 int a[MAXN]，n，k； int search_c(int a[]，int n，int k) { int low，high，i，j，m，t； k一一；low=0；high=n一1； do { i=low；j=high； (1) ； do { while(i<j &&t<a[j])j一一； if(i<j)a[i++]=a[j]； while(i％j&&t>=a[i])i++； if(i<j)a[j一一]=a[i]； } while(i<j)； a[i]=t； if (2)； if(i<k) low=(3) ； else high=(4) ； } while (5) ； return(a[k])； }

●试题二

阅读下列函数说明和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+1］=a［j］；

(3) ；

}

}

【说明2．2】

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

【程序2．2】

#include<stdio．h>

main()

{char b［16］={′0′，′1′，′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：kn″)；

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) )；

}

}

下列程序执行后，k的值是 public class TestDemo { public static void main(String args[ ]) { int m=3，n=6，k=0； while((m++)<(--n) ) ++k； System.out.println(k)； } }

A．0

B．1

C．2

D．3

下列给定程序中，函数proc的功能是找出100～m(m 不大于1000)之间百位数字加十位数字等于个位数字的所有整数，把这些整数放在s所指的数组中，个数作为函数值 返回。 请修改程序中的错误，使它能得到正确结果。 注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。 试题程序： include<stdio．h> define M 1000 int proc(int*S．int n) { int i，j，k，a，b，c； j=0； for(i=100；i<n；i++) { ／／****found**** k=n： a=k％10； k／=10； b=k％10； c=k／10； if(a==b+c) ／／****found**** s[j]=i： } return j； } void main { int a[M]，m，num=0，i； do { printf("＼nEnter m(<=1000)：")； scanf("％d"，＆m)； } while(m>1000)； num=proc(a，m)； printf("＼n＼nThe result：＼n")； for(i=0；i<num；i++) printf("％5d"，a[i])； printf("＼n＼n")； }

以下将ah，…am，和am+1…an，两个有序序列(它们相应的关键字值满足Kh≤Km，Km+1≤…Kn，)合并成一个有序序列Rh，…，Rn，(使其关键字值满足Kh，'≤…≤Kn，')。请分析算法，并在______上填充适当的语句。

void merge(list a,list R,int h,int m,int n)

{i=h;k=h;j=m+1;

while((i＜m)&&(j＜=n))

{ if(a[i].key<=a[i].key){R[k]=______;______;}

else{R[k]=______;______;}

k++;

}

while(i＜=______){R[k]=a[i];i++;k++;)

while(j＜=______){R[k]=a[j];j++;k++;}

}

此算法的执行时间为______。

试题二（共 15 分）

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

[说明]

下面 C 程序代码的功能是：对于输入的一个正整数 n（100≤n<1000） ，先判断其是否是回文数（正读反读都一样的数） 。若不是，则将 n 与其反序数相加，再判断得到的和数是否为回文数，若还不是，再将该和数与其反序数相加并进行判断，依此类推，直到得到一个回文数为止。例如，278 不是回文数，其反序数为 872，相加后得到的 1150还不是回文数，再将 1150 与其反序数 511 相加，得到的 1661 是回文数。 函数 int isPalm(long m)的功能是：将正整数 m的各位数字取出存入数组中，然后判断其是否为回文数。若 m是回文数则返回 1，否则返回 0。

[C 程序代码]

#include <stdio.h>

#include <stdlib.h>

int isPalm(long m)

{ /*判断 m是否为回文数*/

int i = 0, k = 0;

char str[32];

while (m > 0) { /*从个位数开始逐个取出 m的各位数字并存入字符数组 str*/

str[k++] = （1） + '0';

m = m / 10;

}

for(i = 0; i < k/2; i++) /*判断 str中的 k 个数字字符序列是否是回文*/

if ( str[i] != str[ （2） ] ) return 0;

return 1;

}

int main( )

{

long n, a, t;

printf("input a positive integer:"); scanf("%ld",&n);

if (n < 100 || n > =1000) return -1 ;

while( （3） ) { /*n 不是回文数时执行循环*/

printf("%ld -> ", n);

for(a = 0, t = n; t > 0; ) { /*计算 n 的反序数并存入 a*/

a = （4） *10 + t % 10; t = t / 10;

} /*end of for*/

n = （5） ; /*与反序数求和*/

} /*end of while*/

printf("%ld\n",n);

system("pause"); return 0;

}

●试题五

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

【程序5说明】

设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值部分(设为一个字符)和用"()"括起来的各子树的列表(如有子树的话)，各子列表间用"，"分隔。例如下面的三叉树可用列表a(b(c，d)，e，f(g，h，i))表示。

本程序输入列表，生成一棵M叉树，并由M叉树输出列表。假定输入无错误。

【程序5】

#include<stdio.h>

#include<stdli

B．h>

#define M 3

typedef struct node{char val;

struct node*subTree［M］;

}NODE;

char buf［255］,*str=buf;

NODE*d=NULL

NODE*makeTree()/*由列表生成M叉树*/

{int k;NODE*s;

s= (1) ;

s->val=*str++;

for(k=0;k<M;k++)s->subTree［k］=NULL;

if(*str=′(′){

k=0;

do{str++;

s->subTree［k］= (2) ;

if(*str==′)′){str++;break;}

k=k+1;

}while( (3) );

}

return s;

}

void walkTree(NODE*t)/*由M叉树输出列表*/

{int i;

if(t!=NULL){

(4)

if(t->subTree［0］==NULL)return;

putchar(′(′);

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

(5) ;

if(i!=M-1&&t->subTree［i+1］!= NULL)

putchar(′，′)；

}

putchar(′)′)；

}

}

void main()

{printf("Enter exp：");

scanf("%s",str);

d=makeTree();

walkTree(d);putchar(′＼n′);

}

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

[说明]

为网球比赛的选手安排比赛日程。设有n(n=2m)位选手参加网球循环赛，循环赛共进行n-1天，每位选手要与其他n-1位选手赛一场，且每位选手每天赛一场，不轮空。

设n位选手被顺序编号为1，2，…，n，比赛的日程表是一个n行n-1列的表，第i行j列的内容是第i号选手第j天的比赛对手。用分治法设计日程表，就是从其中一半选手(2m-1位)的比赛日程导出全体2m选手的比赛日程。从众所周知的只有两位选手的比赛日程出发，反复这个过程，直至为n位选手安排好比赛日程为止。

如两位选手比赛日程表如下所示：

如四位选手比赛日程表如下所示：

函数中使用的预定义符号如下：

define M 64

int a[M+1][M];

[函数]

voidd main(){

int twoml,twom,i,j,m,k;

printf("指定n(=2的k次幂)位选手，请输入k：\n");

scanf("%d",＆k);

/*8预设两位选手的比赛日程*/

a[1][1] =2;

a[2][1] =1;

m=1;

twoml=1;

while ( (1) ){

m++;

twoml+=twoml;

twom=twoml*2;/*为2^m位选手安排比赛日程*/

/*填日程表的左下角*/

for(i=twoml+1; (2) ;i++){

for(j=1; j<=twoml-1; j++){

a[i][j]=a[i-twoml][j]+twoml;

}

}

/*填日程表的右上角*/

a[1][twoml]= (3) ;/+填日程表右上角的第1列*/

for(i=2; i<=twoml; i++){

a[i][twoml]=a[i-1][twoml]+1;

}

/*填日程表右上角的其他列，参照前一列填当前列*/

for(j=twoml+1; j(twom;j++){

for(i=1; i a[i][j]= (4) ;

}

a[twoml][j]=a[1][j-1];

}

/*填日程表的右下角*/

for(j=twoml; j for(i=1;i<=twoml; i++){

a[ (5) [j]=i;

}

}

/*输出日程表*/

for(i=1; i<=twom; i++){

for(j=1;j printf("%4d",a[i][j]);

}

printf("\n");

}

printf("\n");

}

}

(1)

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

以下程序的输出结果是main(){ int k=4,m=1,p; p=func(k,m); printf("%d,",p); p=func(k,m); printf("%d\n",p);}func(int a,int b){ static int m=0,i=2; i+=m+1; m=i+a+b; return(m);} A．8,17 B．8,16 C．8,20 D．8,8