首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: 当n=7时,在最好情况下需进行多少次比较?请说明理由。
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问: 当n=7时,在最好情况下需进行多少次比较?请说明理由。
admin
2019-08-15
32
问题
对于n个元素组成的线性表进行快速排序时,所需进行的比较次数与这n个元素的初始排序有关。问:
当n=7时,在最好情况下需进行多少次比较?请说明理由。
选项
答案
在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2k一1,那么第一遍划分得到两个长度均为[n/2]的子文件,第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3,k=2)进行排序,备需2次,共10次即可。
解析
转载请注明原文地址:https://jikaoti.com/ti/zMGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
书院制度,始于唐而盛于宋,根据所学知识。回答问题:南宋书院的复起,是由朱熹开始的。他重建白鹿洞书院,亲自到书院讲学,还亲手制定()
系统阐明社会主义初级阶段理论是在()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
在一个双链表中,在*p结点之前插入*q结点的操作是()。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
将两个长度为N的有序表归并到一个长度为2N的有序表,最少需要比较的次数是(),最多需要比较的次数是()。
现有一个长度为3000B的IP数据报,其IP头部的长度为20B,该IP数据报如在最大帧长度为1518B的以太网中进行传输,那么为了正确传输,需要将其拆分的数据报个数是()。
采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中,正确的是____。
测量控制系统中的数据采集任务把所采集的数据送一个单缓冲区,计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。
随机试题
不符合非胰岛素依赖型糖尿病的特点是
患者,女,25岁,劳力性呼吸困难3年,反复咯血,体检:心尖部可闻舒张期隆隆样杂音,P2亢进,双肺下野可闻及湿性啰音,最可能的诊断为
下列关于乙型肝炎的治疗哪项描述是错误的
displacementvaLlue
当一个应用程序窗口被最小化后,该应用程序将()。
在“文件”菜单中,有3个命令都是用于存储Excel文件的,他们是“保存”“另存为”“保存工作区”,分别适用于不同的工作环境。()
载重货车、客货两用汽车、拖拉机当年应缴纳车船税( )元。机动船当年应缴纳车船税( )元。
下列混合销售行为中,应纳营业税的是()。
进行债券投资,应考虑的风险有( )。
我国的社会主义精神文明建设以马列主义、毛泽东思想、邓小平理论为指导。()
最新回复
(
0
)