信管网综合知识

在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中，可将房子和消防栓均视为直线上的点)。

该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为( 1 )；对应的时间复杂度为( 2 )。

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

(1) A.分治

B.动态规划

C.贪心

D.回溯

(2)A.Θ(lgn)

B.Θ(n)

C.Θ(nlgn)

D.Θ(n2)

(3) A.4

B.5

C.6

D.7

(4)A.肯定可以求得问题的一个最优解

B.可以求得问题的所有最优解

C.对有些实例，可能得不到最优解

D.只能得到近似最优解

信管网参考答案：C、B、B、A

查看解析：www.cnitpm.com/st/407522687.html

相关推荐：

点击查看/下载：软件设计师历年真题汇总

点击查看：软件设计师在线培训课程 丨 免费试听课程

免费练习：软件设计师考试题库(模拟试题、章节练习、每日一练)