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

admin2019-10-08 38

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

阅读以下说明和C程序，填入(n)外。[说明]以下C程序实现了将字符串转化为浮点数的功能。例如字符串“1234567”转化为浮点数1234567；字符串“100.02035”转化为浮点数100.02035；字符串“-100.02035”转化为

用例图解释了活动者与用例之间的交互关系。根据系统设计说明，将系统的顶层用例图补充完整。UML设计中交互图通常可以分为哪两类图?绘制交互图对系统的设计有什么作用?

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

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

根据题意，给出类“传阅记录”的主要属性。同一种期刊分不同的期，所以有多本同一种期刊。“传阅名单”只需每一种期刊一份，还是应该每本期刊一份?为什么?

写出SQL语句，将记录(ID，Category==pot，DelSize=1.5)插入Delivery表中。写出如下SQL实现语句。(1)把对表Zone的INSERT权限授予用户Smith，并允许它再将此权限授予他人。(2)收回已经授予Tom的对表

阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的语句填写完整。[说明]函数intToplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点的A

阅读以下函数说明和Java代码，将应填入(n)处的字句写在对应栏内。[说明]很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下，Singleton模式有可能出现问题，需要进行

某淋浴室内共有3个淋浴器。应设地漏的直径为()mm。

关于混凝土表层损坏的原因，下列说法错误的是()。

(　　)是收入、费用、利润要素的特点。

在遭遇自然灾害的袭击时，导游员务必做到()。

公安机关在办理刑事案件中，就被害人及其法定代理人的诉讼权利和犯罪嫌疑人的诉讼权利要平等地适用法律。()

2022年1月1日，《区域全面经济伙伴关系协定》(RCEP)生效实施，全球最大自由贸易区正式启航。RCEP现有()个成员国，从人口数量、经济体量、贸易总额三方面看，均占全球总量的约()。

以下问题中，主要围绕19世纪90年代资产阶级维新派与封建守旧派论战展开的有()

设f(x)连续，且F(x)=∫0x(x-2t)f(t)dt．证明：若f(x)单调不增，则F(x)单调不减．

8位二进制原码表示整数的范围是

"BiologyClass"Whatistheimpacthypothesis?

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

软考中级

阅读以下说明和C程序，填入(n)外。[说明]以下C程序实现了将字符串转化为浮点数的功能。例如字符串“1234567”转化为浮点数1234567；字符串“100.02035”转化为浮点数100.02035；字符串“-100.02035”转化为

用例图解释了活动者与用例之间的交互关系。根据系统设计说明，将系统的顶层用例图补充完整。UML设计中交互图通常可以分为哪两类图?绘制交互图对系统的设计有什么作用?

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

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

根据题意，给出类“传阅记录”的主要属性。同一种期刊分不同的期，所以有多本同一种期刊。“传阅名单”只需每一种期刊一份，还是应该每本期刊一份?为什么?

写出SQL语句，将记录(ID，Category==pot，DelSize=1.5)插入Delivery表中。写出如下SQL实现语句。(1)把对表Zone的INSERT权限授予用户Smith，并允许它再将此权限授予他人。(2)收回已经授予Tom的对表

阅读以下函数说明和C代码，将C程序中(1)～(5)空缺处的语句填写完整。[说明]函数intToplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点的A

阅读以下函数说明和Java代码，将应填入(n)处的字句写在对应栏内。[说明]很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下，Singleton模式有可能出现问题，需要进行

某淋浴室内共有3个淋浴器。应设地漏的直径为()mm。

关于混凝土表层损坏的原因，下列说法错误的是()。

( )是收入、费用、利润要素的特点。

在遭遇自然灾害的袭击时，导游员务必做到()。

公安机关在办理刑事案件中，就被害人及其法定代理人的诉讼权利和犯罪嫌疑人的诉讼权利要平等地适用法律。()

2022年1月1日，《区域全面经济伙伴关系协定》(RCEP)生效实施，全球最大自由贸易区正式启航。RCEP现有()个成员国，从人口数量、经济体量、贸易总额三方面看，均占全球总量的约()。

以下问题中，主要围绕19世纪90年代资产阶级维新派与封建守旧派论战展开的有()

设f(x)连续，且F(x)=∫0x(x-2t)f(t)dt．证明：若f(x)单调不增，则F(x)单调不减．

8位二进制原码表示整数的范围是

"BiologyClass"Whatistheimpacthypothesis?

(　　)是收入、费用、利润要素的特点。