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

admin2019-10-08 68

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

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

选项 A、分治
B、动态规划
C、贪心
D、回溯

答案A

解析

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

阅读以下说明和流程图，回答问题1至问题3。【说明】某城市电信局受理了许多用户申请在指定电话上开设长话业务。长话包括国内长途和国际长途。电信局保存了长话用户档案和长话业务档案。

阅读以下说明和VisualBasic代码，填入(n)处。[说明]以下VisualBasic代码实现了系统登录时对用户进行合法性检查。界面如图9-6所示。阅读下面代码，将(n)处代码补充完整。[代码7-1]BeginVB.

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示：结点源代码行Areada,b,cB

阅读以下说明，回答问题1和问题2，将解答写在对应栏内。【说明】一个野生动物园，有如下动物：老虎、豹、狼、丹顶鹤、鹦鹉、天鹅、金鱼、热带鱼、鳄鱼等等。

如果将上述应用的数据库设计成如下关系模式；RS(A#，A1，A2，A3，B#，B1，B2，D1)，请指出该关系模式的候选键。假设上述关系模式RS上存在函数依赖：A1→A3。上述关系模式RS最高满足第几范式(在1NF～BCNF之内)?为什么?

写出语句，将(ID=1，Category=pot，DelSize=1.5)的数据插入DELIVERY表中。(1)把对表ZONE的INSERT权限授予用户Smith，并允许他再将此权限授予其他人。(2)收回已经授予Tom的对FlowerInfo中属性C

男性，70岁，慢性肾衰竭，心悸2天，查心电图发现T波高尖，QT间期延长。根据上述表现应做何种检查

符合肺炎球菌肺炎表现的是符合肺炎支原体肺炎表现的是

建设工程物资供应计划的编制应(　　)，

施工方案的技术经济比较，不包括()。

某商品流通企业决定将经营战略的重点放在某个特定的目标市场上，为特定的地区、特定的购买群体提供特定的商品和服务。这个企业所采取的战略属于()。

行政许可由()行政机关在法定职权范围内行使。

连续犯指行为人基于同一的或者概括的犯罪故意，连续即断断续续地实施数个独立的犯罪行为，触犯同一罪名的犯罪。下列不属于连续犯特征的一项是：

胆管癌最主要的临床表现是

设随机变量X服从参数为1的指数分布，则随机变量Y=min(X，2)的分布函数()．

CAI表示为______。

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

软考中级

阅读以下说明和流程图，回答问题1至问题3。【说明】某城市电信局受理了许多用户申请在指定电话上开设长话业务。长话包括国内长途和国际长途。电信局保存了长话用户档案和长话业务档案。

阅读以下说明和VisualBasic代码，填入(n)处。[说明]以下VisualBasic代码实现了系统登录时对用户进行合法性检查。界面如图9-6所示。阅读下面代码，将(n)处代码补充完整。[代码7-1]BeginVB.

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示：结点源代码行Areada,b,cB

阅读以下说明，回答问题1和问题2，将解答写在对应栏内。【说明】一个野生动物园，有如下动物：老虎、豹、狼、丹顶鹤、鹦鹉、天鹅、金鱼、热带鱼、鳄鱼等等。

如果将上述应用的数据库设计成如下关系模式；RS(A#，A1，A2，A3，B#，B1，B2，D1)，请指出该关系模式的候选键。假设上述关系模式RS上存在函数依赖：A1→A3。上述关系模式RS最高满足第几范式(在1NF～BCNF之内)?为什么?

写出语句，将(ID=1，Category=pot，DelSize=1.5)的数据插入DELIVERY表中。(1)把对表ZONE的INSERT权限授予用户Smith，并允许他再将此权限授予其他人。(2)收回已经授予Tom的对FlowerInfo中属性C

男性，70岁，慢性肾衰竭，心悸2天，查心电图发现T波高尖，QT间期延长。根据上述表现应做何种检查

符合肺炎球菌肺炎表现的是符合肺炎支原体肺炎表现的是

建设工程物资供应计划的编制应( )，

施工方案的技术经济比较，不包括()。

某商品流通企业决定将经营战略的重点放在某个特定的目标市场上，为特定的地区、特定的购买群体提供特定的商品和服务。这个企业所采取的战略属于()。

行政许可由()行政机关在法定职权范围内行使。

连续犯指行为人基于同一的或者概括的犯罪故意，连续即断断续续地实施数个独立的犯罪行为，触犯同一罪名的犯罪。下列不属于连续犯特征的一项是：

胆管癌最主要的临床表现是

设随机变量X服从参数为1的指数分布，则随机变量Y=min(X，2)的分布函数()．

CAI表示为______。

建设工程物资供应计划的编制应(　　)，