首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
堆排序是(54)类排序,堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
堆排序是(54)类排序,堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。
admin
2009-02-15
26
问题
堆排序是(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
甲、乙两人在同一时间就同样的发明创造提交了专利申请,专利局将分别向各申请人通报有关情况,并提出多种解决这一问题的办法,不可能采用(21)的办法。
中断响应时间是指(3)。
10个9.6kb/s的信道按时分多路复用在一条线路上传输,如果忽略控制开销,在同步TDM情况下,复用线路的带宽应该是(24);在统计TDM情况下,假定每个子信道只有30%的时间忙,复用线路的控制开销为10%,那么复用线路的带宽应该是(25)。
数据加密标准(DES)是一种分组密码,将明文分成大小(33)位的块进行加密,密钥长度为(34)位。
设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,那么采用二级索引结构搜索文件内容时,可寻址的文件最大长度为(40)。
与线路交换相比,分组交换最大的优点是(11),最大的缺点是(12)。设待传送数据总长度为L位分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个键路上的延迟时间为D秒,数据传输率为Bbit/s,线路交换和虚电路建立连接的时间都为
与线路交换相比,分组交换最大的优点是(11),最大的缺点是(12)。设待传送数据总长度为L位分组长度为P位,其中头部开销长度为H位,源节点到目的节点之间的链路数为h,每个键路上的延迟时间为D秒,数据传输率为Bbit/s,线路交换和虚电路建立连接的时间都为
在异步通信中,每个字符包含1位起始位,7位数据位,1位奇偶位和2位终止位,每秒传送100个字符,则有效数据速率为____________。
在异步通信中,每个字符包含1位起始位、7位数据位、1位奇偶校验位和2位终止位,若每秒钟传送100个字符,采用4相相位调制,则码元速率为(1),有效数据速率为(2)。(2008年上半年试题)(2)
随机试题
符合法定条件、标准的,申请人有依法取得行政许可的平等权利,行政机关不得歧视()
对鉴别是否肾小球源性血尿最有意义的是
选择产品定价的特点是()。
气浮过程的必要条件不包括()。
工程网络计划按工作持续时间的特点可划分为( )网络计划。
S有限责任公司系外商投资企业,确定的记账本位币为人民币。20×7年1月2日,S有限责任公司收到外商投入的外币资本400000欧元,当日的即期汇率为:1欧元=10元人民币。中外双方签订的投资合同中约定汇率为:1欧元=9.8元人民币。当月的平均汇率为1欧元=1
“超额贷款损失准备可计入部分”属于商业银行资本中的()。
简述音乐的审美特征
【H1】【H12】
A、TheinaccessibleInternet.B、Theservicequality.C、Theannualincome.D、Therailnetwork.B
最新回复
(
0
)