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

admin2019-10-08 26

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

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

选项 A、O(lgn)
B、O(n)
C、(nlgn)
D、O(n²)

答案B

解析

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

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

指出算法的流程图中(1)～(3)处的内容。指出测试用例设计中(4)～(9)处的内容。

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

阅读下列函数说明和C代码，应填入(n)处。[说明]假设设A和B均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表(例如，A=(x，y，y，z，x，z)，B=(x，y，y，z，y，x，x，z)，则两者中最大的共同前缀为(x，y，y

阅读下列说明和图，回答问题1至问题3。【说明】某汽车数字仪表板将完成下述功能：(1)通过模/数转换，实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。(4)指

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

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

对空间电荷抵偿变压器的叙述，正确的是

以下不属于建设工程项目实施阶段策划中项目实施的组织策划主要内容的是()。

期货公司的董事会每年至少召开一次会议。(　　)

有效利率是指按复利支付利息条件下的一种复合利率。当每年计息次数在一次以上时，有效利率与一般市场利率的关系是()。

西安饺子宴、西安著名的牛羊肉泡馍和()，一起被誉为“西安饮食三绝”。

高峰体验：人在追求自我实现过程中，经过基本需求的追求并获得满足之后，在追求自我实现时体现到的一种臻于顶峰而又超越时空和自我的心理满足感和成就感。下列不属于高峰体验的是()

企业信息系统项目的基础是企业信息战略规划，规划的起点是将(2)与企业的信息需求转换成信息系统目标，实施信息系统项目是要为企业建立起数据处理中心，以满足各级管理人员关于信息的需求，它坚持以(3)为中心的原则。

下列有关分布式数据库系统的功能特点的叙述不正确的是

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

软考中级

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

指出算法的流程图中(1)～(3)处的内容。指出测试用例设计中(4)～(9)处的内容。

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

阅读下列函数说明和C代码，应填入(n)处。[说明]假设设A和B均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表(例如，A=(x，y，y，z，x，z)，B=(x，y，y，z，y，x，x，z)，则两者中最大的共同前缀为(x，y，y

阅读下列说明和图，回答问题1至问题3。【说明】某汽车数字仪表板将完成下述功能：(1)通过模/数转换，实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。(4)指

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

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

对空间电荷抵偿变压器的叙述，正确的是

以下不属于建设工程项目实施阶段策划中项目实施的组织策划主要内容的是()。

期货公司的董事会每年至少召开一次会议。( )

有效利率是指按复利支付利息条件下的一种复合利率。当每年计息次数在一次以上时，有效利率与一般市场利率的关系是()。

西安饺子宴、西安著名的牛羊肉泡馍和()，一起被誉为“西安饮食三绝”。

高峰体验：人在追求自我实现过程中，经过基本需求的追求并获得满足之后，在追求自我实现时体现到的一种臻于顶峰而又超越时空和自我的心理满足感和成就感。下列不属于高峰体验的是()

企业信息系统项目的基础是企业信息战略规划，规划的起点是将(2)与企业的信息需求转换成信息系统目标，实施信息系统项目是要为企业建立起数据处理中心，以满足各级管理人员关于信息的需求，它坚持以(3)为中心的原则。

下列有关分布式数据库系统的功能特点的叙述不正确的是

期货公司的董事会每年至少召开一次会议。(　　)