首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问： 当n=7时，在最好情况下需进行多少次比较?请说明理由。
对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问： 当n=7时，在最好情况下需进行多少次比较?请说明理由。
admin
2019-08-15
79
问题
对于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://www.kaotiyun.com/show/tKCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《中国国民党改组宣言》发表的时间是()。
洋务运动时期，首批赴欧海军留学生派出的时间是()。
二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()
在4×100米接力赛中，4个运动员之间存在如下关系：运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交棒给运动员3；运动员3也只有接到运动员2传来的接力棒后才能往前跑，他跑完100米
下列各种情况中，应采用异步通信方式的是()。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50
指令系统字长16位，每个地址码为6位，采用扩展操作码的方式，试设计14条二地址指令，100条一地址指令，100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图，其中只给出了二地址指令的译码逻辑，试补全一地址指令和零地址指令的
有两部计算机M1和M2，指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类，在M1上执行分别需4、6和8个周期；在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行，其中A、B和C三类指令依次占30％、50
下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控
快速排序算法中，如何选取一个界值(又称为轴元素)，影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
随机试题
触电的危害程度与________、通过人体的电流大小、电流通过人体的部位、电流通过时间的长短等都有直接关系。
下列关于链接表的说法中，错误的是_______。
对图示体系的“几何组成分析”，正确的是()。
下列关于固定资产折旧的说法正确的有()。
一般均衡只有在完全竞争的市场经济条件下才有可能实现。()[2007年真题]
根据《票据法》的规定，背书人在汇票上作禁止背书，其后手再背书转让的，将产生的法律后果是()。
根据我国《宪法》的规定，下列有关公民基本权利的宪法保护的表述，哪一个是正确的?()
2007年1-9月浙江省累计出口()以下的三种说法中，正确的一共有()Ⅰ．2008年1-9月服装、皮革、家具、通信设备行业增加值与去年同期相比下降了Ⅱ．2007年1-9月美资实际到位少于3.4亿美元Ⅲ．2008年
在我国社会主义法律的运行环节中，把法定的权利和义务转化为现实的权利和义务，把文本上的法律转化为现实中的法律的法律运行环节有
A、Theyarethesameperson.B、Theyarefriendsofthespeakers.C、Theyarepsychologyprofessors.D、Theyarefictionalcharacter
最新回复
(
0
)
