首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2019-08-15
72
问题
对一个具有7个记录的文件进行快速排序,请问:
在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,l 。
解析
转载请注明原文地址:https://kaotiyun.com/show/hKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
重庆谈判签署的文件是()。
清朝的()划定了中俄两国中段边界,是继续谈判确立两国相互关系的全面条约的基础
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
下列几种排序方法中,要求内存量最大的是()。
某阅览室晚间开放,第一个进入的读者开灯,最后一个离开的读者关灯。利用P、V原语操作实现读者进程。
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:若操作码0010B表示加法操作(助记符为ad
随机试题
简述1947年南京国民政府改组后与抗战期间国民政府的不同及其性质。
请简述文化环境研究的重要性。
患者,男,56岁。因外伤大出血,送至医院时已处于休克状态,检查发现右股动、静脉损伤出血,积极输血扩容后行右股动、静脉修补术,术程顺利,手术前后共输入同型血3000ml。术后第2天,患者自觉呼吸费力、呼吸促,给予高流量面罩吸氧,症状无缓解。体检肺部未发现明显
钢筋混凝土预制桩基础施工中,打桩时应注意观察的内容中不包括()。桩的入土深度的控制,对于承受轴向荷载的摩擦桩,以()。
在吸收直接投资中,最重要的出资方式是()。
(2008年考试真题)王某于2007年9月30日存入某商业银行一笔人民币款项,同年12月30日王某将该笔存款取出,应得利息收入100元,银行在支付王某利息时应代扣代缴的个人所得税税额为()元。
下列不宜用于喂养婴儿的奶制品是()。
信息系统的物理模型描述了信息系统的具体结构和物理实现方法,下列属于物理模型的是()。
Astimedevelops,therearemanylargechanginghappeninginpeople’slives.BeinglikeotherWestcountries,privatecarsbegin
明朝前期(theearlyMingDynasty),中国是世界上最发达的国家之一。1405年到1433年间,明政府七次派郑和率领大规模船队出使西洋(theWesternOcean)。郑和拜访了东南亚(SoutheastAsia)、南亚和东非等地
最新回复
(
0
)