请教:2011年11月软考软件设计师－下午试题(标准参考答案版)第4大题第1小题如何解答?【题目描述】试题四（共15分） 阅读下列说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。 采用回溯法来求解该问题： 首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{l，2，&helli

试题四（共15分）

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

设有n个货物要装入若干个容量为C的集装箱以便运输，这n个货物的体积分别为{S1，S2，．．．，Sn}，且有si≤C(1≤i≤ n)。为节省运输成本，用尽可能少的集装箱来装运这n个货物。

下面分别采用最先适宜策略和最优适宜策略来求解该问题。

最先适宜策略( firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。

最优适宜策略( bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。

【C代码】

下面是这两个算法的C语言核心代码。

(1)变量说明

n：货物数

C：集装箱容量

s：数组，长度为n，其中每个元素表示货物的体积，下标从0开始

b：数组，长度为n，b[i]表示第i+1个集装箱当前已经装入货物的体积，下标从0开始

i，j：循环变量

k：所需的集装箱数

min:当前所用的各集装箱装入了第i个货物后的最小剩余容量

m:当前所需要的集装箱数

temp：临时变量

(2)函数firstfit

int firstfit(){

inti,j；

k=0：

for(i=0；i<n；i++){

b[i]=0；

}

for（i=0；i<n；i++）{

(1)；

while(C-b[j]<s[i]){

j++;

}

(2)；

k=k>(j+1)?k：(j+1)；

}

returnk；

}

(3)函数bestfit

int bestfit() {

int i，j，min，m，temp;

k=0；

for（i=0；i<n；i++）{

b[i]=0；

}

For (i=0；i<n；i++）{

min=C；

m=k+l；

for(j=O;j< k+l；j++){

temp=C- b[j] - s[i];

if(temp>0&&temp< min){

(3) ；

m=j,

}

}

(4)；

k=k>(m+1)?k:(m+1)；

}

return k；

}

【问题1】（8分）

根据【说明】和【C代码】，填充C代码中的空(1)～(4)。

【问题2】（4分）

根据【说明】和【C代码】，该问题在最先适宜和最优适宜策略下分别采用了(5) 和(6)算法设计策略，时间复杂度分别为 (7) 和 (8)（用O符号表示）。

【问题3】（3分）

考虑实例n= 10，C= 10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况，这两种求解策略能否确保得到最优解？(11) （能或否）

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

【说明】

函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。

【函数】

void QuickSort( int A[ ],int s,int t)

{ int i=s,j=t+1,temp;

int x=A[s];

do{

do i ++ ;while (1);

do j -- ;while(A[j]＞x);

if(i＜j){temp=A[i];(2);(3);}

}while(i＜j);

A[a] =A[j];A[j] =x;

if(s＜i-1) (4);

if(j+1＜t) (5);

}

【题目描述】

● 现需要将数字2和7分别填入6个空格中的2个（每个空格只能填入一个数字），

已知第1格和第2格不能填7，第6格不能填2，则共有 （63） 种填法。

（63）

A. 12            

B. 16               

C. 17               

D. 20

【题目描述】

第 25 题

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

…

}

【题目描述】

● 设用2K×4位的存储器芯片组成16K×8位的存储器 （地址单元为0000H～3FFFH，每个芯片的地址空间连续），则地址单元0B1FH所在芯片的最小地址编号为（4） 。

（4）

A. 0000H   

B. 2800 H  

C. 2000 H   

D. 0800 H  

【题目描述】

第 8 题

●试题二

阅读下列函数说明和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")；

}

}

试题三（共 15 分）

阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。

阅读下列函数说明和C函数，回答问题1～2，将解答填入栏内。

[说明]

若矩阵Am×n中存在某个元素aij满足：aij…是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。下面程序的功能是输出A中所有鞍点，其中参数A使用二维数组表示，m和n分别是矩阵A的行列数。

[程序]

void saddle (int A[ ] [ ], int m, int n)

{ int i,j,min;

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

{ min: (1);

for (j=1; j＜n; j+ +)

if(A[i][j]＜min) (2);

for (j=0; j＜n; j+ +)

if ((3))

{ p=0;

while (p＜m&&(4))p+ +;

if (p ＞ = m)printf ("%d,%d,%d\n",i,j,min);

}

}

}

[问题1] 将函数代码中的(1)～(4)处补充完整

[问题2]在上述代码的执行过程中，若A为矩阵，则调用saddle(A，3，3)后输出是(5)。

阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。

[说明]

这是一个求解Josephus问题的函数。用整数序列1，2，3…，n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。Josephus问题描述，设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，…如此反复直到所有的人全部出局为止。

[C函数]

void Josephus(int A[],int n,s,m)

(int i,j,k,temp;

if(m==O){

printf("m=0是无效的参数!\n");

return;

}

for(i=0;i＜n;i++) A[i]=i+1; /*初始化，执行n次*/

i= (1) /*报名起始位置*/

for(k=n;k＞1;k-){

if((2)) i=0;

i=(3) /*寻找出局位置*/

if(i!=k-1){

tmp=A[i];

for(j=i;J＜k-1;j++) (4);

(5);

}

}

for(k=0;k＜n/2;k++){

tmp=A[k];A[k]=A[n-k+1];A[n-k+1]=tmp;

}

}

试题四（共15分）

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

【说明】

设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。

采用回溯法来求解该问题：

首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{l，2，…，m}，将解空间用树形结构表示。

接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(C11)是否超过上限(cc)，重量(W11)是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(C11+C21)是否超过上限(cc)，重量（W11+W21）是否比当前已知的解（最小重量）大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。

【C代码】

下面是该算法的C语言实现。

(1)变量说明

n：机器的部件数

m:供应商数

cc:价格上限

w[][]：二维数组，w[i][j]表示第j个供应商供应的第i个部件的重量

c[][]：二维数组，c[i][j]表示第j个供应商供应的第i个部件的价格

best1W:满足价格上限约束条件的最小机器重量

bestC:最小重量机器的价格

bestX[]．最优解，一维数组，bestX[i]表示第i个部件来自哪个供应商

cw:搜索过程中机器的重量

cp：搜索过程中机器的价格

x[]：搜索过程中产生的解，x[i]表示第i个部件来自哪个供应商

i：当前考虑的部件，从0到n-l

j：循环变量

(2)函数backtrack

Int n=3；

Int m=3；

int cc=4：

int w[3][3]={{1,2,3},{3,2,1}，{2,2,2}};

int c[3][3]={{1,2,3},{3,2,1},{2,2,2}};

int bestW=8；

int bestC=0；

int bestX[3]={0，0，0}；

int cw=0；

int cp=0；

int x[3]={0，0，0}；

int backtrack(int i){

int j=0；

int found=0；

if(i>n-1){/*得到问题解*/

bestW= cw;

bestC= cp;

for(j=0；j<n；j++){

(1)____；

}

return 1；

}

if(cp<=cc){/*有解*/

found=1；

}

for(j=0； (2)____;j++){

/*第i个部件从第j个供应商购买*/

(3) ；

cw=cw+w[i][j]；

cp=cp+c[i][i][j]；

if(cp<=cc && (4) {/*深度搜索，扩展当前结点*/

if(backtrack(i+1)){found=1;}

}

/*回溯*/

cw= cw -w[i][j]；

(5) ；

}

return found;

}

从下列的2道试题（试题五和试题六）中任选1道解答。

如果解答的试题数超过1道，则题号小的1道解答有效。

试题四（共15 分）

阅读下列说明和C代码，回答问题 1 至问题3，将解答写在答题纸的对应栏内。

【说明】

某应用中需要对100000 个整数元素进行排序，每个元素的取值在 0～5 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x的元素个数(记为m)，将 x放在输出元素序列的第m 个位置。对于元素值重复的情况，依次放入第 m-l、m-2、…个位置。例如，如果元素值小于等于4 的元素个数有 10 个，其中元素值等于 4 的元素个数有3个，则 4 应该在输出元素序列的第10 个位置、第 9 个位置和第8 个位置上。

算法具体的步骤为：

步骤1：统计每个元素值的个数。

步骤2：统计小于等于每个元素值的个数。

步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。

【C代码】

下面是该排序算法的C语言实现。

(1)常量和变量说明

R:常量，定义元素取值范围中的取值个数，如上述应用中 R值应取6i：循环变量

n：待排序元素个数

a：输入数组，长度为n

b：输出数组，长度为n

c：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。

(2)函数sort

1 void sort(int n,int a[ ]，intb[ ]){

2 int c[R]，i；

3 for (i=0；i< (1) ；i++){

4 c[i]=0；

5 }

6 for(i=0；i<n；i++）{

7 c[a[i]] = (2) ；

8 }

9 for(i=1；i<R；i++）{

10 c[i]= （3） ；

11 }

12 for(i=0；i<n；i++）{

13 b[c[a[i]]-1]= (4) ；

14 c[a[i]]=c[a[i] ]-1；

15 }

16 }

【问题1】（8 分）

根据说明和C代码，填充 C代码中的空缺(1)～(4)。

【问题2】（4 分）

根据C代码，函数的时间复杂度和空间复杂度分别为 (5) 和 (6) （用 O符号

表示）。

【问题3】（3 分）

根据以上C代码，分析该排序算法是否稳定。若稳定，请简要说明（不超过 100 字）；

若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。

从下列的2 道试题（试题五和试题六）中任选 1 道解答。

如果解答的试题数超过 道，则题号小的 道解答有效。

阅读以下说明和流程图，回答问题，并将解答填入对应栏内。

【说明】

求解约瑟夫环问题。算法分析：n个士兵围成一圈，给他们依次编号，班长指定从第w个士兵开始报数，报到第s个士兵出列，依次重复下去，直至所有士兵都出列。

【流程图】

【问题】

将流程图中的(1)～(5)处补充完整。

【题目描述】

●n个结点的二叉树，若用二叉链表作为存贮结构，则左、右子链域的总数为 (45) 个，其中 (46) 个用于链接子结点， (47) 个空闲着。

(45)

A．n

   B．n-1

   C．n+1

   D．n-2

(46) A．n-1

   B．n

   C．n+1

   D．n-2

(47) A．n+10

   B．n

   C．n+1

   D．n+9

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

【说明】

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

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

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

的类图如图5-1所示。

【c++代码】

}

●试题一

阅读下列说明和流程图，将应填入(n)处的语句写在答题纸的对应栏内。

【说明】

下列流程图用于从数组K中找出一切满足：K(I)+K(J)=M的元素对(K(I)，K(J))(1≤I≤J≤N)。假定数组K中的N个不同的整数已按从小到大的顺序排列，M是给定的常数。

【流程图】

此流程图1中，比较"K(I)+K(J)∶M"最少执行次数约为 (5) 。

图1

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

【说明】

某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1，m2，…，mn，每项食物mi的营养价值为vi，价格为pi其中i＝1，2，…，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。

1. 【问题1】

下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。

伪代码中的主要变量说明如下。

n：总的食物项数；

v：营养价值数组，下标从1到n，对应第1到第n项食物的营养价值；

p：价格数组，下标从1到n，对应第1到第n项食物的价格；

M：总价格标准，即套餐的价格不超过M；

x：解向量(数组)，下标从1到n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中；

nv：n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。

伪代码如下：

MaxNutrientValue(n，v，p，M，x)

1 for i＝0 to n

2 nv[i][0] ＝ 0

3 for j＝1 to M

4 nv[0][j]＝0

5 for i＝1 to n

6 for j＝1 to M

7 if j＜p[i] //若食物mi不能加入到套餐中

8 nv[i][j] ＝ nv[i-1][j]

9 else if (1)

10 nv[i][j]＝ nv[i-1][j]

11 else

12 nv[i][j]＝ nv[i-1][j-p[i]] + v[i]

13 j ＝ M

14 for i＝n downto 1

15 if (2)

16 x[i] ＝ 0

17 else

18 x[i] ＝ 1

19 (3)

20 return x and nv[n][M]

(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i] (2)nv[i][j]＝nv[i-1][j] (3)j＝j-p[i]