首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。 A:待排序数组 p,r:数组元素下标,从p到r q:划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。 A:待排序数组 p,r:数组元素下标,从p到r q:划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素
admin
2010-01-15
56
问题
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。
A:待排序数组
p,r:数组元素下标,从p到r
q:划分的位置
x:枢轴元素
i:整型变量,用于描述数组下标。下标小于或等于i的元素的值,小于或等于枢轴元素的值
j:循环控制变量,表示数组元素下标
(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度(用 O记号)。最佳情况为(4),平均情况为(5),最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)
选项
答案
这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时,算法为最佳情况,此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n),得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时,即长度为n的数组划分后一个子数组为n-1,一个为0,算法为最坏情况,此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n),得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂,假设数组每次划分为9/10:1/10,此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n),得到时间复杂度为O(nlogn),因此在平均情况下快速排序仍然有较好的性能,时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时,可以认为数组已经有序,此时每次都划分为长度为n-1和0的两个子数组,属于最坏情况。
解析
转载请注明原文地址:https://kaotiyun.com/show/a0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在Windows系统中设置默认路由的作用是(68)。
以下关于信息安全的叙述,不正确的是______。A.SYN洪水攻击通过发送大量TCP连接请求以占满网络带宽,使其他用户无法正常连接服务B.缓冲区溢出攻击能通过修改函数返回地址并执行恶意代码,进而获得系统的控制权C.计算机病毒的主要特征包括破坏性、寄生
设有学生实体Students(学号,姓名,性别,年龄,家庭住址,家庭成员,关系,联系电话),其中“家庭住址”记录了邮编、省、市、街道信息;“家庭成员,关系,联系电话”分别记录了学生亲属的姓名、与学生的关系以及联系电话。学生实体Students中的“
在分层体系结构中,(41)实现与实体对象相关的业务逻辑。在基于Java,EE技术开发的软件系统中,常用(42)技术来实现该层。(42)
模块A、B和C都包含相同的5个语句,这些语句之间没有联系,为了避免重复,把这5个语句抽取出来组成一个模块D,则模块D的内聚类型为(39)内聚。以下关于该类内聚的叙述中,不正确的是(40)。(39)
软件测试的基本方法包括白盒测试和黑盒测试方法,以下关于二者之间关联的叙述,错误的是(61)。
以下测试内容中,属于系统测试的是()。①单元测试②集成测试③安全性测试④可靠性测试⑤兼容性测试⑥可用性测试
若某文件系统的目录结构如下图所示,假设用户要访问文件f1.java,且当前工作目录为Program,则该文件的全文件名为(24),其相对路径为(25)。 (25)
假设系统中有三类互斥资源R1、R2和R3,可用资源数分别为10、5和3。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,此时系统剩余的可用资源数分别为(22)。如果进程按(23)序列执行,那么系统
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
随机试题
计算机网络是计算机技术和_________相结合的产物。
关于色素痣发生恶变的征象,不正确的是
A.阿司米唑B.西替利嗪C.苯海拉明D.吡咯醇胺E.赛庚定无中枢作用的H1受体阻断药是
对无形资产进行评估时,()。
税务师对生产企业出口业务退(免)税申报进行审核时,认为正确的业务有()。
通过发行人营业网点、电子银行等自有渠道发行的大额存单,不可以办理提前支取和赎回。
2005年江山市的GDP总量是()亿元。2005年江山市的第三产业占其GDP总量的比重约为()。
以下关于按份共有关系的表述中正确的是( )。
Ofgreatestinteresttothoseconcernedwiththeenvironmentalaspectsofsolidwastemanagementistheissueof—andtheneedfo
Iappreciated______theopportunitytostudyabroadtwoyearsago.
最新回复
(
0
)