首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2018-08-12
70
问题
对一个具有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
学硕统考专业
相关试题推荐
首次提出“长期共存,互相监督”观念的是在文件()中。
简述北宋与辽的关系。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争,这一古老文件是()。
晚清时期清帝年号的正确排序是
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用的是()。
随机试题
蒋某为个体工商户,2010年5月12日,县卫生局以经营发霉变质食品为由处以蒋某罚款3000元,停业整顿3个月。蒋某不服,向市卫生局申请行政复议。市卫生局于同年7月5日作出维持停业整顿的行政决定,但将罚款数额改为1000元。对此,蒋某仍不服。根据上
设,则秩r(AB—A)等于()。
安装在易受震动场所的雨水管道使用()。
不属于我国资产评估准则体系中的执业准则的是()。
甲公司按10%计提盈余公积,2014~2016年有关投资业务如下:(1)甲公司2014年7月1日与A公司达成资产置换协议,甲公司以交易性金融资产和可供出售金融资产换入A公司对乙公司的股权投资,该资产交换具有商业实质且换入和换出资产的公允价值均能够可靠
某个人独资企业由王某以个人财产出资设立。该企业因经营不善被解散,其财产不足以清偿所欠债务。对尚未清偿的债务,根据个人独资企业法律制度的规定,下列处理方式中,正确的是()。
下列关于奥运会说法不正确的是()。
多洛雷斯呼声
NolongerdomostofEurope’sundergraduateswanttodirtytheirhandsproducingthingsorprovidingservicestocustomers.【R1】_
Whatisimportantwhen...?Producingenergy-savingequipment-Long-termbenefit-Productionefficiency--
最新回复
(
0
)