首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: (1)当n=7时,在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时,给出一个最好情况的初始排序的实例。 (3)当n=7时,在最坏
admin
2019-08-01
32
问题
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问:
(1)当n=7时,在最好情况下需进行多少次比较?请说明理由。
(2)当n=7时,给出一个最好情况的初始排序的实例。
(3)当n=7时,在最坏情况下需进行多少次比较?请说明理由。
(4)当n=7时,给出一个最坏情况的初始排序的实例。
选项
答案
(1)在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k一1,那么第一遍划分得到两个长度均为[n/2]的子文件,第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=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/9VCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
印度列国时代出现了16个国家,其中大部分是王国,只有少数的共和国。下列属于共和国的是()。
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
苏联“十四大”“十五大”后经济建设的核心内容是()
简述大化改新的内容和影响。
罗马共和国早期平民反对贵族斗争过程中,废除债务奴隶制的是()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
设某系统有两种磁盘配置:一种单磁盘结构,一种4磁盘组阵列结构。每个磁盘每磁道64个扇区,每扇区1024.字节,转速为10000rpm。找道时间为6ms。两种结构的磁盘控制器每次访问的延迟时间均为1ms。设I/O系统的性能只与磁盘和控制器有关,单磁
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
阅读《风波》中的最后一段,然后回答问题。现在的七斤,是七斤嫂和村人又都早给他相当的尊敬,相当的待遇了。到夏天,他们仍旧在自家门口的土场上吃饭;大家见了,都笑嘻嘻的招呼。九斤老太早已做过八十大寿,仍然不平而旦康健。六斤的双丫角,已经变成一支大辫子了;伊虽然
洋地黄中毒引起的非阵发性房室交界区性心动过速治疗有
心痛定必需氨基酸和α-酮酸合剂
甲公司对乙公司负有交付葡萄酒的合同义务。丙公司和乙公司约定,由丙公司代甲公司履行,甲公司对此全不知情。下列哪一表述是正确的?(2012年卷三第12题)
周某与妻子庞某发生争执,周某一记耳光导致庞某右耳失聪。庞某起诉周某赔偿医药费1000元、精神损害赔偿费2000元,但未提出离婚请求。下列哪一选项是正确的?()
厚大体积普通混凝土施工,不宜使用()水泥。
背景材料:某集团在东北新建后勤综合楼工程,局部1层地下室、筏板基础,地上4层,框架结构。地下室筏板及外墙混凝土均为C30P6,室内防水采用聚氨酯防水涂料,地下防水及屋面防水均采用SBS卷材,地下室防水设计采用外防外贴法,屋面防水等级为Ⅱ级。屋面防水层下设
根据合同法及相关规定,下列说法哪些是正确?
调价的方向定位为消费者埋单,公众不买账怎么办?据一项网络调查显示,62.4%的网友表示“以后会考虑少打车”。客源减少,的哥收入增加就有了很大的不确定性。如果能提高收入,的哥在打车高峰时段出车率低的情况确实能得到缓解,但这是建立在打车人群总量不变的前提下。就
【说明】假设你是公司的财务经理,写信向银行咨询业务。【内容】1.公司正在寻找一家服务好,收费合理的银行;2.公司目前有260名雇员、2800万美元的年销售额;3.请对方寄来简介材料和银行服务价目表;4.评估不同银行的文字资料后,会开户;5
最新回复
(
0
)