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

admin2019-08-01 59

问题关于堆的一些问题：
(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://kaotiyun.com/show/S3Ci777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

分析“二战”后日本经济起飞的主要原因。

下列哪一个不是罗马王政时代的管理机构?()

1642年英国内战爆发后，议会民兵武装力量远超王党军队，海军也支持议会，许多港口处于议会控制下，但议会军在战场节节失利，原因是

1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是

某新石噐遗址发现大量稻谷壳和稻草，红士，防洪水城垣，此遗址可能是

1977年4月，对“两个凡是”提出批评，开全党思想解放先河的是()。

ICMP在TCP／IP协议集中属于()。

操作数地址存放在寄存器的寻址方式叫()。

在一个单处理器系统中，存在3个进程，最多有几个进程处于就绪队列()。

肢体完全缺血多少时间，会发生肢体永久性功能障碍

驾驶机动车通过窄路、窄桥时，最高速度不能超过多少？

Youshouldlearnthroughfailures.Whydon’tyou______yourplanortryanewapproach?

传统的定额计价模式下，用单价法编制施工图预算过程中，单价是指()。

甲与乙订立货物买卖合同，约定甲于1月8日交货，乙在交货期后的一周内付款。交货期届满时，甲发现乙有转移资产以逃避债务的行为。对此甲可依法行使()。

=_____________________。

下列关于接入技术特征的描述中，错误的是()。

扩展名为.prg的程序文件在“项目管理器”的【】选项卡中显示和管理。

PeopleintheUnitedStateslovetheirdogsandtreatthemwell.Theyusemanyexpressionswiththeword"dog".Herearesomeex