首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
admin
2009-02-15
39
问题
堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
选项
A、O(n
2
)和O(1)
B、O(nlog
2
n)和O(1)
C、O(nlog
2
n)和O(n)
D、O(n
2
)和O(1)
答案
B
解析
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆排序来源于一种称为比赛树的排序方法。用比赛树进行排序的方法是：先对n个结点的键值进行两两比较，再对其中n/2个较大的键值之间作两两比较，依此类推，直至选出键值最大的结点。这个过程可用一棵有2n-1个结点的丰满二叉树来表示，二叉树的叶子结点是待排序的结点序列，二叉树的非叶子结点是层层比较产生的结点。除第一个最大者需比较n-1次外，选其他任一结点都只需从叶结点到根结点路径上那些结点的比较，其比较次数与二叉树的高度相对应，比较次数为O(log
2
n)。总比较次数为O(nlog
2
n)。
堆排序的过程为：(假设是大顶堆)初始时调整n个结点的存储顺序，使之成为一个堆，这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换，并对少了一个结点后的n-1结点重新作调整，使之再次成为堆。这样，在根结点得到结点序列键值次最大者。再次将堆的根结点与堆的最后一个结点交换，并重新使又少了一个结点的序列调整成为堆。依此类推，直至只有两个结点的堆，并对它们作交换，最后得到有序的n个结点序列。所以堆排序的思想是：选择最大的结点与最后一个结点交换，然后选择次最大结点与倒数第二个结点交换，…，所以堆排序是选择类排序，它只需要1个附加的存储空间。
转载请注明原文地址:https://kaotiyun.com/show/5TxZ777K
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
码是一些码字组成的集合。1对码字之间的海明距离是(16)，1个码的海明距离是所有不同码字的海明距离的(17)。如果要检查出d位错，那么码的海明距离是(18)。如果信息长度为5位，要求纠正1位错，按照海明编码，需要增加的校验位是(19)位。以太网中使用的校验
甲、乙两人在同一时间就同样的发明创造提交了专利申请，专利局将分别向各申请人通报有关情况，并提出多种解决这一问题的办法，不可能采用(21)的办法。
中断响应时间是指(3)。
在系统转换的过程中，旧系统和新系统并行工作一段时间，再由新系统代替旧系统的策略称为(19)；在新系统全部正式运行前，一部分一部分地代替旧系统的策略称为(20)。
若每一条指令都可以分解为取指、分析和执行三步。已知取指时间t取指=5Δt，分析时间t分析=2Δt，执行时间t执行=5Δt。如果按顺序方式从头到尾执行完500条指令需(4)Δt。如果按照[执行]k、[分析]k+1、[取指]k+2重叠的流水线方式执行指令，从头
在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位，若每秒钟传送100个字符，采用4相相位调制，则码元速率为(16)，有效数据速率为(17)。
某幅图像具有640×480个像素点，若每个像素具有8位的颜色深度，经5:1压缩后其图像数据需占用的存储空间为(10)字节。
物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。
在局域网标准中，(28)与FDDI的MAC帧格式较为相似。(29)介质访问控制方法对最短帧长度有要求，(30)对传输线路最短长度有要求。长10km，16Mbit/s，100个站点的令牌环，每个站点引入1位延迟位，信号传播速度位200m/us，则该环上1位延
随机试题
谈谈四级语法单位的关系。
电力场效应晶体管MOSFET()现象。
设二元函数z=ln(x2+y)，则=______．
挖孔桩基础施工时，若发现桩间距比较大、地层紧密，不需要爆破时，可以采用()。
用市场法进行资产评估时，应当参照相同或者类似的()评定重估价值。
收入、支出、费用、成本都是计算的判断单位经营成果及其盈亏状况的主要依据。（）
下面哪个不是数据挖掘的常用的方法?
下列循环执行的次数为()。inty=2，x=4；while(--x!=x/y){}
按电子计算机传统的分代方法,第一代至第四代计算机依次是（）。
A、Itcarriesaboutonefifthoftheworld’sfreshwater.B、Ithasnumeroushumansettlementsalongitsbanks.C、Itissecondon
最新回复
(
0
)
