首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于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
43
问题
对于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
学硕统考专业
相关试题推荐
简述希波战争过程及其意义。
首次提出“长期共存,互相监督”观念的是在文件()中。
简述布匿战争的过程。
战国时期提出“民为贵,社稷次之,君为轻”的思想家是()。
以下()协议完成了从网卡到IP地址的映射。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
实现一个经典的“读者一写者”算法时,若当前临界区中有读者访问,写者再来时必须在临界区外面等候,如果其后读者源源不断地到达,按策略他们均可以进入临界区,始终保持临界区中有读者访问,那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题,我们修改访问策略,
某网络拓扑如图A-3所示,路由器R1通过接口E1、E2分别连接局域网1、局域网2,通过接口LO连接路由器R2,并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1,R2的L0接口的IP地址是202.118.2.2,L1接
随机试题
下列情形中,成立共同犯罪的有()。
某企业常年生产需用的某部件以前一直从市场上采购。采购量在5000件以下时,单价为8元;达到或超过5000件时,单价为7元。如果追加投入12000元专属成本,就可以自行制造该部件,预计单位变动成本为5元。要求:用成本无差别点法为企业作出自制或外购
女患者,阴户肿痛,行动艰难,发热,口干纳少,大便秘结,小便黄少。舌红苔黄腻,脉沉数。妇科检查见右侧外阴红肿,触之较硬。首选:
APTT测定检测普通肝素抗凝治疗不恰当的是
3l岁女性,葡萄胎二次清宫后2月,阴道不规则流血持续存在,尿HCG(+)。如B超检查发现子宫肌层呈蜂窝样改变应考虑为
()是注射剂生产中使用量最多的一种溶剂。
根据我国现行《企业会计准则》,企业在资产负债表日或之前违反了长期借款协议,导致贷款人可随时要求清偿的债务,应当归类为()。
【2013年云南昭通.简答】影响小学生心理健康的因素是什么.
某市有关部门策划了一项“全市理想生活小区排列名次”的评选活动。方法足,选择10项指标,内容涉及小区硬件设施(住房质量、配套设施等)、环境卫生、绿化程度、治安状况、交通方便程度等。每项指标按实际质量或数量的高低,评以从1~10分之间的某一分值,然后求得这10
主板有许多分类方法,其中按芯片集的规格进行分类的是()。
最新回复
(
0
)