首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2019-08-15
40
问题
对一个具有7个记录的文件进行快速排序,请问:
在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,l 。
解析
转载请注明原文地址:https://kaotiyun.com/show/hKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述,不正确的是()
中国共产党在大革命失败后,根据中国革命的新特点,明确了“工农武装割据”的思想,其核心内容不包括()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FRl中,且x=一8.25,则FRl的内容是____。
浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示,且位数分别为5位和7位(均含2位符号位)。若有两个数x=27×29/32,Y=25×5/8,则用浮点加法计算x+Y的最终结果是____。
随机试题
战略业务单位是企业值得为其专门制定一种经营战略的()业务单位。
符合现行《中国药典》规定的检查热原的方法有
患儿,7岁。水肿1周,体检:全身明显水肿,血压120/80mmHg(15/10.6kPa),尿常规;蛋白(+++),红细胞10~15个/高倍视野,血白蛋白22g/L,胆固醇7.8mmol/L,诊断为肾病综合征,给予泼尼松1.5~2mg/(kg•
高热病人的护理,下列措施哪项不妥
双级制冷循环中的高、低压级制冷剂吸气体积量()。
政府投资的水利、电力、铁路等项目基本属于()。
甲公司生产A产品,本月成本资料如下:A产品本月完工3200件,月末在产品800件。要求:根据上述资料,分析回答下列问题。若原材料随加工程度逐步投入,月末在产品投料程度为50%,采用在产品按所耗直接材料费用计价法计算,完工产
需求拉动的通货膨胀是由于()引起的通货膨胀。
A、B、C三个水桶的总容积是1440升。如果A、B两桶装满水,C桶是空的,若将A桶水的全部和B桶水的1/5,或将B桶水的全部和A桶水的1/3倒入C桶,C桶都恰好装满。C桶的容积是多少升?
Mostofyouwouldprobablysaythatwhatmakesyoutrulyhappyisyourfamilyandtheloveyoushareinyourrelationships,and
最新回复
(
0
)