第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题：
下面程序的运行结果是【17】。
#define N 10
#define s（x）x*x
#define f（x）（x*x）
main（）
{ int i1,i2;
i1=1000/s（N）; i2=1000/f（N）;
printf（"%d %d＼n",i1,i2）;
}
第3题：
A.[(A.s2S3)m•nHS]•nH
B.[(A.s2S3)m•nH]•nHS—n-++n+—
C.[(A.s2S3)nHS•(n—x)Hm•+—+x-—]•xH+x+
D.[(A.s2S3)•nH•(n—x)HS]•xmHS—
第4题：
以下程序通过函数sunFun求
。这里f(x)=x2＋1
main( )
{ printf("The sum=%d\n",SunFun(10)); }
SunFun(int n)
{ int x,s=0;
for(x=0;x＜=n;x++) s+=F（【 】）;
return s;
}
F( int x)
{ return 【 】);}
第5题：
下列程序的输出结果是______。
long fun5(int n)
( long s;
if((n==l)‖(n==2))
s=2;
else
s=n+fun5(n-1);
return(s);
}
main()
{ long x;
x=fun5(4);
printf(%1d\n",x);
第6题：
以下程序的输出结果是 #include＜stdio.h＞ in[fun(int n，int *s) {int n，f2； if(n==0‖n==1) *s=1； else {fun(n-1，&f1)； fun(n-2，&f2)； *s=f1+f2； }} void main() { int x； fun(6，&x)； pfintf("\n%d"，x)；}
A．7
B．13
C．9
D．10
第7题：
阅读下列程序说明和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
第8题：
●试题四
阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【程序4．1说明】
"背包问题"的基本描述是：有一个背包，能盛放的物品总重量为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(″N0!＼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=l；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；
}
●试题四
【答案】（1）knap（s-w［n］，n-1）（2）knap（s，n-1）（3）top>=1 && !k 或 top>0 && k == 0
（4）x.s - w ［x.n--］（5）stack［++top］（6）rep = 0
【解析】试题提供了两种解决问题的方法，程序5.1是用递归的方法来解决背包问题，程序5.2使用非递归的方法来解决背包问题。每次选择一个物品放入背包，那么剩余的物品和背包剩余的重量，又构成一个"背包问题"。程序从数组下标最大的物品开始考查，因此（1）处应该填"knap（s-w［n］,n-1）"，即将数组中第N个物品放入背包，如果它能够放入到背包中，则该物品是构成解的元素之一；否则，将该物品从背包中取出，该物品不构成解的元素，在以后的考查中，它可以被排除，因此（2）处应该填"knap（s,n-1）"。在改程序中用栈来保存已经考查过的物品，结构KNAPTP表示经过考查的物品，s表示考查过该物品后背包所能够盛放的物品的重量；n表示该物品在数组W中的下标；job表示物品当前的状态：当job等于1，表示物品n可以放入背包；job等于2表示物品n不能被放入到背包，那么在以后的选取中将不再考虑该物品。初始时job等于0，表示背包中没有任何放入任何物品。K为有解的标志。Rep为一个标志变量，rep等于0，表示结束当前的动作；rep等于1表示继续进行当前的动作。当栈顶物品不能放入背包时，将rep设置为0，表示下一步不从数组w中取物品。其初值为1。开始时，将数组中下标最大的物品放入栈中，然后开始考查该物品。该物品满足放入背包的条件，第（4）（5）空将完成将物品放入背包的操作，因此（4）空填"x.s-w［x.n--］"，修改背包的可容纳物品的重量；（5）处填"stack［++top］"，将下一个要考查的物品放入栈中。若该物品不满足放入背包的条件，则将该物品从背包中取出，因此将rep置为0，结束循环while（!k&&rep）。将物品从背包中取出，即释放该物品在背包中所占的重量，并标记为不能放入到背包（job=2），再将其放入到栈中；然后继续考查数组w中的下一个物品，因此需要结束循环while（top>=1&&rep），将rep置为0，所以第（6）处应该填"rep=0"。在第三处要求给出循环结束的条件，即可以继续选取物品的条件，在此处填"top>=1&&!k"。
第9题：
下面程序和运行运行结果是【 】。
define N 10
define s (x) x * x
define f(x) (x * x)
main( )
{ iht i1,i2;
i1 = 1000/s(N); i2 = 1000/f(N);
printf("%d %d\n",i1,i2);
}
第10题：
以下程序的输出结果是( )。 #include＜stdio.h＞ int fun(int n，int *s) { int f1，f2； if(n==0||n==1) *s=1； else { fun(n-1，&f1)； fun(n-2，&f2)； *s=f1+f2； } } void main() { int x； fun(6，&x)； printf("\n％d" ，x)；}
A．7
B．13
C．9
D．10