首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
堆排序是(54)类排序,堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
堆排序是(54)类排序,堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
admin
2009-02-15
58
问题
堆排序是(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
ATM网络的协议数据单元称为(21)。ATM适配层分为2个子层,这2个子层是(22)子层。(23)是对应于A类业务的ATM适配层,它提供的业务特点是(24)。如果要传送IP数据报,则需要(25)业务的支持。
虚拟存储管理系统的基础是程序的(23)理论,这个理论的基本含义是指程序执行时往往会不均匀地访问主存储器单元。根据这个理论,Denning提出了工作集理论。工作集是进程运行时被频繁访问的页面集合。在进程运行时,如果它的工作集页面都在(24),内,能够使该进程
内存按字节编址,地址从A4000H到CBFFFH,共有(1)字节。若用存储容量为 32K×8bit的存储器芯片构成该内存,至少需要(2)片。
布线实施后需要进行测试,在测试线路的主要指标电,(23)是指一对线对相邻的另一对线通过电磁感应所产生的偶合信号。(24)是由于集肤效应、绝缘损耗、阻抗不匹配、连接电阻等因素,造成信号沿链路传输时的损失。
在异步通信中,每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位,若每秒钟传送100个字符,采用4相相位调制,则码元速率为(16),有效数据速率为(17)。
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
文件系统采用多重索引结构搜索文件内容。设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,那么三级索引时可寻址的文件最大长度为(3)。
在异步通信中,每个字符包含1位起始位、7位数据位、1位奇偶校验位和2位终止位,若每秒钟传送100个字符,采用4相相位调制,则码元速率为(1),有效数据速率为(2)。(2008年上半年试题)(2)
随机试题
问题流主要关注于问题的()
烟花爆竹安全生产措施主要包括制造过程措施和生产过程措施两类。下列防止烟花爆竹火灾爆炸的安全措施中,属于生产过程措施的有()。
A.无症状性溃疡B.幽门管溃疡C.复合性溃疡D.球后溃疡夜间痛和背部放射痛显著的是
A.司帕沙星B.金刚烷胺C.利福平D.阿昔洛韦E.磺胺嘧啶极易与金属离子形成螯合物的药物是
在下列医务人员的行为中,不符合有利原则的是
在《合同法》关于预期违约责任制度的规定中,如果当事人一方()不履行合同义务的,对方可以在履行期限届满之前,请求其承担违约责任。
在双代号或单代号网络计划中,工作的最早开始时间应为其所有紧前工作()。
钢绞线质量评定方法中,每批从()做拉力试验,包括整根钢绞线的最大负荷、屈服负荷、伸长率。
简述判断声源方向的主要线索。
①そのようにして読んでいくと、作者の心が自分にはっきりわかってきて、しまいには自分も作者と同じ心になって読めるようになる。そうなれば、もう立派な朗読だ。こういう朗読は、文章を読んでいるというより、みんなに話しかけているように聞き取れるものだ。②朗
最新回复
(
0
)