信管网每日一练
软件设计师 - 每日一练 导航

软件设计师案例分析每日一练试题(2022/9/26)

2022年09月27日来源:信管网 作者:cnitpm

软件设计师案例分析当天每日一练试题地址:www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总:www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题(2022/9/26)在线测试:www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2022/9/26

点击查看:更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容(2022/9/26)

[试题4]

阅读下列说明和C代码,回答下列问题。

[说明]

设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,...,sn},且有s1≤c(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装运这n个货物。

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

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

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

[C代码]

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

11变量说明

n:货物数

C:集装箱容量

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

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

i,j:循环变量

k:所需的集装箱数

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

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

temp:临时变量

12函数firstfit

int firstfit13 {

int i, j;

k=0;

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

b[i]=0;

}

for i=0; i<n;i++) {

______;

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

j++;

}

______;

k=k>(j+1)?k: (j+1);

}

return k;

}

14函数bestfit

int bestfit13 {

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+1;

for (j=0; j<k+1;j++) {

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

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

______;

m=j;

}

}

______;

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

}

return k;

}

[问题1]

根据[说明]和[C代码],填充C代码中的空缺处。

[问题2]

根据[说明]和[C代码],该问题在最先适宜和最优适宜策略下分别采用了______和______算法设计策略,时间复杂度分别为______和______(用O符号表示)。

[问题3]

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

信管网试题答案与解析:www.cnitpm.com/st/2485620390.html

信管网考友试题答案分享:

信管网试题答案与解析:www.cnitpm.com/st/2485620390.html

温馨提示:因考试政策、内容不断变化与调整,信管网提供的以上信息仅供参考,如有异议,请考生以权威部门公布的内容为准!

分享至:

信管网 - 信息系统项目管理专业网站

下载APP-在线学习

培训课程

0元畅享

考试题库

免费资料

客服咨询