首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于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
35
问题
对于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
学硕统考专业
相关试题推荐
顺帝时,()学道于蜀地鹄鸣山中,以道书招致信徒,通道者出米五斗,有病则令自首其过。这就是五斗米道。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
达芬奇、米开朗基罗、拉斐尔称为“文艺复兴三杰",与启蒙思想家相比,他们
1941年~1942年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
北宋在统一南方割据势力的过程中特设(),把征南所得的财富统一存放,以作日后恢复幽燕之费。
经六朝时期的发展,南方形成了三个农业发达地区即()。
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次,其中访问Cache缺失(未命中)50次,则Cache的命中率是()。
随机试题
电力变压器上安装气体继电器的作用是什么?
系统的解释学美学形成于()
下列不属于会计报表认定的是()
简述货币市场的基本特征。
按照当事人分类,索赔不包括()。
计算机病毒是指:
资料显示,电视并不能集中人的注意力。电视观众中,40%的人同时在阅读,21%的人同时在做家务,13%的人在吃喝,12%的人在玩赏他物,10%在烹饪,9%在写作,8%在打电话。而网络用户中,55%的人在使用计算机时不做任何他事,只有6%的人同时在打电话,只有
Researcherssaytalkingtoyourself,outloud,ismorecommonthanmanyofusmightcaretoadmit.Psychologistscallit"selft
工程数据库管理上的3个技术难点是数据多样性、数据可变性和【】。
A、Hehashadaheartattackbecauseofsmoking.B、Hehasseriouslungdisease.C、Heiscoughingbecauseoftoomuchsmoking.D、H
最新回复
(
0
)