首页
登录
从业资格
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
练习题库
2022-08-02
53
问题
在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的数组进行排序的时间复杂度为且是稳定的(即如果待排序的序列中两个
随机试题
It’sasurethingthatifsheknowsthatthereisa______saleintown,shewill
Fortyyearsagopeoplewereindifferenttothehealthoftheoceanbecause_____
[originaltext]Atthisweek’sCEStechnologyexpo,LGwillbeoneofmanyTV
下列各组词语中,没有别字的是( )。A.别出心裁 茕茕孑立 B.相提并论 因
将科技成果转化为生产力的主要环节是()A.基础性研究 B.应用研究 C.
可与Tn结合引起其构象改变的离子是A.钠离子B.钾离子C.钙离子D.镁离子E.氯
工程设计质量管理的依据,不属于项目批准文件的是( )。 A、项目可行性研究报
等渗性缺水的主要病理基础是A.细胞外液浓缩 B.细胞内液低渗 C.细胞外液容
①连成熟的文字都没有产生,人们交流信息除了口传外,就是通过结绳记事 ②通过开放
关于专项施工方案专家论证制度,下列说法中正确的是()。A.对达到一定规模的危险
最新回复
(
0
)