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

admin2019-10-08 52

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

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

选项 A、分治
B、动态规划
C、贪心
D、回溯

答案A

解析

转载请注明原文地址:https://kaotiyun.com/show/VGCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

指出算法的流程图中(1)～(3)处的内容。指出测试用例设计中(4)～(9)处的内容。

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

请写出图书馆藏书管理系统的E-R模型图，该系统涉及的实体集及属性。根据E-R图中给出的词汇，按照“关系模式名(属性，属性，…)”的格式，将此E-R图转换为7个关系模式，其中模式名根据需要取实体名或联系名。

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btreeB){btreestack[m0

阅读下列函数说明、图和C代码，将应填入(n)处的字句写在对应栏内。【说明】假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]

三视图是指、和。

设f(x)=试确定k的值使f(x)在点x=1处连续．

[*]

施工招标时，下列情况中()属于废标。

商店建筑营业厅内自动扶梯设置的规定是：Ⅰ．坡度应等于或小于35°；Ⅱ．坡度应等于或小于30°；Ⅲ．上下两端水平部分2m范围内应留出人流缓冲空间；Ⅳ．上下两端水平部分3m范围内应留出人流缓冲空间。

以货币价格作为评价指标的评标价法，依据标的性质不同可以分为()。

银行对于次级类贷款按季计提专项准备，计提比例为()。

企事业单位进行技术转让，以及在此过程中发生的相关技术培训所得，年净收入在()万元以下的，暂免征收所得税。

导游服饰的要求不包括()。

Thecoupleconsultedexpertsanddecidedtobuythenewhouseonmonthlypaymentplan.

软件设计师上午基础知识考试

软考中级

指出算法的流程图中(1)～(3)处的内容。指出测试用例设计中(4)～(9)处的内容。

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

请写出图书馆藏书管理系统的E-R模型图，该系统涉及的实体集及属性。根据E-R图中给出的词汇，按照“关系模式名(属性，属性，…)”的格式，将此E-R图转换为7个关系模式，其中模式名根据需要取实体名或联系名。

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btree*B){btree*stack[m0

阅读下列函数说明、图和C代码，将应填入(n)处的字句写在对应栏内。【说明】假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]

三视图是指________、________和________。

设f(x)=试确定k的值使f(x)在点x=1处连续．

[*]

施工招标时，下列情况中()属于废标。

商店建筑营业厅内自动扶梯设置的规定是：Ⅰ．坡度应等于或小于35°；Ⅱ．坡度应等于或小于30°；Ⅲ．上下两端水平部分2m范围内应留出人流缓冲空间；Ⅳ．上下两端水平部分3m范围内应留出人流缓冲空间。

以货币价格作为评价指标的评标价法，依据标的性质不同可以分为()。

银行对于次级类贷款按季计提专项准备，计提比例为()。

企事业单位进行技术转让，以及在此过程中发生的相关技术培训所得，年净收入在()万元以下的，暂免征收所得税。

导游服饰的要求不包括()。

Thecoupleconsultedexpertsanddecidedtobuythenewhouseonmonthlypaymentplan.

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。Voidpostorder(btreeB){btreestack[m0

三视图是指、和。