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

admin2019-10-08 36

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

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句，请在空缺处填入正确的内容。SELECT(1)FROM(2)WHERE(3)

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

依据说明，完成下面的类图，要求第1层和第2层填写标识、主要属性和操作，第3层填写标识即可。UML规定类图中类之间的关系有关联、聚集、继承，请说明它们的含义和之间的区别。

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

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btreeB){btreestack[m0

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

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

简述热电偶的中间导体定律。

发行人应当针对实际情况在招股说明书首页作“重大事项提示”，提醒投资者给予特别关注。()

在进行个人件房贷款申请时，应提交的申请材料不包括()。

物业服务差异目标市场营销策略的优点是（）。

学生在问题解决过程中是受到一定因素影响的，教师应当怎样克服这些因素培养学生的问题解决能力?

某一类应用问题中，需要求正比例函数与反比例函数之和的极值。例如，正比例函数奴与反比例函数9/x之和用f(x)表示，即f(x)=4x+9/x(x＞0)，那么函数f(x)(63)。

下列关于WindowsServer2003系统下WWW服务器的描述中，错误的是()。

下面的程序执行后，文件test.t中内容是______。#inc1ude＜stdio.h＞voidfun(charfname,charst){FILE*myf;inti;

Obesity(肥胖)hasbecomeanepidemic.NotonlydoesObesityhavemore【C1】______healthconsequencesthansmoking,drinking,orpo

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

软考中级

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

试分析该关系模式中的函数依赖，并指出关系模式的候地选码。如下的SQL语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句，请在空缺处填入正确的内容。SELECT(1)FROM(2)WHERE(3)

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

依据说明，完成下面的类图，要求第1层和第2层填写标识、主要属性和操作，第3层填写标识即可。UML规定类图中类之间的关系有关联、聚集、继承，请说明它们的含义和之间的区别。

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

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btree*B){btree*stack[m0

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

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

简述热电偶的中间导体定律。

发行人应当针对实际情况在招股说明书首页作“重大事项提示”，提醒投资者给予特别关注。()

在进行个人件房贷款申请时，应提交的申请材料不包括()。

物业服务差异目标市场营销策略的优点是（）。

学生在问题解决过程中是受到一定因素影响的，教师应当怎样克服这些因素培养学生的问题解决能力?

某一类应用问题中，需要求正比例函数与反比例函数之和的极值。例如，正比例函数奴与反比例函数9/x之和用f(x)表示，即f(x)=4x+9/x(x＞0)，那么函数f(x)(63)。

下列关于WindowsServer2003系统下WWW服务器的描述中，错误的是()。

下面的程序执行后，文件test.t中内容是______。#inc1ude＜stdio.h＞voidfun(char*fname,char*st){FILE*myf;inti;

Obesity(肥胖)hasbecomeanepidemic.NotonlydoesObesityhavemore【C1】______healthconsequencesthansmoking,drinking,orpo

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btreeB){btreestack[m0

下面的程序执行后，文件test.t中内容是______。#inc1ude＜stdio.h＞voidfun(charfname,charst){FILE*myf;inti;