软题库 培训课程
当前位置:信管网 >> 在线考试中心 >> 软件设计师题库 >> 试题查看
试卷年份2018年下半年
试题题型【单选题】
试题内容

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

假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是( )。
(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.只能得到近似最优解

查看答案

相关试题