关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中，最多做多少次数据比

admin2019-08-01 85

问题关于堆的一些问题：
(1)堆的存储表示是顺序的，还是链接的?
(2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

选项

答案(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：由于第i层上的结点数至多是2^i-1，以它为根的二叉树的深度为h一i+1，则调用[n／2]次筛选算法时总共进行的关键字比较次数不超过下式之值： [*] 提示：此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K₁，K₂，…，K_n，当且仅当该序列满足如下性质(简称为堆性质)： (1)k_i≤K_2i且k_i≤k_2i+1或 (2)k_i≥K_2i且k_i≥k_2i+1(1≤i≤n)。k_i相当于二叉树的非叶结点，k_2i则是左孩子，k_2i+1是右孩子。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/S3Ci777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

对20世纪20年代德国经济复兴的原因表述不准确的一项是()。

导致东欧国家和苏联发生剧变的根本原因是()。

胡适与李大钊“问题与主义”论战主要的阵地是()。

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。(1)原码定点小数；(2)补码定点小数；(3)反码定点小数；(4)IEEE754标准短

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

UPS电源故障如何判断?

Keepondoingwhateveryouweredoing.Ididn’tmean______you.

()不属于债券筹资的优点。

负责人就来文如何办理对有关承办部门和承办人员提出批示性意见的活动是收文处理中的()。

要折叠一批纸飞机，若甲单独折叠要半个小时完成，乙单独折叠需要45分钟完成。若两人一起折，需要多少分钟完成?()

论述元认知策略及其教学。

有两个关系R和S如下：由关系R通过运算得到关系S，则所使用的运算为

A、Itisbasedonresearchesfrombothschoolsandworkplaces.B、Itliststhingsthathelpkidsnowandinthefuture.C、Itisab