首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: 当n=7时,在最好情况下需进行多少次比较?请说明理由。
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: 当n=7时,在最好情况下需进行多少次比较?请说明理由。
admin
2019-08-15
60
问题
对于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
学硕统考专业
相关试题推荐
卡诺莎事件
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中,正确的是____。
以下关于校验码的叙述中,正确的是()。Ⅰ校验码的码距必须大于2Ⅱ校验码的码距越大检错纠错能力越强Ⅲ增加奇偶校验位的位数可以提高奇偶校验的正确性Ⅳ采用奇偶校验可检测出一位数据错误的位置并加以纠正Ⅴ采用
假设有一个进程拥有两个线程(编号为0和1)需要去访问同一个共享资源,为了避免竞争状态的问题,必须实现一种互斥机制,使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码:intflag[2];/*flag数组,初始化为FALSE*/
随机试题
UniversityChallengeWhenitwenttoairnearly【A6】________yearsago.Whattopicsitcoversliterature,physics
下列作品中,既是传记,又属寓言,更兼说理的是()
[2013年第23题]在投资方案财务评价中,获利能力较差的方案是:
《乐记》和《系辞》中都有“天尊地卑”、“方以类聚,物以群分”等文句,由于《系辞》的文段写得比较自然,一气呵成,而《乐记》则显得勉强生硬,分散拖沓,所以,一定是《乐记》沿袭或引用了《系辞》的文句。以下哪项陈述如果为真,能最有力地削弱上述论证的结论?
现今,网上购书确实快捷、便利,而且有十分诱人的廉价活动,以致网上书店人气指数暴涨。相对于此,我们的实体书店,则面临经营困境。人力和租金的不断上涨,给书店经营造成巨大压力。但我们不能总拿自己的弱项跟网店比。论资本融资,网店一般都有深厚的资本背景,实体书店要实
【2010河南第116题】下列不属于具体行政行为的是()。
2月5日,甲与乙订立一份房屋买卖合同,约定乙购买甲的房屋一套(以下称0l号房),价格80万元。并约定,合同签订后一周内乙先付20万元,交付房屋后付30万元,办理过户登记后付30万元。2月8日,丙得知甲欲将该房屋出卖,表示愿意购买。甲告其已与乙签订合同的事实
【】是精确定义的一系列规则,它指出怎样从给定的输入信息经过有限步骤产生所求的输出信息。
C语占中,函数值类型的定义可以缺省,此时函数值的隐含类型是
【S1】【S4】
最新回复
(
0
)