首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为
admin
2018-07-27
55
问题
(2021年下半年下午试题四)阅读下列说明和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
表示第n+i个集装箱当前已经装入货物的体积,下标从0开始
i,j:循环变量
k:所需的集装箱数
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量
m:当前所需的集装箱数
temp:临时变量
(2)函数firstfit
int firstfit(){
int i,j;
k=0;
for(i=0;i<n;i++){
b
=0;
}
for(i=0;i<n;i++){
_____(1);
while(C-b[j]<s
){
j++;
}
_______(2);
k=k>(j+1)?k:(j+1);
}
return k;
}
(3)函数bestfit
int bestfit(){
int i,j,min,m,temp;
k=0;
for(i=0;i<n;i++){
b
=0;
}
for(i=0;i<n;i++){
min=C;
m=k+1;
for(j=0;j<k+1;j++){
temp=C-b[j]-s
;
if(temp>0 &&temp<min){
______(3);
m=j;
}
}
______(4);
k=k>(j+1)?k:(j+1);
}
return k;
}
根据【说明】和【C代码】,该问题在最先适宜和最优适宜策略下分别采用了_____(5)和_____(6)算法设计策略,时间复杂度分别为_____(7)和盟(用O符号表示)。
选项
答案
(5)贪心 (6)贪心 (7)O(n
2
) (8)O(n
2
)
解析
贪心算法在解决最优化问题上是仅根据当前已有的信息做出选择,即不是从整体最优考虑,它所做出的选择只是力求局部最优。最先适宜策略和最优适宜策略均采用了该算法设计策略。
对于时间复杂度,应根据程序中循环的层数及每层循环的次数来进行计算。可以很容易地判断,这两种算法的时间复杂度均为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/l7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请说出图9-1的拓扑结构名称与特点。当增加了[问题3]中的设备后(此设备设置正确,且PC3与PC2是连通的,PCI与PC3也是连通的,经测试PCI与PC2物理连接正常),但PCIPing不通PC2。请问是什么原因?
从图7-1中可以看出采用什么拓扑结构与设计方法?为了进一步简化系统,有人建议把“电脑模块”与“电话模块”合成一个模块,其传输介质共用,这可以实现吗?
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]现在,家居装修布线是一个大且细致的工程项目,除了要布设普通电源线、有线电视电缆和电话线、音响线、视频线等,越来越多的电脑爱好者家中的网络布线则是少不了的。如果不是
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1~3。虚拟局域网(VirtualLAN)是与地理位置无关的局域网的一个广播域,由一个工作站发送的广播信息帧只能发送到具有相同虚拟网号的其他站点,可以形象地认为,VLAN是在物理局域
阅读以下关于RIP动态路由配置的技术说明,结合网络拓扑图回答问题1至问题3。[说明]某大学城局域网的网络拓扑结构如图7-18所示,图中路由器R1、R2,R3均运行基于距离矢量算法的RIP路由协议,并且图中给出了路由器R1、R2、R3各端口的IP地
阅读以下关于网络应用系统可靠性分析方面的技术说明,根据要求回答问题1至问题4。【说明】可靠性是一个网络应用系统能正常工作的能力,一般用平均故障间隔时间(MTBF)来度量。某网络应用软件研发公司正在开发一个嵌入式实时应用软件——宽带路由器的NanO
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如用户人数达到1000,为了保证100个用户同时正常下载,请问在图6-4中怎么
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如要封闭某用户的账号,请问在图6-4中怎么设置?
随机试题
关于摊铺导排层、收集渠码砌,说法错误的是()。
胁痛辨证除有虚实之分,还要辨
患儿,女,6岁3个月。6天前无明显诱因出现高热,体温最高达39.2℃,口干舌燥,微恶风,口渴喜饮,无汗,微咳,目赤头痛,球结膜充血,口咽潮红,双侧扁桃体Ⅱ度肿大,面部、躯干部散在分布无痛皮疹,压之褪色,颈后淋巴结肿大,活动度好,有触痛,舌边尖红,苔薄黄
中药炮制学专门研究
国内引起新生儿溶血病最常见的原因是()。
根据《仲裁法》的规定,涉外仲裁委员会作出的发生法律效力的裁决,当事人请求执行的,如果被执行人或者其财产不在中华人民共和国领域内,应当由下列哪一主体向有管辖权的外国法院申请承认和执行:()
会计人员职业道德表现好与差,()是最直接的受益者或受害者。
甲公司2×16年3月份A商品有关收、发、存情况如下:(1)3月1日结存300件,单位成本为2万元。(2)3月8日购入200件,单位成本为2.2万元。(3)3月10日发出400件。(4)3月20日购入300件,单位成本
苏霍姆林斯基教育思想的核心内容是()
WhichofthefollowingsentencesisINCORRECT?
最新回复
(
0
)