首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
admin
2009-01-10
90
问题
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。
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)问题。
在CPU与主存之间设置高速缓冲存储器(Cache)的目的是为了(2)。
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
(12)是指把数据以及操作数据的相关方法组合在同一个单元中,使我们可以把类作为软件中的基本复用单元,提高其内聚度,降低其耦合度。面向对象中的(13)机制是对现实世界中遗传现象的模拟,通过该机制,基类的属性和方法被遗传给派生类。
关于数据库索引,以下表述正确的是(57)。①如果对表创建了索引,那么更新、插入和删除表中的记录都将导致额外的系统开销。②全表扫描一定比使用索引的执行效率低。③在字段选择性很低的情况下适用索引。④一个表创建的索引越多,对系统的性能提升越大。
针对下列程序段,需要(52)个测试用例才可以满足语句覆盖的要求。 switch(value){ case 0: other=30; break; case 1:
软件能力成熟度模型(CMM)将软件能力成熟度自低到高依次划分为5级。目前,达到CMM第3级(已定义级)是许多组织努力的目标,该级的核心是(29)。
对需求说明书评测的内容包括______。①系统定义的目标是否与用户的要求一致②被开发项目的数据流与数据结构是否足够、确定③与所有其他系统交互的重要接口是否都已经描述④主要功能是否已包含在规定的软件范围之内,是否都已充分说明
V模型描述了软件基本的开发过程和测试行为,描述了不同测试阶段与开发过程各阶段的对应关系。其中,集成测试阶段对应的开发阶段是______。A.需求分析阶段B.概要设计阶段C.详细设计阶段D.编码阶段
假设段页式存储管理系统中的地址结构如下图所示,则系统()。
随机试题
A.Meigs综合征B.阿司匹林三联症C.Kartagener综合征D.Wegener肉芽肿E.Good-pasture综合征
A.患者B.病案管理人员C.医院管理人员D.医技人员E.护士提供真实可靠的病情描述,不可随手拿走病案的是
枳术丸的功用是
变电所操作电源分为()。
沪深300成长指数和沪深300价值指数的样本数量均固定为( )只。
行政复议期间,有下列情形之一的,行政复议终止()。
在软件生命周期中,能准确确定软件系统必须做什么和必须具备哪些功能的阶段是
小王利用Word撰写专业学术论文时,需要在论文结尾处罗列出所有参考文献或书目,最优的操作方法是
Readthearticlebelowabouteffectivenegotiating.Foreachquestion1-10,writeoneword.Wearealwaysnegotiating,not
Tomfailedintheexam.Helooked______.
最新回复
(
0
)