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;

　　}