首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2018-08-12
93
问题
对一个具有7个记录的文件进行快速排序,请问:
(1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
(1)在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1,显然,第一遍划分得到两个长度均为[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,1,2。 (2)在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,1。
解析
转载请注明原文地址:https://kaotiyun.com/show/nuRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。
戈尔巴乔夫上台后,在和平共处五项原则基础上,推动苏中关系正常化,这一做法主要表明了()。
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
下列不属于延安整风运动的文件是()。
印加人记载事物使用的方法是()。
阅读史料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合
下列哪两个国家是第二次工业革命的发源地和“中心”?
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
高度为7的AVL树最少有()个结点。
随机试题
电路如图4—6所示,逻辑与非门要实现F=,则C端应接_________。
论述区域经济一体化的六种基本模式。
小儿发病率和死亡率最高是哪一期
根据国务院《建设工程质量管理条例》,下列有关建设工程的最低保修期限的规定,正确的是()。
施工中材料的消耗分为必需消耗的材料和损失的材料。在确定材料定额量时,必需消耗的材料包括()。
近代教育与古代教育相比较,出现了哪些变化?
与电子政务相关的行为主体主要有三个,即(),政府的业务活动也主要围绕着这三个行为主体展开。
Linux是目前较为流行的网络操作系统,如同Unix操作系统一样,它也可以通过手工编辑配置文件达到对系统进行配置的目的。在Linux网络配置文件中的几个较为重要的配置文件如下:(56)用于存放本机主机名以及经常访问IP地址的主机名,在对IP地址进行域名
A、Shewantstoliveinthesuburbs.B、Sheisoffendedbyhernaughtychildren.C、Shedisagreeswithfather.D、Sheturnsadeafe
Sandy’sStoryA)Sandy,apoliteandfriendlyforty-year-oldwomanwithasoftSouthernaccent,lovescatsandfrequentedthene
最新回复
(
0
)