首页
登录
从业资格
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
练习题库
2022-08-02
50
问题
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分,先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)(65)。A.Θ(n)B.Θ(lgn)C.Θ(nlgn)D.Θ(n2)
选项
A.Θ(n)
B.Θ(lgn)
C.Θ(nlgn)
D.Θ(n2)
答案
D
解析
本题考查数据结构基础知识。快速排序一种分治的排序方法,其思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。快速排序的每一趟结果都是找到一个基准元素放置于线性表中部位置,将原来的线性表划分为前后两部分,前部分元素都小于基准元素,后部分元素都大于基准元素。快速排序总的关键字比较次数为Θ(nlog2n),最坏情况下时间复杂度为Θ(n2),最好情况下的时间复杂度为Θ(nlog2n);快速排序是不稳定的排序。最坏情况下需要的栈空间为Θ(n),其他需要Θ(nlog2n)。根据以上描述,本题依次选C、D选项。
转载请注明原文地址:https://tihaiku.com/congyezige/2407853.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户服务要
若二维数组arr[1..M,1..N]的首地址为base,数组元素按列存储且每
在软件开发过程中,详细设计的内容不包括()设计A.软件体系结构 B.算法
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用是否合理
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户的服务
下列算法中,不属于公开秘钥加密算法的是()? A.ECC B.DSA C
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素
设数组a[1..10,1..8]中的元素按行存放,每个元素占用4个存储单元,已知
若要求对大小为n的数组进行排序的时间复杂度为且是稳定的(即如果待排序的序列中两个
随机试题
泰山的每个季节都有独特的魅力。春天,绿茵茵的山坡上,争奇斗艳的花朵到处可见。夏天,泰山的雷暴雨堪称奇观。秋天,枫树叶漫山遍野,蔚蓝色的河水穿流而行。冬天
Thefirstpermanentpicturewasmadebyusing_________[originaltext]TodayI
Time______,thecelebrationwillbeheldasscheduled.A、permitB、permittingC、p
确定会计核算工作空间范围的前提条件是()。A.会计主体 B.持续经营 C.会
Ante主张A.以缺牙部位决定基牙数目 B.以上都不对 C.以牙合力比值决定
在客户关系管理理念里,客户价值的预测通常采用下列()方式进行。A.客户消费量最
下列各项,不属亚急性再型肝炎并发症的是A.脑水肿 B.消化道出血 C.血糖增
(2019年真题)侦查机关在办理一起武装暴乱案时,办案人员王某发现犯罪嫌疑人系其
确定颌位关系包括A.定位平面记录 B.下颌后退记录 C.面下1/3高度记录
妊娠早期羊水的主要来源是A.母血清经胎膜进入羊膜腔的透析液 B.胎儿尿液 C
最新回复
(
0
)