首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。 A:待排序数组 p,r: 数组元素下标,从p到r q: 划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
admin
2009-01-10
64
问题
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。
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)用来描述核心业务逻辑。
阅读下列流程图:当用判定覆盖法进行测试时,至少需要设计(44)个测试用例。
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
关于数据库索引,以下表述正确的是(57)。①如果对表创建了索引,那么更新、插入和删除表中的记录都将导致额外的系统开销。②全表扫描一定比使用索引的执行效率低。③在字段选择性很低的情况下适用索引。④一个表创建的索引越多,对系统的性能提升越大。
黑盒测试中,(59)是根据输出对输入的依赖关系设计测试用例。
对软件可靠性的理解,正确的是(45)。①软件可靠性是指在指定条件下使用时,软件产品维持规定的性能级别的能力②软件可靠性的种种局限是由于随着时间的推移,软件需求和使用方式发生了变化③软件可靠性包括成熟性、有效性、容错性、易恢复性
模块设计中,某模块根据输入的控制信息从文件中读一个记录或者向文件中写一个记录,则其内聚类型为______。
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则___________(41)是一个大项堆结构,该堆结构用二叉树表示,其高度(或层数)为___________(42)。(42)
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则___________(41)是一个大项堆结构,该堆结构用二叉树表示,其高度(或层数)为___________(42)。(41)
随机试题
A.清肝泻火,化痰开窍B.涤痰息风,开窍定痫C.平肝息风,安神定惊D.疏肝和胃,健脾化痰E.清热泻火,顺气豁痰(1997年第93,94题)风痰闭阻之痫的治法是()
官僚组织的行政管理意味着根据______进行统治,这是它所固有的特别合理的基本性质。
与可摘局部义齿稳定无关的是A.翘动B.弹跳C.摆动D.旋转E.移位
按其()不同,财务报表分为个别财务报表和合并财务报表。
证券公司定向发行债券的担保金额原则上不少于债券本息总额的()。
某居民企业2009年实际支出的工资、薪金总额为150万元,福利费本期发生30万元,拨缴的工会经费3万元,已经取得工会拨缴收据,实际发生职工教育经费4.50万元,该企业在计算2009年应纳税所得额时,应调整的应纳税所得额为()万元。
全面推进依法治国,必须坚持()有机统一,这是我国社会主义法治建设的一条基本经验。
面对新的时代和新的实践,马克思主义永葆生命力的关键在于要
在所有的关系数据库上的操作,是核心、是其他操作的前提的是
A.EdwardB.SpenoEdwardB.SpenowasExecutiveVicePresidentofCreditCardServiceCorporation("CCSC")from1982to1991.P
最新回复
(
0
)