首页
登录
从业资格
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
考试题库
2022-08-02
43
问题
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为( )。
假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是(请作答此空)。A.肯定可以求得问题的一个最优解B.可以求得问题的所有最优解C.对有些实例,可能得不到最优解D.只能得到近似最优解
选项
A.肯定可以求得问题的一个最优解
B.可以求得问题的所有最优解
C.对有些实例,可能得不到最优解
D.只能得到近似最优解
答案
C
解析
快速排序由C.A.R.Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。整个算法的时间复杂度是O(nlogn)。场地上可以安排活动1、8、11为一个场地;活动2、6、9一个场地;活动3为一个场地;活动4、7为一个场地;活动5、10为一个场地,共5个场地。
转载请注明原文地址:https://tihaiku.com/congyezige/2425197.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
正常成人颅内压的范围是A.20~30mmHO B.50~100mmHO C.
针对组织内部的具体问题,在较小范围内和较短时间内实施的计划属于A.指令性计划
用于表示较短时间和小范围内医院感染的暴发或流行情况的指标是A.医院感染患病率B.
正常成人颅内压的范围是A.20~30mmHO B.50~100mmHO C.
颅内压的正常范围是A:0.4~0.6kPa(40~60mmH2O) B:0.7
若分页系统的地址结构如下图所示。 该系统页的大小为()字节,页号的取值范围
话音信道的频率范围为300~3400Hz,如果采用PCM编码技术,则采样频率必须
无线城域网标准IEEE802.16规定的有效覆盖范围最大可达()。A.2km
扩展访问控制列表的编号范围是()。如果允许来自子网172.16.0.0/16
数字话音的采样频率定义为8kHz,这是因为()。A.话音信号定义的频率范围最
随机试题
[originaltext]Whatdoyouthinkofourmanager?[/originaltext][originaltext]Ho
APosterAboutanAcademicReportForthispart,youareallowed30minutes
Geneticallymodified(GM)foodstuffsareheretostay.That’snottosaythat
Marysaidtome,"HadIseenyourbag,I______ittoyou."A、willreturnB、must
IfU.S.softwarecompaniesdon’tpaymoreattentiontoquality,theycoul
急性下壁心肌梗死的特征性心电图改变出现于A.V、V、V导联 B.V、V、V导联
A.滑 B.促 C.弦 D.涩 E.数青壮年的常脉多见
患者便血紫黯,甚则黑色,腹部隐痛,喜热饮,面色不华,神倦懒言,便溏,舌质淡,脉细
在分立过程中,不存在股权和控制权向母公司和其股东之外第三者转移情况的分立形式是(
男性,67岁,慢性咳嗽,咳少量白痰,活动后气短3年,近2月气短加重,痰量较多,为
最新回复
(
0
)