现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动 A 从 1 时间开始,5 时间结束,活动 B 从 5 时间开始,8 时间结束,则活动 A 和 B 不冲突。现要计算 n 个活动需要最少场地数。求解该问题基本思路如下(假设需要场地数为 m,活动数为 n,场地集合为 P1，P2,…,Pm),初始条件 Pi均无活动安排:(1)采用快速排序算法对 n 个活动开始时间从小到大排序,得到活动 a1，a2,…，an。对每个活动 ai，i 从 1 到 n,重复步骤(2)、(3)和(4)；(2)从 p1开始,判断 ai与 P1最后一个活动是否冲突,若冲突,考虑下一个场地 P2,…；(3)一旦发现 ai与某个 Pj最后一个活动不冲突,则将 ai安排到 Pj,考虑下一个活动；(4)若 ai与所有己安排活动 Pj最后一个活动均冲突,则将 ai安排到一个新场地,考虑下一个活动；(5)将 n 减去没有安排活动场地数即可得到所用最少场地数算法首先采用了快速排序算法进行排序,其算法设计策略是（ ）；后面步骤采用算法设计策略是( )。整个算法时间复杂度是( )。下表给出了 n=11 活动集合,根据上述算法,得到最少场地数为(请作答此空)。
- A.4
- B.5
- C.6
- D.7
正确答案及解析
正确答案
解析
快速排序由C.A.R.Hoare在1962年提出。它基本思想是：通过一趟排序将要排序数据分割成独立两部分，其中一部分所有数据都比另外一部分所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序采用思想是分治思想。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好选择。也就是说，不从整体最优上加以考虑，他所做出是在某种意义上局部最优解。整个算法时间复杂度是O(nlogn)。场地上可以安排活动1、8、11为一个场地；活动2、6、9一个场地；活动3为一个场地；活动4、7为一个场地；活动5、10为一个场地，共5个场地。
你可能感兴趣的试题
【说明】
某公司现有网络拓扑结构如图1-1所示。该网络中使用交换机SW1为三层交换机，SW2和SW3均为二层智能交换机。
【问题4】（4分）
为了对用户上网行为进行监管，需要在SW1与R1之间部署（9）。
（9）备选答案：
A.FW（防火墙） B.IDS（入侵检测系统） C.堡垒机 D.上网行为管理
随着公司各部门成员增加，某些时候部分员工获取到IP地址和真实DHCP分出来IP不一致，为了避免这种情况可以在交换机上开启（10）功能。
（10）备选答案：
A．dhcp snooping B. broadcast-suppression C. loopback-detect
- 查看答案
阅读下列说明，回答问题1至问题5，将解答填入答题纸对应栏内。 【说明】 攻克要塞教育中心在部署计算机网络时采用了一款硬件防火墙，该防火墙带有三个以太网络接口，其网络拓扑如图3-1所示。
【问题1】（8分）
防火墙包过滤规则默认策略为拒绝，表3-1给出防火墙包过滤规则配置。若要求内部所有主机能使用IE浏览器访问外部IP地址202.117.118.23Web服务器，为表中（1）~（4）空缺处选择正确答案，填写在答题纸相应位置。（1）备选答案：A．允许 B．拒绝（2）备选答案：A．192.168.1.0/24 B．211.156.169.6/30 C．202.117.118.23/24（3）备选答案：A．TCP B．UDP C．ICMP（4）备选答案：A．E3E2 B．E1E3 C．E1E2
【问题2】（6分）
内部网络经由防火墙采用NAT方式与外部网络通信，表3-2中（5）~（7）空缺处选择正确答案，填写在答题纸相应位置。（5） 备选答案：A．192.168.1.0/24 B．anyC．202.117.118.23/24（6）备选答案： A．E1 B．E2 C．E3（7）备选答案： A．192.168.1.1 B．210.156.169.6C．211.156.169.6
【问题3】（2分）
图3-1中 （8）适合设置为DMZ区。（8）备选答案：A．区域A B．区域B C．区域C【问题4】（4分）防火墙上配置信息如图3-2所示。要求启动HTTP代理服务，通过HTTP缓存提高浏览速度，代理服务端口为3128，要使主机PC1使用HTTP代理服务，其中“地址”栏中内容应填写为 （9） ，“端口”栏中内容应填写为 （10） 。
【问题5】（4分）
NAT和HTTP代理分别工作在 （11） 和 （12） 。（11）备选答案：A．网络层 B．应用层 C．服务层（12）备选答案：A．网络层 B．应用层 C．服务层
- 查看答案
阅读以下说明，回答问题1至问题4，将解答填入答题纸对应解答栏内。
【说明】
某企业采用PIX防火墙保护公司网络安全，网络结构如图4-1所示。
【问题1】（4分）
防火墙一般把网络区域划分为内部区域（trust区域）、外部区域（untrust区域）以及(1)，其中在这个网络区域内可以放置一些公开服务器，下列(2)服务器不适合放在该区域。
空(2)备选答案：
A．Web
B．FTP
C．邮件
D．办公自动化(OA)
【问题2】（2分）
衡量防火墙性能主要参数有并发连接数、用户数限制、吞吐量等，其中最重要参数是(3)，它反映出防火墙对多个连接访问控制能力和连接状态跟踪能力，这个参数大小直接影响到防火墙所能支持最大信息点数。
空(3)备选答案：
A．并发连接数
B．用户数限制
C．吞吐量
D．安全过滤带宽
【问题3】（4分）
设置防火墙接口名称，并指定安全级别，安全级别取值范围为0～100，数字越大安全级别越高。要求设置：ethemet0命名为外部接口outside，安全级别是0；ethernet1命名为内部接口inside，安全级别是100；ethernet2命名为中间接口dmz，安全级别为50。
请完成下面命令。
…
PLX#config terminal
PLX (config)#nameif ethemet0 (4) security0
PLX (config)#nameif ethernet1 inside (5)
PLX (config)#nameif ethemet2 (6) (7)
…
【问题4】（5分）
编写表4-1中规则，设置防火墙安全规则，允许外网主机133.20.10.10访问内网数据库服务器10.66.1.101，同时允许内网和外网访问DMZ区WWW服务器10.65.1.101。
- 查看答案
阅读以下说明，回答问题一，并将解答填入答题纸对应解答栏中。 某公司用ASP 实现了用户满意度调查网页，系统几个主要文件及作用如表1所示， 网页效果如图1 所示。
用户调查数据库表info表结构如表2所示：
问题1：完成下列代码填空
备选答案：A.用户满意度调查 B. rs C. username
D. ＜/frameset> E. dbpathF.Conn G.exec H. top.html I.info J. login.asp K.searchtext L. rs.EOF M. MoveNext N.wt1 O. rowcount
- 查看答案
阅读下列有关网络防火墙说明，回答问题1至问题4，将答案填入答题纸对应解答栏内。
【说明】
某公司网络有200台主机、一台WebServer和一台MailServer。为了保障网络安全，安装了一款防火墙，其网络结构如图4-1所示，防火墙上配置NAT转换规则如表4-1所示。
防火墙配置遵循最小特权原则（即仅允许需要数据包通过，禁止其他数据包通过），请根据题意回答以下问题。
【问题1】（6分，每空1分）
防火墙设置缺省安全策略如表4-2所示，该策略含义为：内网主机可以访问WebServer、MailServer和Internet，Intemet主机无法访问内网主机和WebServer、MailServer。
如果要给Internet主机开放WebServerWeb服务以及MaiIServer邮件服务，请补充完成表4-3策略。（注：表4-3策略在表4-2之前生效）
【问题2】（3分，每空1分）
如果要禁止内网用户访问Internet上202.10.20.30FTP服务，请补充完成表4-4策略。
（注：表4-4策略在表4-2之前生效）
问题3】（4分，每空1分）
如果要禁止除PC1以外所有内网用户访问Internet上219.16.17.18Web服务，请补充
完成表4-5策略。（注：表4-5策略在表4-2之前生效）
【问题4】（2分，每空1分）
如果要允许Intemet用户通过Ping程序对WebServer连通性进行测试，请补充完成表4-6策略。（注：表4-6策略在表4-2之前生效）
- 查看答案