在一条笔直公路一边有许多房子，现要安装消防栓，每个消防栓覆盖范围远大于房子面积，如下图所示。现求解能覆盖所有房子最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上点）。该问题求解算法基本思路为：从左端第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖所有房子。在剩余房子中重复上述操作，直到所有房子被覆盖。算法采用设计策略为（ ）；对应时间复杂度为（请作答此空）。
假设公路起点A坐标为0，消防栓覆盖范围（半径）为20米，10栋房子坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法叙述中，正确是（ ）。
- A.见图A
- B.见图B
- C.见图C
- D.见图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.只能得到近似最优解
你可能感兴趣的试题
图 1 是某企业网络拓扑，网络区域分为办公区域、服务器区域和数据区域，线上商城系统为公司提供产品在线销售服务。公司网络保障部负责员工办公电脑和线上商城技术支持和保障工作。
【问题 1】（6 分）某天，公司有一台电脑感染“勒索”病毒，网络管理员应采取（1）、（2）、（3）措施。（1）~（3）备选答案：A.断开已感染主机网络连接B.更改被感染文件扩展名C.为其他电脑升级系统漏洞补丁D.网络层禁止 135/137/139/445 端口 TCP 连接E.删除已感染病毒文件【问题 2】（2分）图 1 中，为提高线上商城并发能力，公司计划增加两台服务器，三台服务器同时对外提供服务，通过在图中（4）设备上执行（5）策略，可以将外部用户访问负载平均分配到三台服务器上。（5）备选答案：A．散列B．轮询C．最少连接D．工作-备份【问题3】（2分）其中一台服务器 IP 地址为 192.168.20.5/27，请将配置代码补充完整。ifcfg-eml 配置片段如下：DEVICE =emlTYPE=EthernetUUID=36878246-2a99-43b4-81df-2db1228eea4bONBOOT=yesNM_CONTROLLED=yesBOOTPROTO=noneHWADDR=90:B1:1C:51:F8:25IPADDR=192.168.20.5NETMASK=（6）GATEWAY=192.168.20.30DEFROUTE= yesIPV4_FAILURE_FATAL=yesIPV6INTI=no【问题 4】（4 分）网络管理员发现线上商城系统总是受到 SQL 注入、跨站脚本等攻击，公司计划购置（7）设备/系统，加强防范；该设备应部署在图 1 中设备①~④（8）处。A．杀毒软件B．主机加固C．WAF（Web 应用防护系统）D．漏洞扫描【问题5】（1分）图 1 中，存储域网络采用是（9）网络。
- 查看答案
阅读以下说明，回答问题1至问题4.将解答填入答题纸对应解答栏内。某企业网络拓扑如图1所示，无线接入区域安装若干无线AP （无线访问接入点）供内部员工移动设备连接互联网，所有AP均由AC（无线控制器）控制，请结合图，回答相关问题。
【问题1】 （6分）常见无线网络安全隐患有IP地址欺骗、数据泄露、（1）、（2）、网络通信被窃听等:为保护核心业务数据区域安全，网络管理员在设备①处部署（3）实现核心业务区域边界防护:在设备②处部署（4）实现无线用户上网行为管控;在设备③处部署（5）分析网络中入侵行为，为加强用户安会认证，配置基于（6）RADIUS认证。（1）~（2）备选答案(每空限选一项，选项不能重复):A.端口扫描B.非授权用户接入C.非法入侵（6）备选答案;A. IEEE 802.11B. IEEE 802.1xD. sql注入攻击【问题2】（4分）桌面虚拟化可能会带来（7）等风险和问题，可以进行（ 8）等对应措施。A.虚拟机之间相互攻击B.防病毒软件扫描风暴C.网络带宽瓶颈D.扩展性差A.安装虚拟化防护系统B.不安装防病毒软件C.提升网络带宽D. 提高服务器配置【问题3】（2分）目前世界公认比较安全公开密钥密码有：基于大合数因子分解困难性RAS密码类和基于（9）困难性ELGamal密码类（包括椭圆曲线密码）。【问题4】（3分）列举三种DES加密算法工作模式。
- 查看答案
【说明】图1为A公司和公司总部部分网络拓扑。
【问题1】（4分，每空2分）网络威胁会导致非授权访问、信息泄露、数据被破坏等网络安全事件发生，其常见网络威胁包括窃听、拒绝服务、病毒、木马、（1）等， 常见网络安全防范措施包括访问控制、审计、身份认证、数字签名、（2）、 包过滤和检测等。（1）备选:A.数据完整性破坏B.物理链路破坏C.机房破坏D.电路干扰（2）备选:A.数据格式转换B.电磁防护C.违规外联控制D.数据加密【问题2】(6分，每空2分)某天，网络管理员在入侵检测设备.上发现图2所示网络威胁日志，从该日志可判断网络威胁为 （3）， 网络管理员应采取（4）、（5）等合理有效措施进行处理。
(3)备选:A.跨站脚本攻击B.拒绝服务C.木马D. sql注入 (4)~(5)备选:A.源主机安装杀毒软件并查杀B.目标主机安装杀毒软件并查杀C.将上图所示URL加入上网行为管理设备黑名单D.将上图所示URL加入入侵检测设备黑名单E.使用漏洞扫描设备进行扫描【问题3】（5分）根据业务发展，购置了一套存储容量为30TB存储系统，给公司内部员工每人配备2TB网盘，存储管理员预估近一年内，员工对网盘平均使用空间不超过200GB，为节省成本，启用了该存储系统自动精简(Thin provisioning不会一次性全部分配存储资源，当存储空间不够时，系统会根据实际所需要容量,从存储池中多次少量扩展存储空间)配置功能，为100个员工提供网盘服务。请简要叙述存储管理员使用自动精简配置优点和存在风险
- 查看答案
在Internet安全领域，扫描器是最有效安全检测工具之一。扫描器是一种自动检测远程或本地主机、网络系统安全性弱点程序。【问题1】（3分）试阐述扫描器作用。【问题2】（3分）阐述漏洞扫描器作用。【问题3】（3分）目前使用IPv4协议支持16位端口，端口号可使用范围是0～65535。（1）端口称为熟知端口，由IANA管理。第二部分端口号（2）叫做注册端口，一般用于客户端连接时随机选择。（3）端口叫做动态端口或专用端口，提供给专用应用程序。【问题4】（2分）TCP SYN扫描中，客户端首先向服务器发送SYN分组发起连接，如果收到一个来自服务器SYN／ACK应答，那么可以推断该端口处于（4） 。如果收到一个RST／ACK分组则认为该端口（5）。【问题5】（4分）蜜罐（Honeypot）技术是一种主动防御技术。根据技术分类，蜜罐可以分为牺牲型蜜罐、外观型蜜罐等。简述牺牲型蜜罐和外观型蜜罐特点。
- 查看答案
图1为某公司拟建数据中心简要拓扑图，该数据中心安全规划设计要求符合信息安全等级保护（三级）相关要求。
【问题1】（6分）1.在信息安全规划和设计时，一般通过划分安全域实现业务正常运行和安全有效保障，结合该公司实际情况，数据中心应该合理地划分为 （1） 、 （2）、 （3） 三个安全域。2.为了实现不同区域边界防范和隔离，在图3-1设备①处应部署 （4） 设备，通过基于HTTP/HTTPS安全策略进行网站等Web应用防护，对攻击进行检测和阻断；在设备②处应部署（5）设备，通过有效访问控制策略，对数据库区域进行安全防护；在设备③处应部署（6）设备，定期对数据中心内服务器等关键设备进行扫描，及时发现安全漏洞和威胁，可供修复和完善。【问题2】（4分）信息安全管理一般从安全管理制度、安全管理机构、人员安全管理、系统建设管理、系统运维管理等方面进行安全管理规划和建设。其中应急预案制定和演练、安全事件处理属于 （7） 方面；人员录用、安全教育和培训属于（8）方面； 制定信息安全方针与策略和日常操作规程属于（9）方面；设立信息安全工作领导小组，明确安全管理职能部门职责和分工属于（10）方面。【问题3】（5分）随着DDoS（Distributed Denial of Service，分布式拒绝服务）攻击技术门槛越来越低，使其成为网络安全中最常见、最难防御攻击之一，其主要目是让攻击目标无法提供正常服务。请列举常用DDoS攻击防范方法。
- 查看答案