首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
admin
2019-08-01
51
问题
对一个具有7个记录的文件进行快速排序,请问:
在最好情况下需进行多少次比较?说明理由,并给出相应实例。
选项
答案
在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1,显然,第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行后=log
2
(n+1)遍划分,各文件的长度均为1,此时排序结束。由于n=7,k=3,在最好情况下,第一遍经过6次,可找到一个基元是正中间的元素;第二遍分别对两个子文件(此时长度为3)进行排序,各需要2次,这样就可将整个文件排序完毕,从而知n=7的最好情况下需进行10次比较。例如:4,7,5,6,3,1,2。
解析
转载请注明原文地址:https://kaotiyun.com/show/i3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述日本大化改新的背景、内容和意义。
试述1946年政治协商会议的主要原因及意义。
武则天时期,为了管理天山以北的广大区域而设立了()。
《共产党宣言》指出:“资产阶级在历史上曾经起过非常革命的作用。”其中包括①“使生产工具,从而使生产关系,从而使社会关系不断地革命化”;②“开拓了世界市场,使一切国家的生产和消费都成为世界性的了”;③“使乡村从属于城市”;④“使未开化的和半开化的国家从属于文
西汉的主要赋税形式中,征收对象是儿童的是()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:随着商业的发展,唐朝在货币和金融方面有一些重要的进步,以下表述全面的是()
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
一台主机申请了一个到www.ab@C@edu.cn的连接,为了获取服务器的IP地址,首先要进行DNS查询,下图为本次查询的过程,请回答如下问题:(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
随机试题
在父进程创建一个子进程后,子进程主要继承了父进程哪些映像?
Theviolinewasaqueer______thingthathadtobehandledmostcarefully.
肝硬化腹水患者每日进水量限制在
我国的会计监督体系由()、政府监督和社会监督构成。
甲公司各年投资业务资料如下:资料一:2×14年6月6日,经股东大会同意,甲公司与乙公司的股东丙公司签订股权转让协议,有关资料如下:(1)以2×14年6月20日乙公司经评估后的净资产价值为基础,甲公司以5000万元的价格取得乙公司15%的股权。(2)
试分析《蜗牛和黄鹂鸟》的童趣特征。蜗牛和黄鹂鸟作词:陈弘文啊门啊前一棵葡萄树啊嫩啊嫩绿地刚发芽蜗牛背着那重重的壳呀一步一步地往上爬啊树啊上两只黄鹂鸟啊嘻啊嘻哈哈在笑它葡萄成熟还早地
( )是人民警察的象征与标志。
下述不属于供给与需求的理论假设的是()。
科学家洛伦兹提出“蝴蝶效应”理论,他说:“可预言:一只蝴蝶在巴西轻拍翅膀,可以导致一个月后德克萨斯州的一场龙卷风”,这种说法()
【S1】【S4】
最新回复
(
0
)