首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1~问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为{S1,S2,…,Sn},且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装运这n个货
阅读下列说明和C代码,回答问题1~问题3,将解答写在答题纸的对应栏内。 【说明】 设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为{S1,S2,…,Sn},且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装运这n个货
admin
2017-08-31
71
问题
阅读下列说明和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+1个集装箱当前已经装入货物的体积,下标从0。
i,j:循环变量。
k:所需的集装箱数。
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量。
m:当前所需要的集装箱数。
temp:临时变量。
(2)函数firstfit。
int firstfit(){
inti,j;
k=0: ;
for(i=0;i
b
=0;
}
for(i=0;i
(1) ,
while(C—b[j]
){
j++;
}
(2);
k=k>(j+1)?k:(j+1);
}
returnk
}
(3)函数bestfit。
int bestfit(){
int i , j f min t m t temp;
k=0;
for(i=0;i
b
=0;
}
for(i=0;i
min=C;
m=k+1;
for(j=0;j
temp=C—b[j]一S
;
if(temp>O&&temp
(3) ;
m=j;
}
}
(4) ;
k=k>(m+1)?k:(m+1);
}
return k:
}
根据【说明】和【C代码】,该问题在最先适宜和最优适宜策略下分别采用了(5)和 (6)算法设计策略,时间复杂度分别为(7)和 (8) (用0符号表示)。
选项
答案
(5)贪心。 (6)贪心。 (7)O(n
2
)。 (8)O(n
2
)。
解析
转载请注明原文地址:https://kaotiyun.com/show/cODZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整IEEE802.11定义了无线局域网(WLAN)的两种工作模式,根据图4-8所示的网络拓朴结构可判断出该WLAN的工作模式是(4)。当前WLAN中主要使
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
SSL是一个协议独立的加密方案,在网络信息分组的应用层和传输层之间提供了安全的通道。SSL主要包括SSL修改密文协议、SSL握手协议、SSL告警协议、SSL记录协议等,其协议栈见图7-16。请根据SSL协议栈结构,将(1)~(4)处空缺的协议名称填写完整。
PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(1)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(2)位的报文摘要,发送方用自己的RSA私钥对(3)进行加密,附加在邮件中进行传送。公钥只用来加密(4),文件是用
上述配置中是否有问题?请指出并说明理由。解释配置中画线部分内容含义?
依据给出的可选设备进行选型,将(1)~(5)处空缺的设备名称填写在相应位置将(6)~(8)处空缺的介质填写在相应位置(所给介质可重复选择)。
ADSL技术可以充分利用现有铜线网络,只要在用户线路两端加装ADSL设备即可为用户提供服务。请从以下术语选择适当的编号,将图5-9所示的拓扑结构中(1)~(4)空缺处的名称填写完整。【供选择的答案】A.程控交换机B.二层交换机
阅读以下交换机Switch01的部分配置信息,结合图2-8所示的网络拓扑图将(1)~(8)空缺处的内容(命令或解释)填写完整。Switch>enable(进入特权模式)S
随机试题
患者男,60岁。因“声音嘶哑半个月余伴咽痛”就诊,查体发现颈部可及2cm×4cm大小肿大淋巴结,颈部MRI提示:①右侧梨状窝新生物,侵及右侧声带,环状软骨部分受侵;②双侧颈部多个肿大淋巴结,最大径<6cm。下列检查对进一步确诊意义最大的是
艾叶的功效有
患者,女,41岁,因进食:不洁食物后发生腹泻,伴有恶心、呕吐及下腹痛,大便每日6~8次,为糊状或稀水状,伴有黏液。血常规检查提示:白细胞计数、中性粒细胞百分比明显升高。粪常规:白细胞8~10/HP,红细胞3~5/HP。诊断:急性腹泻。医嘱:复方地芬诺酯片,
甲在网络散布乙的不实信息,对乙进行诽谤,乙与之理论不成,将甲打成重伤。乙向公安机关提出控告。甲向法院提起刑事自诉并附带民事诉讼,法院判决乙有期徒刑1年,附带民事赔偿3万元。下列说法正确的是?
灰土地基施工过程中应检查()。
当各种粒料的颗粒级配连续、相互嵌挤密实的矿料,与沥青结合料拌合,压实后剩余空隙率小于( )的沥青混合料称为密级配沥青混凝土混合料。
阅读下面短文,回答下列五道题。人类正面临着全球变暖的挑战,联合国的一份报告向我们描述了气候变化产生的灾难性后果:森林消失和沙漠扩大;将使非洲成为受影响最广的地区;热带流行的疟疾和寄生虫病将向北蔓延,使欧洲出现流行病,地中海地区由于严重缺水会半沙漠化
设二次型f(x1,x2)=ax12+bx22+4x1x2经过正交变换x=Qy化为g(y1,y2)=2y12+2y1y2二次型f与g的矩阵分别为A与B求a,b的值
Earthquakescanbedevastating【1】disasters.TheinfamousSanFranciscoearthquakeof1906causedover$200millionworthofdam
A、Theybelievepubsareonlysuitableformen.B、Theystronglyopposewomen’svisittopubs.C、Theyconsiderthepubanunrespec
最新回复
(
0
)