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

admin2018-08-12 26

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

选项

答案(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：由于第i层上的结点数至多是2^i-1，以它为根的二叉树的深度为h一i+1，则调用[*92]次筛选算法时总共进行的关键字比较次数不超过下式之值： [*] 提示：此题考查的知识点是堆的基本定义及效率。堆定义为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/rMRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

近代天文学革命引起教会人士的极端仇恨，其根本原因是它()

下列有关《布列斯特和约》的说法中，错误的一项是()。

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

元曲是元代文学的重要成就，涌现出一批优秀作品，下列作者与作品对应错误的是()。

试述法国大革命的特点及影响。

论述欧洲一体化的进程及影响。

在教皇()的时候，罗马教廷的势力达到了鼎盛。

有效容量为128KB的Cache，每块16字节，8路组相联。字节地址为1234567H的单元调入该Cache，其Tag应是()。

“冲天香阵透长安，满城尽带黄金甲”是唐末农民大起义领袖、冤句人黄巢的名句，当时的“冤句”也就是今天的()。

简述影响社会态度形成的因素。

A、现病史B、既往史C、个人史D、月经及婚育史E、家族史起病日期、发病情况及有关发病因素等记入

根据《中华人民共和国水法》，关于建立饮用水水源保护区制度及设置、新建、改建或者扩大排污口的说法，错误的有()。

某史书序言中说：“上起战国，下终五季，一千三百六十二年之间，贤君令主，忠臣义士，志士仁人，兴邦之远略，善俗之良规……靡不具焉。”这部史书是()。

Word2007中，若要计算表格中某列数值的总和，可使用的统计函数是()。

设曲线L过点(1，1)，L上任意一点P(χ，y)处的切线交χ轴于点T，O为坐标原点，若{PT}＝｜OT｜。试求曲线L的方程。

Awisemanoncesaidthattheonlythingnecessaryforthetriumphofevilisforgoodmentodonothing.So,asapoliceoffice

Projectingtheideaofadistinctivefemaledemandinseventeenth-andeighteenth-centuryEnglandwasagroundbreakingdeparture