首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
admin
2009-01-10
97
问题
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。
A:待排序数组
p,r: 数组元素下标,从p到r
q: 划分的位置
x:枢轴元素
i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值
j:循环控制变量,表示数组元素下标
QUICKSORT (A,p,r){
if (p <r){
q=PARTITION(A,p,r) ;
QUICKSORT(A,p,q-1);
QUICKSORT(A,q+1,r);
}
}
PARTITION(A,p,r){
x=A[r];i=p-1;
for(j=p;j≤r-1;j++){
if (A[j]≤x){
i=i+1;
交换A
和A[j]
}
}
交(1)和(2)//注:空(1)和空(2)答案可互换,但两空全部答对方可得分 return (3)
}
(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用O记号。最佳情况为(4),平均情况为(5),最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况?(7)。(最佳,平均、最坏)
选项
答案
(4)O(nlgn)或O(log
2
n) (5)O(nlgn)或O(nlog
2
n) (6)O(n
2
) (7)最坏
解析
转载请注明原文地址:https://kaotiyun.com/show/P5DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
通过疲劳强度测试,最容易发现(55)问题。
以下各项中,(51)属于需求说明书的评测内容。①系统定义的目标是否与用户的要求一致②设计的约束条件或限制条件是否符合实际③是否考虑过软件需求的其他方案④软件的行为与它必须处理的信息、必须完成的功能是否一致
(12)是指把数据以及操作数据的相关方法组合在同一个单元中,使我们可以把类作为软件中的基本复用单元,提高其内聚度,降低其耦合度。面向对象中的(13)机制是对现实世界中遗传现象的模拟,通过该机制,基类的属性和方法被遗传给派生类。
黑盒测试中,(59)是根据输出对输入的依赖关系设计测试用例。
J2EE系统架构被各种信息系统普遍采用,______不属于其服务器端应用组件。A.ServletB.JSPC.EJBD.Applet
关于bug管理流程,______是正确的做法。A.开发人员提交新的bug入库,设置状态为“New”B.开发人员确认是bug,设置状态为“Fixed”C.测试人员确认问题解决了,设置状态为“Closed”D.测试人员确认不是bug,设置状态为“Reo
关系数据库管理系统应能实现的专门关系运算包括______。A.选择、索引、统计B.选择、投影、连接C.关联、更新、排序D.显示、打印、制表
以下关于软件生命周期的叙述不正确的是______。A.软件生命周期包括以下几个阶段:项目规划、需求定义和需求分析、软件设计、程序编码、软件测试、运行维护B.程序编码阶段是将软件设计的结果转换成计算机可运行的程序代码。为了保证程序的可读性、易维护性和提高
模块设计中,某模块根据输入的控制信息从文件中读一个记录或者向文件中写一个记录,则其内聚类型为______。
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则___________(41)是一个大项堆结构,该堆结构用二叉树表示,其高度(或层数)为___________(42)。(41)
随机试题
蛛网膜下腔出血最可靠的诊断依据是()
有种观点认为,在法与社会的关系问题上,“纸上的法”必须要以“活法”为基础,否则“纸上的法"将失去生命力。对于这种说法,下列理解错误的是哪一项?()
当前,各类安全生产问题错综复杂,但其中影响最大、危害最严重的是()。
一国同其他国家之间的利率相对水平的高低是影响汇率的重要因素。()
关于印花税的说法正确的是()。
根据基金法律地位不同可分为公司型基金和契约型基金,下列描述中不属于公司型基金的是()。
补写出下列名句名篇中的空缺部分。曹操《短歌行》抒发了广招贤才,一统天下的博大胸怀,诗的最后四句是:“________,________,周公吐哺,天下归下。”
阅读下列文字,完成以下问题改革开放以来,我国个体私营经济的发展速度成倍地高于全国经济增长速度,2004年我国个体私营经济占GDP的比重已超过1/3。2004年的GDP总量为138,515亿元。截至2004年底,个体私营经济已占全国工业增加值和销售
下列无穷小中阶数最高的是().
A、Demandapromptresponse.B、Provideallthedetails.C、Senditbyexpressmail.D、Sticktothepoint.D
最新回复
(
0
)