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

admin2019-10-08 48

问题在一条笔直公路的一边有许多房子，现要安装消火栓，每个消火栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中，可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧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。【说明】某城市电信局受理了许多用户申请在指定电话上开设长话业务。长话包括国内长途和国际长途。电信局保存了长话用户档案和长话业务档案。

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

阅读下列函数说明和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

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

阅读以下说明，回答问题1～3，将解答填入对应的解答栏内。[说明]现有两个应用，涉及到两个关系模式：R1(A#，A1，A3，B#，D1)，其上的函数依赖F={A#→A1，A#→A2，A#→A3，(A#，B#)→D1}R2(B#，B1，

阅读下列Java程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】本程序实现功能：读入两个整数，第1个数除以第2个数，声明当除数为零时抛出异常类DivideByZeroException。publicclassDivideByZeroEx

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

君子如祉，亂庶遄已。庶：

患者孙××，女，48岁，近日吞咽梗阻，胸膈痞闷，情志舒畅时可稍减轻，口干咽燥，舌质偏红，苔薄腻，脉弦。诊断属于

已知甲声压是乙声压的2倍，甲声压的声压级为90dB，则乙声压的声压级为()。

某工程双代号时标网络计划如下图所示，该计划表明()。

在商业银行风险管理“三道防线”中，属于第二道防线的部门有()。

简述强迫症的症状表现及其矫正方法。

有两个相同的正方体，每个正方体的六个面上分别标有数字1、2、3、4、5、6，将两个正方体放在桌面上，向上的一面数字之和不超过5的有（）种情形。

在数据库管理系统中，下面哪个模块不是数据库定义的功能模块?

Itusedtobethatifyouwantedtotravel,youhadtoplanforalongbusortrainride.But,thecarchangedallthat.Thougha

WhydosomanyAmericansdistrustwhattheyreadintheirnewspapers?TheAmericanSocietyofNewspaperEditorsistryingtoans