首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2017-01-04
76
问题
对一个具有7个记录的文件进行快速排序,请问:
(1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
(1)在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1,显然,第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各文件的长度均为l,此时排序结束。由于n=7,k=3,在最好情况下,第一遍经过6次,可找到一个基元是正中间的元素;第二遍分别对两个子文件(此时长度为3)进行排序,各需要2次,这样就可将整个文件排序完毕,从而知n=7的最好情况下需进行10次比较。例如:4,7,5,6,3,1,2。 (2)在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,1.
解析
转载请注明原文地址:https://kaotiyun.com/show/6QRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
新王朝时期出现了什么类型的墓?()
下列对春秋时期各国称霸的顺序描述错误的选项是()
1988年起,苏联民族矛盾激化,民族分离运动加剧,第二次较大规模的民族冲突是()。
在下列哪个条约中,最先出现了片面最惠国待遇?()
红山文化的代表性墓葬形式为()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
某32位计算机系统采用段页式虚拟存储管理,现有一个进程被分成5段,其段号和段长见下表,段内分页,页表见下,存放在内存中,每页的长度为4096B。进程运行到某一个指令,其地址为(2,3,010),当前CPU的寄存器和地址加法器的状态如图所示,当上述指令执行时
下图所示的CPU逻辑框图中,有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位),数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout/)控制命令,但图中未标出。
利用栈求表达式的值时,设立运算数栈OPND。假设OPND只有两个存储单元,在下列表达式中,不发生溢出的是()。
随机试题
英国以培养高级政界人士而著称的大学是()。
牙周感染对全身疾病的影响可能的机制是
A.<1.0×109/LB.<0.5×109/LC.<0.1×109/LD.>0.5×109/LE.>1.0×109/L渗出液白细胞一般
某男性患者,25岁。下唇皮肤潮红、硬结。镜下见血管周围有上皮样细胞、淋巴细胞及浆细胞,呈结节样聚集,有时结节内有多核巨细胞,血管周围淋巴细胞或(和)浆细胞浸润呈灶状,固有层水肿,可见较多肥大细胞。病理诊断应为()
患儿男,5岁。体重12kg,身高98cm,经常烦躁不安,皮肤干燥苍白,腹部皮下脂肪0.3cm,肌肉松弛。护士判断该患儿是
控制网外业观察阶段,采用()记录方式,不仅可以大大提高作业效率,更主要的是可以减少许多人为的错误。
投资项目现金流量分析指标中,内部收益率指标的经济含义是项目对()。
如果发现发言者的讲话内容与会议主题无关,会议主持人应()。
下列有关文学常识的表述,错误的一项是()。
A、Theprofessordidn’tshowup.B、Toomanystudentsdidn’tshowup.C、Theprofessorwasill.D、Theclassthoughtthedemonstrati
最新回复
(
0
)