首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
堆排序是(54)类排序,堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
堆排序是(54)类排序,堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
admin
2009-02-15
20
问题
堆排序是(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
虚拟存储管理系统的基础是程序的(23)理论,这个理论的基本含义是指程序执行时往往会不均匀地访问主存储器单元。根据这个理论,Denning提出了工作集理论。工作集是进程运行时被频繁访问的页面集合。在进程运行时,如果它的工作集页面都在(24),内,能够使该进程
内存按字节编址,地址从A4000H到CBFFFH,共有(1)字节。若用存储容量为 32K×8bit的存储器芯片构成该内存,至少需要(2)片。
中断响应时间是指(3)。
10个9.6kb/s的信道按时分多路复用在一条线路上传输,如果忽略控制开销,在同步TDM情况下,复用线路的带宽应该是(24);在统计TDM情况下,假定每个子信道只有30%的时间忙,复用线路的控制开销为10%,那么复用线路的带宽应该是(25)。
在系统转换的过程中,旧系统和新系统并行工作一段时间,再由新系统代替旧系统的策略称为(19);在新系统全部正式运行前,一部分一部分地代替旧系统的策略称为(20)。
若每一条指令都可以分解为取指、分析和执行三步。已知取指时间t取指=5Δt,分析时间t分析=2Δt,执行时间t执行=5Δt。如果按顺序方式从头到尾执行完500条指令需(4)Δt。如果按照[执行]k、[分析]k+1、[取指]k+2重叠的流水线方式执行指令,从头
物理层的电气特性有多种标准,其中非平衡型标准规定(65),电缆最大长度为(66)m。新的非平衡标准规定(67),距离为10m时的最高数据率为(68)。在多种标准中,数据率最高的是新的平衡型标准,近距离传输其最高数据率可达(69)。
两个公司希望通过Internet传输大量敏感数据,从信息源到目的地之间的传输数据以密文形式出现,而且不希望由于在传输结点使用特殊的安全单元而增加开支,最合适的加密方式是(),使用会话密钥算法效率最高的是()。
收到数据报时,如果本结点是路由结点,则需要(51)。
随机试题
行政给付的内容是赋予被帮助人:()
A、Themajorityofdriversprefertodriveandparkthemselves.B、Humandriversbecomeeasilydistractedortiredwhiledriving.
计算机屏幕显示“Harddiskfailure”,表示()。
《公路桥涵地基与基础设计规范》(JTG3363—2019)将桥涵地基岩土分为()。
某企业以在保险公司存款的利息充抵保险费用的方式向保险公司购买保险。2005年7月初,企业在保险公司的存款为400万元;月末,企业在保险公司的存款为200万元。假设人民银行公布的1年期存款利率为3%,保险公司在7月份应纳的营业税税额为()。
贷款分类需要考虑的因素包括()。
()不属于事前风险控制手段。
下列各项中,注册会计师在确定某项重大错报风险是否为特别风险时,通常无须考虑的是()。
系统方法论是项目评估方法论的理论基石。系统方法论的基本原则不包括()。
Sleepwalkingisadisordercharacterizedbywalkingorotheractivitiesapersonengagedinwhile【C1】______stillasleep.Itis
最新回复
(
0
)