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

admin2019-10-08 41

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

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

选项 A、4
B、5
C、6
D、7

答案B

解析

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

阅读以下说明和c++代码，将应填入(n)处的字句写在对应栏内。【说明】本程序将两个从小到大的有序链表合成一个新的从小到大的有序链表。链表的每一项由类Node描述，而链表由List描述，类List的成员函数有以下几个：creatLi

阅读下列函数说明和C代码，填入(n)处。[说明]以下C语言程序实现了生成从里到外是连续的自然数排列的回旋矩阵，矩阵形式如下：7651681415923

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

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

“巴塞尔新资本协议”的内容涉及()。

(2008年4月)＿＿＿＿＿＿就是突破传统组织结构垂直的纵向一体化特点，组建小型、自主和创新的经营单位，构成以信息全方位沟通的网络制组织形式。

存在于同一个体的抗原称为

男性，20岁，近5年反复咳嗽、咳脓痰，加重伴发热2天，入院抗感染治疗后病情可暂时短期缓解。入院时立即需要做的检查是

女，16周岁，高中学生，因涉嫌盗窃而被公安机关立案侦查。在侦查过程中，依照我国刑事诉讼法的规定，侦查人员讯问时，下述正确的做法是：()

风管系统主要由______等组成。()

建筑内应合理设置的安全疏散设施和避难逃生设施，为安全疏散和救援工作创造良好的条件。下列不属于疏散设计考虑的因素的是()。

为保证来料加工合同的顺利执行，某加工企业要求外商提供一辆小型货运汽车，企业以工缴费偿还车价款。该车进口时可享受免税。()

德育内容是德育工作的出发点，它不仅决定了德育的目标、形式和方法，而且制约着德育工作的基本过程。()

下列对“空化现象”这一概念的理解，准确的一项是()。下列对“超声波清洗技术已成为国内外最有效的清洗手段”这句话的理解，不正确的一项是()。