首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏
admin
2019-07-12
56
问题
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)(65)。
(65)
选项
A、Θ(n)
B、Θ(lgn)
C、Θ(nlgn)
D、Θ(n
2
)
答案
A
解析
本题考查算法设计与分析的相关知识。中位数的含义:将一组数据按照由小到大(或由大到小)的顺序排列,如果数据的个数是奇数,则处于中间位置的数就是这组数据的中位数;如果数据的个数是偶数,则中间两个数据的平均数就是这组数据的中位数。根据题干的描述,选择的基准元素将数组分得越均匀越好,因此中位数是最佳选择。对于该问题,若每次都是选择中位数作为基准元素,则时间复杂度的递归式为:
T(n)=T(n/2)+cn
求解该递归式,得到T(n)=Θ(n)。
转载请注明原文地址:https://kaotiyun.com/show/khCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
请填充图4-1中的空缺(1)、(2)和(3)处。对于本题的作业处理问题,用图4-1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。图3-1中缺少了一条关联,请指出这条关联两端所对应的类以及每一端的多重度。
根据问题描述,填写图2-1中(1)~(4)处联系的类型。联系类型分为一对一、一对多和多对多三种,分别使用1:1,1:n或1:*,m:n或*:*表示。根据图2-1和说明,将逻辑结构设计阶段生成的关系模式中的空(5)~(8)补充完整。
使用说明中的词语,给出上述顶层数据流图中的外部实体E1~E4的名称。上述0层数据流图中缺少了4条数据流,根据说明及顶层数据流图提供的信息,分别指出这4条数据流的起点和终点。
试分析该关系模式中的函数依赖,并指出关系模式的候地选码。如下的SQL语句是检索“信息系(IS)和计算机科学系(CS)的学生的姓名和性别”的不完整语句,请在空缺处填入正确的内容。SELECT(1)FROM(2)WHERE(3)
用例图解释了活动者与用例之间的交互关系。根据系统设计说明,将系统的顶层用例图补充完整。UML设计中交互图通常可以分为哪两类图?绘制交互图对系统的设计有什么作用?
根据题意,指出数据流图中缺失的数据流(a)的名称,并指出该数据流的起点。根据题意,补充数据字典中(d)、(e)、(f)处的空缺。
阅读以下关于某订单管理系统的技术说明、部分UML类图及Java程序,将Java程序中(1)~(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-16所示。在图5-16中,Product表示产品,Pro
运行Web浏览器的计算机与网页所在的计算机要建立(66)连接,采用(67)协议传输网页文件。
计算机中常用的一种检错码是CRC,即(4)码。在进行编码过程中要使用(5)运算。假设使用的生成多项式是C(x)=x4+x3+x+1。原始报文为11001010101,则编码后的报文为(6)。CRC码(7)的说法是正确的。在无线电通信中采用7中取3定比码,它
随机试题
设y=e-3x+3,则dy=()
美洲钩虫口囊的特征
对于恐惧症的治疗最好选择
犬恶丝虫的幼虫是()。
A.地尔硫卓(硫氮酮)B.洋地黄C.阿托品D.利多卡因E.胺碘酮预激综合征合并快速心房颤动宜选择的治疗药物为
设计方的项目管理工作涉及项目()。
1999年,欧元的正式问世成为21世纪初欧洲甚至世界经济领域的重大事件.其中重大作用表现在()。
红日家电厂是集体所有制企业,刘某是该厂的法定代表人。在经营期间,刘某得知赵某从事走私成品油的活动,为了逃避有关机关的追查,刘某以红日家电厂的名义从赵某处购得成品油12吨,转手将成品油销售,获利8万元,刘某将违法所得占为己有。刘某得知赵某被抓获后,想去公安机
(2015年真题)根据我国特别行政区基本法,下列表述正确的是()。
Thousandsofpeoplearepackedtightlyintrains,themen’sfaces______intheireveningpapers,whilethewomentryinginvain
最新回复
(
0
)