现需要申请，些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果一个活动结束之前，另一个活动开始，即两个活动冲突。若活动A从1时间开始，5时间结束，活动B从5时间开始，8时间结束，则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该

admin2019-10-08 42

问题现需要申请，些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果一个活动结束之前，另一个活动开始，即两个活动冲突。若活动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减去没有安排活动的场地数即可得到所用的最少场地数算法首先采用了快速排序算法进行排序，其算法设计策略是_______(1)；后面步骤采用的算法设计策略是_______(2)。整个算法的时间复杂度是_______(3)。下表给出了n=11的活动集合，根据上述算法，得到最少的场地数为_______(4)。

(3)

选项 A、O(1gn)
B、O(n)
C、O(nlgn)
D、O(n2)

答案C

解析

转载请注明原文地址:https://kaotiyun.com/show/RFCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

写出语句，将(ID=1，Category=pot，DelSize=1.5)的数据插入DELIVERY表中。(1)把对表ZONE的INSERT权限授予用户Smith，并允许他再将此权限授予其他人。(2)收回已经授予Tom的对FlowerInfo中属性C

指出哪张图的哪些文件可以不必画出。数据流图3—4中缺少2条数据流，请直接在图中添加。

填写下列SQL程序中的(1)～(6)，使它们分别完成相应的功能。程序1：查没有借阅过编号为111111图书的所有读者名单。SELECTRno,Rname,address,phoneFROMReaders

阅读下列Java程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】清点盒子。本程序当用户输入一个整数值时，一切正常；当输入其他数值时，程序就出错。现在已做了改进，请填空。importjava.text.NumberFormat；

上表中带下划线的为主码。请为还没有确定主码或是主码不合理的数据表选定最合适的主码。上面的关系模式中还有不是第二范式的，请将其转为第二范式。并确定新数据表的主码。

图7-10中只有一个外部实体E1。使用[说明]中的词语，给出E1的名称。在进行系统分析与设计时，面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。

对于阴道上段淋巴引流，下列哪项不恰当

关于压力管道的水压试验说法，不正确的是()。

在单代号搭接网络计划中，STFi-j表示(　　)。

关于有价证券的期限性，下列描述正确的有()。

一船顺水而下每小时6千米，逆流而上每小时4千米。求往返两地相距24千米的码头间平均速度多少?

教育心理学的发展经历包括()阶段。

下列行为中，符合构成间谍罪客观方面的有

OperaAdshasannouncedtheadditionofnewadunitstohelpNigerianadvertisersincreaseengagementwiththeirtargetaudience

下面关于数据库三级模式结构的叙述中，正确的是()。

SandypromisedtomarryJohn____________(只要她得到父亲的同意).

软件设计师上午基础知识考试

软考中级

写出语句，将(ID=1，Category=pot，DelSize=1.5)的数据插入DELIVERY表中。(1)把对表ZONE的INSERT权限授予用户Smith，并允许他再将此权限授予其他人。(2)收回已经授予Tom的对FlowerInfo中属性C

指出哪张图的哪些文件可以不必画出。数据流图3—4中缺少2条数据流，请直接在图中添加。

填写下列SQL程序中的(1)～(6)，使它们分别完成相应的功能。程序1：查没有借阅过编号为111111图书的所有读者名单。SELECTRno,Rname,address,phoneFROMReaders

阅读下列Java程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】清点盒子。本程序当用户输入一个整数值时，一切正常；当输入其他数值时，程序就出错。现在已做了改进，请填空。importjava.text.NumberFormat；

上表中带下划线的为主码。请为还没有确定主码或是主码不合理的数据表选定最合适的主码。上面的关系模式中还有不是第二范式的，请将其转为第二范式。并确定新数据表的主码。

图7-10中只有一个外部实体E1。使用[说明]中的词语，给出E1的名称。在进行系统分析与设计时，面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。

对于阴道上段淋巴引流，下列哪项不恰当

关于压力管道的水压试验说法，不正确的是()。

在单代号搭接网络计划中，STFi-j表示( )。

关于有价证券的期限性，下列描述正确的有()。

一船顺水而下每小时6千米，逆流而上每小时4千米。求往返两地相距24千米的码头间平均速度多少?

教育心理学的发展经历包括()阶段。

下列行为中，符合构成间谍罪客观方面的有

OperaAdshasannouncedtheadditionofnewadunitstohelpNigerianadvertisersincreaseengagementwiththeirtargetaudience

下面关于数据库三级模式结构的叙述中，正确的是()。

SandypromisedtomarryJohn____________(只要她得到父亲的同意).

在单代号搭接网络计划中，STFi-j表示(　　)。