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

admin2019-10-08 39

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

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

软考中级

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

请写出图书馆藏书管理系统的E-R模型图，该系统涉及的实体集及属性。数据依赖对关系模式有哪些影响?请简述这些影响。

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]将一个正整数分解质因数。例如：输入90，打印出90=233*5。main(){intn,i;printf("\npleaseinputa

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

画出上述信息涉及的E—R图。指出每个关系模式的候选码。

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

处在某组织影响范围之中，但与该组织无关，其观点、态度和行为不受该组织的影响，也不对该组织产生作用的公众对象属于()

Before1945,hardlyanyoneoutsideofNewMexicohadeverheardofAlamogordo.In1960itspopulationnumbered21,723.Eversinc

患者，女，40岁，2个月前行765丨固定义齿修复，自诉进食后桥体两侧龈端经常有食物堆积医生检查后首先排除的原凶是

工资核算模块初始设置包括：()、工资项目设置、工资计算公式定义、工资原始数据输入及工资转账定义。

商业承兑汇票到期，承兑人违约拒付或无力支付票款，企业收到银行退回的商业承兑汇票、委托收款凭证、未付票款通知书或拒绝付款证明等，将到期票据的票面金额转入()账户。

属于WAIS—RC言语测验的分测验包括()。

宏命令OPenReport的功能是()。

Whatdoesthemanwanttoorder?

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

软考中级

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

请写出图书馆藏书管理系统的E-R模型图，该系统涉及的实体集及属性。数据依赖对关系模式有哪些影响?请简述这些影响。

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]将一个正整数分解质因数。例如：输入90，打印出90=2*3*3*5。main(){intn,i;printf("\npleaseinputa

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

画出上述信息涉及的E—R图。指出每个关系模式的候选码。

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

处在某组织影响范围之中，但与该组织无关，其观点、态度和行为不受该组织的影响，也不对该组织产生作用的公众对象属于()

Before1945,hardlyanyoneoutsideofNewMexicohadeverheardofAlamogordo.In1960itspopulationnumbered21,723.Eversinc

患者，女，40岁，2个月前行765丨固定义齿修复，自诉进食后桥体两侧龈端经常有食物堆积医生检查后首先排除的原凶是

工资核算模块初始设置包括：()、工资项目设置、工资计算公式定义、工资原始数据输入及工资转账定义。

商业承兑汇票到期，承兑人违约拒付或无力支付票款，企业收到银行退回的商业承兑汇票、委托收款凭证、未付票款通知书或拒绝付款证明等，将到期票据的票面金额转入()账户。

属于WAIS—RC言语测验的分测验包括()。

宏命令OPenReport的功能是()。

Whatdoesthemanwanttoorder?

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]将一个正整数分解质因数。例如：输入90，打印出90=233*5。main(){intn,i;printf("\npleaseinputa