首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
admin
2019-08-15
53
问题
对一个具有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://www.kaotiyun.com/show/QKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
为了顺利开展武装起义的准备工作,在彼得格勒苏维埃中成立了()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。
随机试题
简述阿昔洛韦的药理作用及临床应用。
在多效蒸发的流程中,并流加料的优点是各效的压力依次降低,溶液可以自动地从前一效流入后一效,不需用泵输送。()
患者男性,58岁。高血压10余年,间歇发作胸闷、胸痛2年,医生确诊为原发性高血压、冠心病。此次上厕所后,突然出现胸闷、气短,咳粉红色泡沫痰。查体:端坐体位,心率1lO次/分,双肺可闻及水泡音,双下肢无水肿。该患者目前最可能的诊断是
与病例对照研究相比,队列研究的主要优点是
A.士的宁B.林可霉素C.利福平D.碳酸钙E.红霉素不宜与含有机酸成分的中药,如乌梅、山茱萸同服的是()。
关于毒性药品的管理,正确的是()
时间加权收益率的计算公式的前提假定是()。
下列哪一项不属于直接融资区别于间接融资的情形?()
软件维护工作越来越受到重视,因为它的花费常常要占软件生存周期全部花费的(83)%左右。其工作内容为(84),为了减少维护工作的困难;可以考虑采取的措施是(85)。而软件的可维护性包含(86)。所谓维护管理主要指的是(87)等。
SomehowCaliforniaisalwaysatthecuttingedge,beitintheflower-powerdaysofthe1960sorthedotcomboomofthe1990s.A
最新回复
(
0
)