2010年软件水平考试软件设计师模拟试题(1)

　　●试题四

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

　　【程序4.1说明】

　　"背包问题"的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，...，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。

　　如下程序均能求得"背包问题"的一组解，其中程序4.1是"背包问题"的递归解法，而程序4.2是"背包问题"的非递归解法。

　　【程序4.1】

　　#include

　　#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

　　#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;

　　}