指出开标工作的不妥之处，并说明理由。

阅读下列程序说明和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

阅读下列程序说明和C++程序，把应填入其中(n)处的字句，写在对应栏内。

【说明】

阅读下面几段C++程序回答相应问题。

比较下面两段程序的优缺点。

①for (i=0; i＜N; i++ )

{

if (condition)

//DoSomething

…

else

//DoOtherthing

…

}

②if (condition) {

for (i =0; i＜N; i++ )

//DoSomething

}else {

for (i=0; i ＜N; i++ )

//DoOtherthing

…

}

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

【说明】

某灯具厂商欲生产一个灯具遥控器，该遥控器具有7个可编程的插槽，每个插槽都

有开关按钮，对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌

灯具的开关，现采用Command（命令）模式实现该遥控器的软件部分。Command模式

的类图如图5-1所示。

【c++代码】

}

（） 阅读下列说明和C++代码，将应填入空(n)处的字句写在答题纸的对应栏内。【说明】 某中学开展中外中学生野外生存夏令营活动，由于中外学生的语言障碍，随队为外籍学员配置一名翻译。以下代码采用适配器（Adapter）模式模拟翻译适配器。其类图如下：

阅读下列函数说明和C代码，填入(n)处字句，并回答相应问题。

[说明]

背包问题就是有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，而且选中物品的价值之和为最大。

背包问题是一个典型的NP完全难题。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。

常用的背包问题求解方法很多，但本题中采用了一种新的算法来求解背包问题。该算法思想为：首先要对物品进行价重比排序，然后按价重比从大到小依次装进包裹。这种方法并不能找到最佳的方案，因为有某些特殊情况存在，但只要把包中重量最大的物品取出，继续装入，直到达到limitweight，这时的物品就是limit weight的最大价值。这种算法不需要逐个进行试探，所以在数据非常大时，执行效率主要由排序的时间复杂度决定。该算法的流程图为图11-4。

仔细阅读程序说明和C程序流程图及源码，回答问题1和问题2。

[流程图11-4]

[程序说明]

struct Thing：物品结构

typedef struct Bag：背包结构类型

input ()：将物品按序号依次存入数组函数

inbag ()：物品按物价比入包函数

init ()：初始化函数

sort ()：对物品按价格重量比排序函数

outbag ()：取出包中weiht最大的物品函数

print ()：最佳方案输出函数

[C程序]

define N 255

struct Thing {

double weight;

double value;

double dens;

}thing[N];

typedef stmct Bag {

Thing thing [N];

double weighttmp;

double sumvalue;

}bag,best;

inbag ()

{

do{

bag.thing[i]=thing[i]

(1)

(2)

i++;

}while ((3) )

}

init ()

{

for (inti=0; i＜N; i++)

{

input (thing[i].weight, thing [i].value)

thing [i].dens=thing[i].value/thing [i].weight;

};

}

main ()

{

init ();

sort ();

inbag ();

do {

best=bag; //把包中物品放入暂存数组

outbag (); //取出包中weight最大的物品

(4)

}while ((5))

print (best)； //输出temp因为是最佳方案

}

根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。

阅读下列说明，回答问题1至问题2，将解答填入答题纸的对应栏内。

【说明】

0—1背包问题可以描述为：有n个物品，对i=l，2，…，n，第i个物品价值为vi，重量为wi(vi和wi为非负数)，背包容量为w(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，xi∈{O，1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。

用回溯法求解此0—1背包问题，请填充下面伪代码中(1)～(4)处空缺。

回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOuND(v，w，k，W)函数，其中v、w、k和w分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。下面给出0—1背包问题的回溯算法伪代码。

函数参数说明如下：w：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。

变量说明如下：

cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。

BKNAP(W，n，w，v，fw，fp，X)

1 cw←cp0

2 (1)

3 fp←l

4 while true

5 while k≤n and cw+w[k]≤w d。

6 (2)

7 cp←cp+v[k]

8 Y[k]←l

9 k←k+1

10 if k>n then

11 if fp<cp then

12 fp←cp

13 fw←cw

14 k←n

15 X←Y

16 else Y (k)←O

17 while BOUND(cp，cw，k，W) ≤fp do

18 while k≠O and Y(k)≠l d0

19 (3)

20 if k=0 then return

2l Y[k]←0

22 cw←cw-w[k]

23 cp←cp-v[k]

24 (4)

●试题二

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

【说明】

该程序运行后，输出下面的数字金字塔

【程序】

include<stdio．h>

main ()

{char max，next；

int i；

for(max=′1′；max<=′9′；max＋＋)

{for(i=1；i<=20- (1) ；＋＋i)

printf(" ")；

for(next= (2) ；next<= (3) ；next＋＋)

printf("％c"，next)；

for(next= (4) ；next>= (5) ；next--)

printf("％c"，next)；

printf("＼n")；

}

}

某数据文件students.txt的内容为100名学生的学号和成绩，下面的程序将文件中的数据全部读入对象数组，按分数从高到低进行排序后选出排名前30%的学生。【C++代码】

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

【说明】

某灯具厂商欲生产一个灯具遥控器，该遥控器具有7个可编程的插槽，每个插槽都

有开关按钮，对应着一个不同的灯。利用该遥控器能够统一控制房间中该厂商所有品牌

灯具的开关，现采用Command（命令）模式实现该遥控器的软件部分。command模式

的类图如图6-1所示。

【Java代码】

}