首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
admin
2019-08-15
37
问题
对一个具有7个记录的文件进行快速排序,请问:
在最好情况下需进行多少次比较?说明理由,并给出相应实例。
选项
答案
在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一l,显然,第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各文件的长度均为1,此时排序结束。由于n=7,k=3,在最好情况下,第一遍经过6次,可找到一个基元是正中间的元素;第二遍分别对两个子文件(此时长度为3)进行排序,各需要2次,这样就可将整个文件排序完毕,从而知n=7的最好情况下需进行10次比较。例如:4,7,5,6,3,l,2。
解析
转载请注明原文地址:https://kaotiyun.com/show/QKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赵匡胤了解高级将领发动兵变夺取政权的危险,他注意分散军权。回答问题:建隆二年,赵匡胤采取了()的措施,收夺武将的兵权
《中国国民党改组宣言》发表的时间是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱,其基本理由是他们()
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法),分析其死锁的可能性并提出解决方案。Philosopheri:d0{wait(chopstick[i];wait(ch
浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示,且位数分别为5位和7位(均含2位符号位)。若有两个数x=27×29/32,Y=25×5/8,则用浮点加法计算x+Y的最终结果是____。
假设有一个进程拥有两个线程(编号为0和1)需要去访问同一个共享资源,为了避免竞争状态的问题,必须实现一种互斥机制,使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码:intflagL22;/*flag数组,初始化为FALSE*/
随机试题
人员沟通在“风暴期”中显得尤为重要,经常会面临“小团体”现象。关于小团体的描述,正确的是:________。
先报有较大虚头的价格,然后适时压低价格。这种报价术被称为()
男性,48岁,下肢静脉曲张10年,劳累后肢体肿胀,皮炎及溃疡经久不愈,首选的治疗是
普济消毒饮主治
A.麝香B.地龙C.蜈蚣D.石决明E.青黛能平喘利尿的中药是
建设项目竣工验收在正常情况下的验收范围包括()。
FIDIC的组织机构中,()负责指导秘书处的行政工作。
下列各项中,注册会计师应当在了解管理层如何识别是否需要作出会计估计时了解的有()。
品牌经济是品牌在市场竞争中充分发展的__________,是一国经济发展达到较高水平的重要标志。发展品牌经济的过程,就是通过培育品牌不断提升企业核心竞争力、__________增强国家经济实力的过程。因此,培育发展品牌和品牌经济是推动我国经济发展迈上更高台
DVDrentalkiosks(售货亭)fromRedboxandBlockbusterseemtobepoppinguponeverycornerthesedays,buthome-videomarketanalys
最新回复
(
0
)