首页
登录
从业资格
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思
考试题库
2022-08-02
19
问题
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分,先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)(65)。A.第一个B.最后一个C.中位数D.随机一个
选项
A.第一个
B.最后一个
C.中位数
D.随机一个
答案
C
解析
本题考查数据结构基础知识。快速排序一种分治的排序方法,其思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。快速排序的每一趟结果都是找到一个基准元素放置于线性表中部位置,将原来的线性表划分为前后两部分,前部分元素都小于基准元素,后部分元素都大于基准元素。快速排序总的关键字比较次数为Θ(nlog2n),最坏情况下时间复杂度为Θ(n2),最好情况下的时间复杂度为Θ(nlog2n);快速排序是不稳定的排序。最坏情况下需要的栈空间为Θ(n),其他需要Θ(nlog2n)。根据以上描述,本题依次选C、D选项。
转载请注明原文地址:https://tihaiku.com/congyezige/2407808.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如
加密和解密是明文和密文之间的可逆转换,( )不属于加密算法。A.RSA B.
在软件开发过程中,详细设计的内容不包括()设计A.软件体系结构 B.算法
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据
结构化开发方法中,()主要包含对数据结构和算法的设计。对算法设计时,其主要依据
结构化开发方法中,(请作答此空)主要包含对数据结构和算法的设计。对算法设计时,其
若要求对大小为n的数组进行排序的平均时间复杂度为O(nlog2n),且是不稳定的
对n个数排序,平均情况下时间复杂度最低的算法是()排序算法。A.直接插入排序
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素
随机试题
[originaltext]Germany’sRhineRiverishundredsofmileslong,butnotall
[originaltext][3]Internationalinvestigatorshavepublishedaphotoofala
Supposeyougointoafruiter’sshop,wantinganapple—youtakeupone,ando
货币政策中介目标承担的功能主要包括()。A.传导功能 B.测度功能 C.
A.rr1=kλ B. C. D.
患者,男性,65岁,主因咳嗽、咳痰10年,加重伴痰中带血4个月入院。吸烟30余年
期末对具有减值迹象的固定资产进行减值测试时,影响其可收回金额的因素有( )。A.
成人双上肢烧伤面积约为( )。A.18% B.22% C.12% D.1
国民收入最终分配结果通过初次收入分配和二次收入分配达成。政府凭借权力在初次分配中
下列资料为定性资料的是A.坐高指数(%,坐高/身高) B.血型(A、B、O、A
最新回复
(
0
)