首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏
admin
2019-07-12
34
问题
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)(65)。
(65)
选项
A、Θ(n)
B、Θ(lgn)
C、Θ(nlgn)
D、Θ(n
2
)
答案
A
解析
本题考查算法设计与分析的相关知识。中位数的含义:将一组数据按照由小到大(或由大到小)的顺序排列,如果数据的个数是奇数,则处于中间位置的数就是这组数据的中位数;如果数据的个数是偶数,则中间两个数据的平均数就是这组数据的中位数。根据题干的描述,选择的基准元素将数组分得越均匀越好,因此中位数是最佳选择。对于该问题,若每次都是选择中位数作为基准元素,则时间复杂度的递归式为:
T(n)=T(n/2)+cn
求解该递归式,得到T(n)=Θ(n)。
转载请注明原文地址:https://jikaoti.com/ti/dOG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和C++代码。【说明】传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)和Closing(正在关闭)五种状态。触发传输门状态转换的事件有click
根据问题描述,补充联系及其类型,完善实体联系图2-1。(联系及其类型的书写格式参照教练与球队之间的联系描述,联系名称也可使用联系1、联系2、……)如果考虑记录一些特别资深的热心球迷的情况,每个热心球迷可能支持多个球队。热心球迷包括:姓名、住址和喜欢的俱
(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]=nv[i-1][j](3)j=j-p[i]问题1中伪代码的时间复杂度为(6)(用O符号表示)。
根据问题描述,填写上图中(1)~(3)处联系的类型。联系类型分为一对一、一对多和多对多三种,分别使用1:1,1:n或1:*,m:n或*:*表示。补充上图中的联系并指明其联系类型。
阅读下列程序说明,将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】对于一个公司的雇员来说,无非有3种:普通雇员、管理人员和主管。这些雇员有共同的数据:名字、每小时的工资,也有一些共同的操作:数据成员初始化、读雇员的数据成员及计算雇员
阅读下列函数说明和C代码,回答下面问题。[说明]冒泡排序算法的基本思想是:对于无序序列(假设扫描方向为从前向后,进行升序排列),两两比较相邻数据,若反序则交换,直到没有反序为止。一般情况下,整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作,冒泡排序
阅读下列函数说明和C代码,应填入(n)处。[说明]假设设A和B均为顺序表,A’和B’分别为A和B中除去最大共同前缀后的子表(例如,A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),则两者中最大的共同前缀为(x,y,y
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。A:待排序数组p,r:数组元素下标,从p到rq:划分的位置x:枢轴元素i:整型变量,用于描述数组下标。下标小于或等于i的元素
计算机中常用的一种检错码是CRC,即(4)码。在进行编码过程中要使用(5)运算。假设使用的生成多项式是C(x)=x4+x3+x+1。原始报文为11001010101,则编码后的报文为(6)。CRC码(7)的说法是正确的。在无线电通信中采用7中取3定比码,它
随机试题
简述公共政策监控的主要功能。
下列属于我国法的渊源的是
低分化肿瘤的特点是()
A.WhendoyouneeditB.DoyouhaveanyavailableC.WhatdoyoumeanD.MayIcomeovertomorrowtotakealook
女性,48岁,5年前患右上肺结核,痰菌阳性,经异烟肼、链霉素和乙胺丁醇治疗6个月,痰菌转阴,病灶明显吸收,自行停药,未再随访。近1个月来感乏力,2天前起咳嗽,痰中带血就诊。X线胸片示右上肺大片密影,边缘不清,密度不均,高密度病灶部分隐约见有钙化。侧位病变位
骨巨细胞瘤的好发年龄是
具有悬浮状、堆积状的可燃粉尘或可燃纤维,虽不能形成爆炸混合物,但在数量和配置上能引起火灾危险的环境,照明灯具应选用()。
注册会计师应当针对评估的认定层次重大错报风险设计和实施进一步审计程序,包括审计程序的性质、时间和范围。进一步审计程序的目的包括通过实施控制测试以确定内部控制运行的有效性,通过实施实质性程序以发现认定层次的重大错报。进一步控制测试审计程序的类型不包括( )
TheMuseumofContemporary(当代的)Art(MOCA)hasstartedanewseriesofprograms,knownas“ArtMakesGoodBusiness.“Itisdesigned
Manyofthemostdamagingandlifethreateningtypesofweather--torrentialrains,severethunderstorms,andtornadoes--beginqu
最新回复
(
0
)