首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: 当n=7时,在最好情况下需进行多少次比较?请说明理由。
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: 当n=7时,在最好情况下需进行多少次比较?请说明理由。
admin
2019-08-15
83
问题
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问:
当n=7时,在最好情况下需进行多少次比较?请说明理由。
选项
答案
在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k一1,那么第一遍划分得到两个长度均为[n/2]的子文件,第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3,k=2)进行排序,备需2次,共10次即可。
解析
转载请注明原文地址:https://kaotiyun.com/show/tKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:对于二里头文化的发现的意义,下列选项表述最准确的是()
“人身保护法”
水门事件
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
随机试题
胰腺CT的扫描范围为
《建设项目竣工环境保护验收技术规范一生态影响类》规定了生态影响类建设项目竣工环境保护验收调查()。
项目准备阶段的咨询包括()
某市建筑集团公司承担一栋20层智能化办公楼工程的施工总承包任务,层高3.3m,其中智能化安装工程分包给某科技公司施工。在工程主体结构施工至第18层、填充墙施工至第8层时,该集团公司对项目经理部组织了一次工程质量、安全生产检查。部分检查情况如下:(1)现场
在会计职业道德规范中,坚持准则的基本要求是熟悉准则、遵循准则和坚持准则。()
在计算外商投资企业和外国企业所得税时,下列说法正确的是( )。
基督教起源于公元1世纪亚洲西部巴勒斯坦地区的犹太人中间。()
行政性督导工作中督导者扮演的角色有()
一般认为,剑乳齿象是从北美迁入南美洲的。剑乳齿象的显著特征是具有较真的长剑形门齿,颚骨较短,臼齿的齿冠隆起,齿板数目为7~8个,并呈乳状凸起,剑乳齿象因此得名。剑乳齿象的牙齿结构比较复杂,这表明它能吃草。在南美洲的许多地方都有证据显示史前人类捕捉过剑乳齿象
CompletethesentencesbelowwithwordstakenfromReadingPassage1.UseNOMORETHANTHREEWORDSforeachanswer.Writeyoura
最新回复
(
0
)