免费智能真题库 > 历年试卷 > 软件设计师 > 2018年上半年 软件设计师 上午试卷 综合知识
  第61题      
  知识点:   贪心法
  章/节:   计算机软件知识       

 
现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。
求解该问题的基本思路如下(假设需要场地数为m,活动数为n,场地集合为P1P2,…,Pm),初始条件Pi均无活动安排:
(1)采用快速排序算法对n个活动的开始时间从小到大排序,得到活动a1a2,…,an。对每个活动aii从1到n,重复步骤(2)、(3)和(4);
(2)从P1开始,判断aiP1的最后一个活动是否冲突,若冲突,考虑下一个场地P2,…;
(3)一旦发现ai与某个Pj的最后一个活动不冲突,则将ai安排到Pj,考虑下一个活动;
(4)若ai与所有已安排活动的Pj的最后一个活动均冲突,则将ai安排到一个新的场地,考虑下一个活动;
(5)将n减去没有安排活动的场地数即可得到所用的最少场地数。
算法首先采用了快速排序算法进行排序,其算法设计策略是( 60 );后面步骤采用的算法设计策略是( 61 )。整个算法的时间复杂度是( 62 )。下表给出了n=11的活动集合,根据上述算法,得到最少的场地数为( 63 )。
 
 
  A.  分治
 
  B.  动态规划
 
  C.  贪心
 
  D.  回溯
 
 
 

 
  第62题    2018年上半年  
   65%
现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个..
  第62题    2014年下半年  
   48%
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值..
  第64题    2012年上半年  
   52%
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有的运输目的地,到达每个运输目的地一次且仅一次..
   知识点讲解    
   · 贪心法
 
       贪心法
               和动态规划法一样,贪心法也经常用于解决最优化问题。不过与动态规划法不同的是,贪心法在解决问题的策略上是仅根据当前已有的信息作出选择,而且一旦作出选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所作出的选择只是在某种意义上的局部最优。
               用贪心法求解的问题一般具有以下两个重要的性质。
               (1)最优子结构。当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
               (2)贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来得到。这是贪心法和动态规划法的主要区别。
   题号导航      2018年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第61题    在手机中做本题