第1题:
阅读下列程序说明和C++代码,将应填入(n)处。
【说明】
“背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1;w2,……,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品的重量之和等于S。
如下程序均能求得“背包问题”的一组解,其中程序4.1是“背包问题”的递归解法,而程序4.2是“背包问题”的非递归解法。
【程序4.1】
include<stdio.h>
define N 7
define S 15
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s,int n)
{ if(s==0)return 1;
if(s<0||(s>0& &n<1))return 0;
if((1)))|
printf("%4d",w[n]);return 1;
} return (2);
}
main(){
if(knap(S,N))printf("OK!\n");
else printf("NO!\n");
}
【程序4.2】
include<stdio.h>
define N 7
define S 15
typedef struct{
int s;
int n:
int job;
} KNAPTP;
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s,int n);
main(){
if(knap(S,N))printf("OK!\n");
else printf("NO!\n");}
int knap(int s,int n)
{ KNAPTP stack[100],x;
int top,k,rep;
x.s=s;x.n=n;
x.job=0;
top=|;Stack[top]=x;
k=0;
while((3)){
x=Stack[top];
rep=1;
while(!k && rep){
if(x.s==0)k=1;/*已求得一组解*/
else if(x.s<0||x.n <=0)rep=0;
else{x.s=(4);x.job=1;
(5)=x;
}
}
if(!k){
rep=1;
while(top>=1&&rep){
x=stack[top--];
if(x.job==1){
x.s+=W[x.n+1];
x.job=2;
Stack[++top]=x;
(6);
}
}
}
}
if(k){/*输出一组解*/
while(top>=1){
x=staCk[top--];
if(x.job==1)
printf("%d\t",w[x.n+1]);
}
}
return k;
}
第2题:
设R、N分别表示实数、整数和自然数集,下面定义函数f1、f2、f3: f1:R→R,f(x)=2x f2:N→N×N,f(n)=<n,n+1> f3:N→N,f(x)=x mod 3,x除以3的余数 则下面说法正确的是( )。
A.f1和f2是单射但不是满射函数
B.f1和f3都是满射函数
C.f2是双射函数
D.以上说法全都是错误的
第3题:
第4题:
阅读下列程序说明和C代码,将应填入(n)处的字句写在对应栏内。
【说明】
“背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1,w2,…,wn。希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品的重量之和等于S。
如下程序均能求得“背包问题”的一组解,其中程序1是“背包问题”的递归解法,而程序2是“背包问题”的非递归解法。
【程序1】
include<stdio.h>
define N 7
define S 15
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s, int n)
{
if(s==0) return 1;
if(s<0 || (s>0 && n<1))return 0;
if((1)){/*考虑物品n被选择的情况*/
printf("%4d",w[n]);
return 1;
}
return (2);/*考虑不选择物品n的情况*/
}
main()
{
if(knap(S,N))printf("OK!\n");
else printf("N0!\n");
}
【程序2】
include<stdio.h>
define N 7
define S 15
typedef struct{
int s;
int n;
int job;
}KNAPTP;
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s, int n);
main()
{
if(knap(S,N)) printf("0K!\n");
else printf("N0!\n");
}
int knap(int s, int n)
{
KNAPTP stack[100],x;
int top, k, rep;
x.s=s;x.n=n;
x.job=0;
top=1; stack[top]=x;
k=0;
while( (3) ){
x=stack[top];
rep=1;
while(!k && rep){
if(x.s==0) k=1;/*已求得一组解*/
else if(x.s<0 || x.n<=0) rep=0;
else{
x.s=(4);
x.job=1;
(5)=x;
}
}/*while*/
if(!k){
rep=1;
while(top>=1 && rep){
x=stack[top--];
if(x.job==1){
x.s +=w[x.n+1];
x.job=2;
stack[++top]=x;
(6);
}/*if*/
}/*while*/
}/*if*/
/*while*/
if(k){&nbs
第5题:
下面这个程序段的时间复杂度是( )。 for (i=1; i<n; i++) { y=y+3; for (j=0;j<=(2*n);j++) x++; }
A.O(log2n)
B.O(n)
C.O(nlog2n)
D.O(n2)
第6题:
下面是一段Pascal程序: for h:=1 tO n-1 dO begin x:=A[h+1]; k:=h; while (k>=1) and (A[k]>x) do begin A[k+1):=A[k]; k:=k-1 end; A[k+1]:=x end; 假设在程序开始执行时,数组A[1..n)是一组随机整数。下列答案中,哪一个最好的描述了最差情况下的程序执行时间(运行时间阶数)?( )
A.0(nlog2n)
B.O(n)
C.0(log2n)
D.O(n2)
第7题:
( 6 ) 描述 “ X 是小于 100 的非负整数 ” 的 Visual Basic 表达式是 【 6 】 。
第8题:
描述 \"X 是小于 100 的非负整数 \" 的 Visual Basic 表达式是______。
第9题:
下面是一段Pascal程序: for h:=1 to n-1 do begin x:=A[h+1]; k:=h; while(k>=1)and(A[k]>x)do begin A[k+1]:=A[k]; k:=k-1 end; A[k+1]:=x end; 假设在程序开始执行时,数组A[1…n)是一组随机整数。下列答案中,最好地描述了最差情况下的程序执行时间(运行时间阶数)的是
A.O(n log2n)
B.O(n)
C.O(log2n)
D.O(n2)
第10题:
若x是int型变量,且有下面的程序片段: for(x=3;x<6;x++)printf(x%2)?("* *%d"):(”# #%d\n”),x); 上面程序片段的输出结果是 ( )
A.* * 3 # # 4 * * 5
B.# # 3 * * 4 # # 5
C.# # 3 * * 4 # # 5
D.* * 3 # # 4 * * 5