首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
admin
2009-01-10
33
问题
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。
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
软件设计师下午应用技术考试
软考中级
相关试题推荐
下列测试工具中,使用(68)执行自动化负载压力测试,使用(69)执行代码静态结构分析,使用(70)执行网络测试。
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
某供应商数据库中的供应关系为SPJ(供应商号,零件号,工担号,数量),如下命令查询某工程至少用了3家供应商(包含3家)供应的零件的平均数量,并按工程号的降序排列。SELECT工程号,(14)FROMSPJGROUPBY工程号(15)
针对以下C语言程序段,对于(MaxNum,Type)的取值,至少需要(62)个测试用例能够满足判定覆盖的要求。while(MaxNum-->0){if(10==Type)x=y*2;elseif(100==Type)
若关系R、S如下图所示,则R与S自然连接后的属性列数和元组个数分别为(28);π1,4(σ3=6(R×S))=(29)。
设有职工EMP(职工号,姓名,性别,部门号,职务,进单位时间,电话),职务JOB(职务,月薪)和部门DEPT(部门号,部门名称,部门电话,负责人)实体集。一个职务可以由多个职工担任,但一个职工只能担任一个职务,并属于一个部门,部门负责人是一个职工。下图所示
针对程序段:IF(X>10)AND(Y<20)THEN W=W/A,对于(X,Y)的取值,以下(56)组测试用例能够满足判定覆盖的要求。
在执行测试和评价的过程中,会产生较多的文档,(43)是对文档内容的正确描述。①评价需求的主要内容是描述评价的目标,特别是描述了产品的质量需求。②评价规格说明的主要内容是确定对软件及其部件实行的所有分析和测量,标识要采用的操作规程、测试方法和工具。③评
V模型描述了软件基本的开发过程和测试行为,描述了不同测试阶段与开发过程各阶段的对应关系。其中,集成测试阶段对应的开发阶段是______。A.需求分析阶段B.概要设计阶段C.详细设计阶段D.编码阶段
随机试题
若有以下定义:chars[20]=="programming",*ps=s;则不能代表字符o的表达式是()
对阵发性室性心动过速伴明显血流动力学障碍者,首选治疗是
A.不得调剂B.应当告知处方医师,请其确认或者重新开具处方C.药师可自行修改D.应当拒绝调剂,及时告知处方医师,并应当记录,按照有关规定报告在处方调剂过程中,最关键的步骤就是药师对处方的核查。在审核的过程中,药师应该经处方审核后,认为存在用药不
实现A/D转换的核心环节是()。
城市轨道交通线网规划的主要任务是研究确定城市轨道交通发展目标和()
某一回转运动的反应釜,工艺要求在负压下工作,釜内壁需采用金属铅防腐蚀,覆盖铅的方法应为()。
借款偿还期指标适用于()。
从现实的应用形态来看,饭店员工的劳动能力主要表现为()。
学习质量的检测与评定,对深入教学研究、深化教学改革具有()作用。
Inthepasttwentyyears,hehas______greatwealthbyhardwork.
最新回复
(
0
)