首页
登录
从业资格
现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果
现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果
最全题库
2022-08-02
28
问题
现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动 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.Θ(lgn)B.Θ(n)C.Θ(nlgn)D.Θ(n2)
选项
A.Θ(lgn)
B.Θ(n)
C.Θ(nlgn)
D.Θ(n2)
答案
C
解析
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。整个算法的时间复杂度是O (nlogn)。场地上可以安排活动1、8、11为一个场地;活动2、6、9一个场地;活动3为一个场地;活动4、7为一个场地;活动5、10为一个场地,共5个场地。
转载请注明原文地址:https://tihaiku.com/congyezige/2408471.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
算术表达式采用后缀式表示时不需要使用括号,使用()就可以方便地进行求值。a-b
在高级语言源程序员,常需要用户定义的标识符程序员的对象命名,常见的命名对象有(
流水线的吞吐率是指单位时间流水线处理的任务数,如果各段流水的操作时间不同,则流水
若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别是t取指=2
MPEG视频中的时间冗余信息可以采用()的方法来进行压缩编码。A.帧间预测和变
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
甲、乙两软件公司于2012年7月12日就其财务软件产品分别申请“用友”和“用有”
甲、乙两人在同一时间就同样的发明创造提交了专利申请,专利局将分别向各申请人通报有
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动
随机试题
【B1】[br]【B8】[originaltext]Thehumanbraincontains10thousandmillionce
Thecasualuseoflanguagewhichconsistsofexpressivebutnon-standardvocabul
“崇高”属于( )。A.普遍概念 B.单独概念 C.集合概念 D.正概念
标准的实施状况是指标准批准发布后一段时间内,工作性质差别不大,通过综合各项评价指
症见一身面目俱黄,黄色鲜明,身热,无汗或但头汗出,口渴欲饮,恶心呕吐,腹微满,小
发热而赤,汗出口渴,面赤心烦,舌红,脉洪大,宜用方剂A.竹叶石膏汤B.犀角地黄汤
A.枸橼酸他莫昔芬B.巯嘌呤C.紫杉醇D.吉非替尼E.异环磷酰胺作用机制为表皮生
患者,男性,33岁,因腰椎间盘突出症急性发作入院接受牵引治疗,护理措施正确的是A
关于合同履行跟踪实施要点的表述中,不正确的是()。A、项目跟踪是指对整个项目合同
2007年5月单项选择题 评定求助者的抑郁症状可使用()。 A.SDS
最新回复
(
0
)