在一条笔直公路的一边有许多房子，现要安装消火栓，每个消火栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中，可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧

admin2019-10-08 60

问题在一条笔直公路的一边有许多房子，现要安装消火栓，每个消火栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中，可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消火栓，去掉被该消火栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为________(1)；对应的时间复杂度为________(2)。

假设公路起点A的坐标为0，消火栓的覆盖范围(半径)为20m，10栋房子的坐标为(10，20，30，35，60，80，160，210，260，300)，单位为m。根据上述算法，共需要安装________(3)个消火栓。以下关于该求解算法的叙述中，正确的是________(4)。
(2)

选项 A、O(lgn)
B、O(n)
C、(nlgn)
D、O(n²)

答案B

解析

转载请注明原文地址:https://kaotiyun.com/show/jGCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

用例图解释了活动者与用例之间的交互关系。根据系统设计说明，将系统的顶层用例图补充完整。图10-8为选课注册顺序图，请根据系统设计说明及图中信息，采用说明中的术语将选课注册顺序图补充完整。

阅读以下函数说明和Java代码，将应填入(n)处的字句写在对应栏内。【说明】以下程序实现数据的排序，将n个整数分别按照升序和降序进行排序，类SortInt_1实现升序排序，类SortInt_2实现降序排序。【Java代码】

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】应用Prim算法求解连通网络的最小生成树问题。请阅读程序后填空。constintMaxInt＝INTMAX；//INTMAX的值在＜limits．h＞

画出上述信息涉及的E—R图。将该E-R图转换为关系模型。

阅读下列函数说明、图和C代码，将应填入(n)处的字句写在对应栏内。【说明】假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]

A．HgSB．As2S2C．Fe2O3D．FeS2E．CaSO4•2H2O朱砂的主要成分是()。

领导者电话与信函沟通的艺术。

孩子们在看天上的白云时，经常会说看到了各种小动物。这体现的知觉特性是()

急性胰腺炎上腹痛最常见位置是

某产妇，28岁。因妊娠合并心脏病，心功能Ⅱ级，行剖宫产术。手术顺利，术后安返病房，子宫收缩好，血压正常。对该产妇的护理措施中正确的是

护理专业应届毕业生甲已经完成了国务院教育主管部门和卫生主管部门规定的全日制4年护理专业课程学习，本人拟申请护士执业注册。不属于申请护士执业注册的条件是

依据购房面积，可将客户划分为()。

在现行的《环境空气质量标准》中，SO2的年平均二级标准限值为()ms/m3。

对于逻辑表达式(bufc[i]＞223&&bufc[i]＜240&&i+2＜totalbytes)，需要______个测试用例才能完成条件组合覆盖。

在CD光盘上标记有“CD-RW”字样，“RW”标记表明该光盘是()。