2. 从业资格
  3. 现需要申请一些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果

现需要申请一些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果

练习题库2022-08-02  40
问题 现需要申请一些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果一个活动结束之前，另一个活动开始，即两个活动冲突。若活动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的活动集合，根据上述算法，得到最少的场地数为（　　）。问题1选项A.分治B.动态规划C.贪心D.回溯问题2选项A.分治B.动态规划C.贪心D.回溯问题3选项A.Θ(lgn)B.Θ(n)C.Θ(nlgn)D.Θ(n2)问题4选项A.4B.5C.6D.7
选项
答案 ACDB
解析 快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题，然后再将这些子问题的解组合成原问题的解，其时间复杂度为Θ（nlog2n）。贪心法总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。根据其算法可得，p1场地可排a1、a8、a11；p2场地可排a2、a6、a9；p3场地可排a3；p4场地可排a4、a7；p5场地可排a5、a10；最少需要的场地数为5。通过比较过程可以看到，比较时需要对场地和活动两个维度进行遍历，二者最大值都可以取到n，是两层嵌套循环，时间复杂度为Θ（n2），整体时间复杂度选择D选项。
转载请注明原文地址:https://tihaiku.com/congyezige/2410412.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)