首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2019-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
1
,K
2
,…,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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
分析“二战”后日本经济起飞的主要原因。
下列哪一个不是罗马王政时代的管理机构?()
1642年英国内战爆发后,议会民兵武装力量远超王党军队,海军也支持议会,许多港口处于议会控制下,但议会军在战场节节失利,原因是
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
某新石噐遗址发现大量稻谷壳和稻草,红士,防洪水城垣,此遗址可能是
1977年4月,对“两个凡是”提出批评,开全党思想解放先河的是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
ICMP在TCP/IP协议集中属于()。
操作数地址存放在寄存器的寻址方式叫()。
在一个单处理器系统中,存在3个进程,最多有几个进程处于就绪队列()。
随机试题
肢体完全缺血多少时间,会发生肢体永久性功能障碍
驾驶机动车通过窄路、窄桥时,最高速度不能超过多少?
Youshouldlearnthroughfailures.Whydon’tyou______yourplanortryanewapproach?
传统的定额计价模式下,用单价法编制施工图预算过程中,单价是指()。
甲与乙订立货物买卖合同,约定甲于1月8日交货,乙在交货期后的一周内付款。交货期届满时,甲发现乙有转移资产以逃避债务的行为。对此甲可依法行使()。
对抗,在生态学中指生活在一起的两种不同种类的生物,一方或双方遭受损害的关系。对抗通常是不同生物为占据同一生态位而产生的结果。可分为侵害、抗生和竞争,一种生物受益而另一种生物遭受损害的属于侵害;一种生物遭受损害而另一种生物不受影响的属于抗生;两种生物相互施加
=_____________________。
下列关于接入技术特征的描述中,错误的是()。
扩展名为.prg的程序文件在“项目管理器”的【】选项卡中显示和管理。
PeopleintheUnitedStateslovetheirdogsandtreatthemwell.Theyusemanyexpressionswiththeword"dog".Herearesomeex
最新回复
(
0
)