在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的

试卷名称 2018年下半年软件设计师考试上午真题试题（综合知识）

考试中心《2018年下半年软件设计师考试上午真题试题（综合知识）》在线考试

试卷年份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.Θ(n²)
（3） A.4
B.5
C.6
D.7
（4）A.肯定可以求得问题的一个最优解
B.可以求得问题的所有最优解
C.对有些实例，可能得不到最优解
D.只能得到近似最优解

查看答案

相关试题

第58题：已知某二叉树的先序遍历序列为A B C D E F、中序遍历序列为B A D C F E，则可以确定该二叉树（）。
A.是单支树（即非叶子结点都只有一个孩子）
B.高度为4（即结点分布在4层上）
C.根结点的左子树为空
D.根结点的右子树为空
答案解析与讨论：www.cnitpm.com/st/4074818465.html

第59题：可以构造出下图所示二叉排序树（二叉检索树、二叉查找树）的关键码序列是（）。

A.10 13 17 19 23 27 31 40 65 91
B.23 40 91 17 19 10 31 65 27 13
C.23 19 40 27 17 13 10 91 65 31
D.27 31 40 65 91 13 10 17 23 19
答案解析与讨论：www.cnitpm.com/st/4074923342.html

第60题：图G的邻接矩阵如下图所示（顶点依次表示为v0、v1、v2、v3、v4、v5），G是（请作答此空）。对G进行广度优先遍历（从v0开始），可能的遍历序列为（）。

（1）A.无向图
B.有向图
C.完全图
D.强连通图
（2）A.v0、v1、v2、v3、v4、v5
B.v0、v2、v4、 v5、v1、v3
C.v0、v1、v3、v5、v2、v4
D.v0、v2、v4、v3、v5、v1答案解析与讨论：www.cnitpm.com/st/4075025468.html

第66题：使用ADSL接入Internet，用户端需要安装（）协议。
A.PPP
B.SLIP
C.PPTP
D.PPPoE
答案解析与讨论：www.cnitpm.com/st/4075619779.html

第67题：下列命令中，不能用于诊断DNS故障的是（）。
A.netstat
B.nslookup
C.ping
D.tracert
答案解析与讨论：www.cnitpm.com/st/4075726272.html

第68题：以下关于TCP/IP协议和层次对应关系的表示中，正确的是（）。
A.