对一个具有7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。

admin2018-08-12 91

问题对一个具有7个记录的文件进行快速排序，请问：
(1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。

选项

答案 (1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1，显然，第一遍划分得到两个长度均为[n／2]的子文件。第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各文件的长度均为1，此时排序结束。由于n=7，k=3，在最好情况下，第一遍经过6次，可找到一个基元是正中间的元素；第二遍分别对两个子文件(此时长度为3)进行排序，各需要2次，这样就可将整个文件排序完毕，从而知n=7的最好情况下需进行10次比较。例如：4，7，5，6，3，1，2。 (2)在最坏情况下，若每次划分时用的基元，它的关键字值是当前记录中最大(或最小)，那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此，若初始排列的记录是按关键字递增或递减，而所得的结果必须为递减或递增排列，那么此时，快速排序就退化为与冒泡排序相似，而且时间复杂度为O(n²)，反而不快了。对于n=7的记录文件，显然最坏情况下的比较次数为21。例如：7，6，5，4，3，2，1。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/nuRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

对一个具有7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。

计算机408

学硕统考专业

1925年爆发的当时世界上罢工时间最长的一次斗争是()。

下列哪个文件标志着“文化大革命”的发起?()

简述北宋与辽的关系。

年鉴学派开创了总体史研究方法，其代表人物马克·布洛赫研究中世纪的代表作是()

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

符某，男，62岁。水肿不愈缠绵10余年，现症见全身水肿，腰以下甚，气短、腰冷痛，畏寒肢冷，面色灰滞，舌淡胖苔白，脉沉细无力。应治以（　　）。

A．渗透效率B．溶解速率C．胃排空速度D．解离度E．酸碱度生物药剂学分类系统根据药物溶解性和肠壁渗透性的不同组合将药物分为四类。阿替洛尔属于第Ⅲ类，是高水溶性、低渗透性的水溶性分子药物，其体内吸收取决于

中毒型菌痢临床症状中最严重的是

黑龙江是中国位置最北、纬度最高的省份。()

“服务至上”是导游处理问题的出发点，其关键在于时时刻刻关心游客。()

北宋的都城在今天的陕西西安。()

2，3，8，27，32，()，128

Accordingtothepassage,thepurposeofeffectivereadingwithhigherspeedismostlikelytohelpyou______.Whichofthefo

Somanypeopleusethecellphonesofrequentlyeveryday.But【C1】______littleiscertainaboutthehealtheffectsofitsuse.M

OneSaturday,MarkandJanedecidedtogotoahillneartheirvillage.Theymadesomefoodtotakealong【C1】______lunch.Thetw

对一个具有7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。

计算机408

学硕统考专业

1925年爆发的当时世界上罢工时间最长的一次斗争是()。

下列哪个文件标志着“文化大革命”的发起?()

简述北宋与辽的关系。

年鉴学派开创了总体史研究方法，其代表人物马克·布洛赫研究中世纪的代表作是()

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

符某，男，62岁。水肿不愈缠绵10余年，现症见全身水肿，腰以下甚，气短、腰冷痛，畏寒肢冷，面色灰滞，舌淡胖苔白，脉沉细无力。应治以（ ）。

A．渗透效率B．溶解速率C．胃排空速度D．解离度E．酸碱度生物药剂学分类系统根据药物溶解性和肠壁渗透性的不同组合将药物分为四类。阿替洛尔属于第Ⅲ类，是高水溶性、低渗透性的水溶性分子药物，其体内吸收取决于

中毒型菌痢临床症状中最严重的是

黑龙江是中国位置最北、纬度最高的省份。()

“服务至上”是导游处理问题的出发点，其关键在于时时刻刻关心游客。()

北宋的都城在今天的陕西西安。()

2，3，8，27，32，()，128

Accordingtothepassage,thepurposeofeffectivereadingwithhigherspeedismostlikelytohelpyou______.Whichofthefo

Somanypeopleusethecellphonesofrequentlyeveryday.But【C1】______littleiscertainaboutthehealtheffectsofitsuse.M

OneSaturday,MarkandJanedecidedtogotoahillneartheirvillage.Theymadesomefoodtotakealong【C1】______lunch.Thetw

符某，男，62岁。水肿不愈缠绵10余年，现症见全身水肿，腰以下甚，气短、腰冷痛，畏寒肢冷，面色灰滞，舌淡胖苔白，脉沉细无力。应治以（　　）。