网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上的点）。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为（请作答此空）；对应的时间复杂度为（ ）。
假设公路起点A的坐标为0，消防栓的覆盖范围（半径）为20米，10栋房子的坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法的叙述中，正确的是（ ）。
假设公路起点A的坐标为0，消防栓的覆盖范围（半径）为20米，10栋房子的坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法的叙述中，正确的是（ ）。
A.分治
B.动态规划
C.贪心
D.回溯
B.动态规划
C.贪心
D.回溯
参考答案
参考解析
解析：（一）对于第一空，本题使用的是分治法。1、分治法特征：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。2、动态规划法：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。本题情景没有列出所有的可能解进行筛选，因此，本题不属于动态规划法。3、回溯法：回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。本题情景没有探索和回退的过程，因此，本题不属于回溯法。4、贪心法：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。在本题情景中，没有给出每步选择的局部最优判断条件，因此，本题不属于贪心法。舍弃已被覆盖的房子，可以将问题的规模逐步缩小，形成规模较小的子问题，而这些问题的求解与原问题的求解过程相同，因此本题属于分治法的算法思想。由于本题的算法过程，是依次与各个房子进行判断，当所有房子都被比较之后，则问题结束，因此时间复杂度与房子的个数相关，本问题的时间复杂度应该趋于现象，为O(n)。对于第三空，关于对应序列（10，20，30，35，60，80，160，210，260，300）第一轮放置：在第一座房子x=10的右侧20米处安装一个消防栓，可以覆盖10，20，30，35这4栋房子；2、第二轮放置：去掉前4栋房子，在第5栋房子x=60的右侧20米处安装一个消防栓，可以覆盖60、80这2栋房子；3、第三轮放置：去掉前面已覆盖的房子，在第7栋房子x=160的右侧20米处安装一个消防栓，只可以覆盖160这一栋房子；4、第四轮放置：去掉前面已覆盖的房子，在第8栋房子x=210的右侧20米处安装一个消防栓，可以覆盖210这一栋房子第五轮放置：去掉前面已覆盖的房子，在第9栋房子x=260的右侧20米处安装一个消防栓，可以覆盖260、300这2栋房子；房子全部覆盖完毕，因此共需安装5个消防栓。对于第四空，对于得到一个最优解是动态规划的特点，可以得到问题所有的最优解，是回溯法的特征，可以排除A、B选项。对于C、D选项。A.肯定可以求得问题的一个最优解B.可以求得问题的所有最优解C.对有些实例，可能得不到最优解D.只能得到近似最优解
更多 “在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上的点）。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为（请作答此空）；对应的时间复杂度为（ ）。 假设公路起点A的坐标为0，消防栓的覆盖范围（半径）为20米，10栋房子的坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法的叙述中，正确的是（ ）。A.分治 B.动态规划 C.贪心 D.回溯 ” 相关考题
考题
村里的房子都不是木房子，有些房子涂上了颜色。由此可以推断( )A.有些房子是涂了颜色的木房子B.有些房子不是涂了颜色的木房子C.有些房子或者是木房子或者是涂了颜色D.有些房子或者不是木房子或者没有涂颜色
考题
甲有一所归自己所有的房子,甲的下列行为中,体现其物权性质的是()。
A、乙欲侵占该房子，甲制止乙侵占的行为B、甲自己居住该房子的行为C、甲拆除自己房子的行为D、甲出卖该房子请求他人支付价款的行为
考题
甲有一所归自己所有的房子，甲的下列行为中，体现其物权性质的有（ ）。A．乙欲侵占该房子，甲制止乙侵占的行为B．甲自己居住该房子的行为C．甲拆除自己房子的行为D．甲出卖该房子请求他人支付价款的行为E．甲出租该房子请求他人支付租金的行为
考题
阅读以下说明和图，填补流程图中的空缺。【说明】在一条农村公路的一边稀疏地分布着房子，其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。实现贪心算法的流程如图10-6所示，请填充其中空白并计算该算法的时间复杂度，其中：1．d[i](1≤i≤N)表示第i个房子到公路A端的距离，N表示房子的总数，房子的编号按照房子到公路A端的距离从小到大进行编号。2．s[k]表示第k(k≥1)个基站到公路A端的距离，算法结束后k的值为基站的总数。该算法的时间复杂度为(5)。
考题
下列每题给出的四个选项中，只有一个选项符合题目要求。基于以下题干：在一不发达的街道上，一开发商要在该街道的一边同时建四幢编号为1，3，5和7的房子，在街道的对边建四幢编号为2，4，6和8的房子。编号为2，4，6和8的房子将分别与编号为1，3，5和 7的房子相对。每幢房子的风格恰好是R，S和T中的某一种，且满足以下条件：相邻的房子具有不同的风格：(1)两个S风格的房子不能对面；(2)每一个R风格的房子至少都有一个T风格的房子与其相邻；(3)3号房子是R风格的；(4)6号房子是S风格的。下面除了哪一幢房子之外都可能是T风格的房子?A．1B．2C．4D．7
考题
在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上的点）。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为（ ）；对应的时间复杂度为（ ）。
假设公路起点A的坐标为0，消防栓的覆盖范围（半径）为20米，10栋房子的坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（请作答此空）个消防栓。以下关于该求解算法的叙述中，正确的是（ ）。A.4
B.5
C.6
D.7
考题
在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上的点）。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为（ ）；对应的时间复杂度为（请作答此空）。
假设公路起点A的坐标为0，消防栓的覆盖范围（半径）为20米，10栋房子的坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法的叙述中，正确的是（ ）。A.O(lgn)
B.O(n)
C.(nlgn)
D.O(n2)
考题
在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上的点）。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为（ ）；对应的时间复杂度为（ ）。
假设公路起点A的坐标为0，消防栓的覆盖范围（半径）为20米，10栋房子的坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法的叙述中，正确的是（请作答此空）。A.肯定可以求得问题的一个最优解
B.可以求得问题的所有最优解
C.对有些实例，可能得不到最优解
D.只能得到近似最优解
考题
甲有一所归自己所有的房屋，甲的下列行为中，体现其物权性质的有（ ）A.乙欲侵占该房子，甲制止乙的侵占行为
B.甲自己居住该房子的行为
C.甲拆除自己房子的行为
D.甲出卖该房子请求他人支付价款的行为
E.甲对房子的装修行为
考题
甲有一所归自己所有的房子，甲的下列行为中，体现其物权性质的有：（）A、乙欲侵占该房子，甲制止乙侵占的行为B、甲自己居住该房子的行为C、甲拆除自己房子的行为D、甲出卖该房子请求他人支付价款的行为
考题
单选题国王要为自己的女儿挑选一个最聪明勇敢的女婿，他向所有的求婚者宣称他已经把公主和两只狮子分别关进了三间房子，然后在三间房子的门上分别写了一句话，让求婚者们去打开自己认为可以打开的门。第一间房门上写着：“这间房子里有狮子。”第二间房门上写着：“公主在第一间房子里。”第三间房门上写着：“这间房子里有狮子。”其实这三句话中，只有一句话是真的。据此可以推断（ ）。A
公主在第一间房子里B
公主在第二间房子里C
公主在第三间房子里D
三间房子里关的都是狮子
考题
多选题甲有一所归自己所有的房子，甲的下列行为中，体现其物权性质的有：（）A乙欲侵占该房子，甲制止乙侵占的行为B甲自己居住该房子的行为C甲拆除自己房子的行为D甲出卖该房子请求他人支付价款的行为
考题
单选题甲男与乙女结婚后，共同购买了一辆汽车和一套房子。关于甲和乙对汽车和房子的所有权，下列说法正确的是________。A
对汽车和房子都是共同所有B
对汽车和房子都是按份所有C
对汽车是共同所有，对房子是按价所有D
对汽车是按份所有，对房子是共同所有
考题
单选题国王要为自己的女儿挑选一个最聪明勇敢的女婿，他向所有的求婚者宣称他已经把公主和两只狮子分别关进了三间房子，然后在三间房子门上分别写了一句话，让求婚者们去打开自己认为可以打开的门。第一间房上写着：“这间房子里有狮子。”第二间房门上写着：“公主在第一间房子里。”第三间房门上写着：“这间房子里有狮子。”其实这三句话中，只有一句话是真的。据此可以推断（ ）。A
公主在第一间房子里B
公主在第二间房子里C
公主在第三间房子里D
三间房子里关的都是狮子
热门标签
最新试卷