首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
admin
2019-01-16
49
问题
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问:
(1)当n=7时,在最好情况下需进行多少次比较?请说明理由。
(2)当n=7时,给出一个最好情况的初始排序的实例。
(3)当n=7时,在最坏情况下需进行多少次比较?请说明理由。
(4)当n=7时,给出一个最坏情况的初始排序的实例。
选项
答案
(1)在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k一1,那么第一遍划分得到两个长度均为[*91]的子文件,第二遍划分得到4个长度均为[*]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,后=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3,k=2)进行排序,各需2次,共10次即可。 (2)在最好情况下快速排序的原始序列实例:4,1,3,2,6,5,7。 (3)在最坏情况下,若每次用来划分的记录的关键字具有最大值(或最小值),那么只能得到左(或右) 子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为O(n
2
)。所以当n=7时,最坏情况下的比较次数为21次。 (4)在最坏情况下快速排序的初始序列实例:7,6,5,4,3,2,1,要求按递增排序。 提示:此题考查的知识点是快速排序的思想。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
解析
转载请注明原文地址:https://kaotiyun.com/show/7eRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
明治维新的主要内容不包括()。
1543年,发表了解剖学专著《人体结构》的是()。
试析第三次科学技术革命对人类社会和历史进程的影响。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
民初政党林立,其中进步党是由几个党派合并而成的,这其中不包括()。
我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是()。
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
1908年安庆新军起义是由()领导的。
下列各种情况中,应采用异步通信方式的是()。
下图是三个计算机局域网A,B和C,分别包含10台,8台和5台计算机,通过路由器互联,并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB公用一个C类IP地址
随机试题
询问该婴儿添加副食品情况及下一步打算时,下列哪项是不正确的
先在龙口建造浮桥或栈桥,由自卸汽车或其他运输工具运来抛投料,沿龙口前沿投抛的截流方法是()。
在发生违约时,下列对继续履行说法有误的是( )。
建筑安装工程费用中的措施项目费包括()。
我国消费税对不同应税消费品采用了不同的税率形式。下列应税消费品中,适用复合计税方法计征消费税的是()。
根据《票据法》的有关规定,关于涉外票据付款行为的法律适用,应适用()。
属于我国古代医学所说的“五脏”是指()。
人民警察应具备的心理素质,主要体现为()。
设f(x)的一个原凼数为F(x),且F(x)为方程xy’+y=ex的满足y(x)=1的解.(1)求F(x)关于x的幂级数;(2)求的和.
(2014下项管)(2007下项管)依据《中华人民共和国政府采购法》规定,在招标采购中,关于应予废标的规定,______是不成立的。
最新回复
(
0
)