首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
admin
2009-01-10
67
问题
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。
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)问题。
若关系R、S如下图所示,则R与S自然连接后的属性列数和元组个数分别为(28);π1,4(σ3=6(R×S))=(29)。
从数据库管理系统的角度看,数据库系统一般采用如下图所示的三级模式结构。图中①②处应填写(26),③处应填写(27)。
针对程序段:IF(X>10)AND(Y<20)THEN W=W/A,对于(X,Y)的取值,以下(56)组测试用例能够满足判定覆盖的要求。
内存按字节编址,地址从90000H到CFFFFH,若用存储容量为16KB×8bit的存储器芯片构成该内存,至少需要(3)片。
假设在程序控制流图中,有12条边,8个节点,则确保程序中每个可执行语句至少执行一次所必需的测试用例数目的上限是(54)。
对软件可靠性的理解,正确的是(45)。①软件可靠性是指在指定条件下使用时,软件产品维持规定的性能级别的能力②软件可靠性的种种局限是由于随着时间的推移,软件需求和使用方式发生了变化③软件可靠性包括成熟性、有效性、容错性、易恢复性
(25)属于系统软件,它直接执行高级语言源程序或与源程序等价的某种中间代码。
为验证某呼叫中心是否能够承受大量呼叫信息同时呼入并得到正确处理,测试工程师一般采用______测试工具。A.负载压力B.代码C.网络仿真D.故障诊断
若二维数组arr[1..M,1..N]的首地址为base,数组元素按列存储且每个元素占用K个存储单元,则元素arr[i,j]在该数组空间的地址为______。
随机试题
A.易化扩散B.主动转运C.两者都是D.两者都不是氧由肺泡进入血液的方式是
下列哪项可引起真菌性脑膜炎
A.感受暑气B.外感时行疫疠之气C.内为体质虚弱,外为暑热亢盛D.禀赋不足E.感受暑温邪毒
作为整体,通常所说人力资源包含了两个方面,即()。
我国在证券交易的过程中的订单匹配方面,所采用的原则是价格优先和时间优先。( )
下列关于货币制度的说法,错误的是()。
关于财产租赁的转租问题,下列说法正确的是()。
2013年,Q区全年社会消费品零售总额416.1亿元,比上年增加58.3亿元,增长16.3%,完成零售总额超过全年目标0.3个百分点。全区社会消费品零售总额中,限额以上企业共完成148.1亿元,占35.6%。其中,国家标准企业实现社会消费品零售额95.5亿
关于“丝绸之路”,下列说法正确的是()。
考生文件夹下存在一个数据库文件“samp2.accdb”,里面已经设计好“tStud”、“tCourse”、“tScore”三个关联表对象和一个空表“tTemp”。此外,还提供窗体“fTest”和宏“mTest”,试按以下要求完成设计:创建追加查询,将
最新回复
(
0
)