首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于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
28
问题
对于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://jikaoti.com/ti/HLGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述1929~1933年经济危机的根源和影响。
严复翻译的《天演论》一书的出版时间是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,分别分在卫、鲁、唐、燕的贵族是()
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下: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,B,C,D,E,F)中的字母组成,这6个字母在正文中出现的次数分别为{12,18,26,6,4,34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成,试计算按哈夫曼编码压缩存储这段正文共需多少个字
给定页面请求序列RS=cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
主机H通过快速以太网连接Internet,IP地址为192.168.0.8,服务器S的lP地址为211.68.71.80。H与S使用TCP通信时,在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。题47一a表中的IP分组中,哪几个是由H
随机试题
关于雷公藤,以下哪项叙述不正确
灭菌后物品存放架或柜的排放正确的是
既能补肝肾,又能行血脉,有补而不滞优点的药物是
A.骨牵引B.皮牵引C.手法复位及石膏外固定D.介入疗法(髂内动脉造影及栓塞)E.骨盆兜悬吊牵引法髋臼骨折合并髋关节中心性脱位者,应采用何种治疗
一天夜晚,甲开车逆行迫使骑车人乙为躲避甲向右拐,跌人修路挖的坑里(负责修路的施工单位对该坑未设置保护措施),造成车毁人伤。则下列关于如何承担乙的损失的表述正确的是:()
根据《水工混凝土施工规范》SDJ207—82,下列关于钢筋材质和混凝土浇筑的说法错误的是()。
存储信息要方便利用,而方便利用的关键是要()。
设f(x)满足讨论f(x)在(一∞,+∞)是否存在最大值或最小值,若存在则求出;
设f(x)在[0,1]上连续,在(0,1)内可导,且∫01f(t)dt=0证明:存在ξ∈(0,1),使得f(ξ)=∫0ξf(t)dt.
Everyone【21】______ofthePresidentoftheUS【22】______themostpowerfulmanin【23】______Butwhentherepresentatives
最新回复
(
0
)