首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2017-01-04
75
问题
关于堆的一些问题:
(1)堆的存储表示是顺序的,还是链接的?
(2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大0表示法)?
选项
答案
(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/SLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
分析东欧国家选择斯大林政治经济体制的主要原因。
论述15世纪以后美洲作物在中国和欧洲的传播及影响。(2013年统考真题)
戊戌维新运动失败的原因和教训。
《关于建国以来党的若干历史问题的决议》的主要内容及其意义。
武昌起义()。①由同盟会直接领导②原计划被偶然因素打乱③其成功有深刻的社会原因④迅速的胜利潜伏着失败的危机
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
下列关于第二三次科技革命的说法,不正确的是()。
“两个凡是”
美国首次提出争夺世界霸权的纲领性文件是()。
请根据下面材料,结合相关知识,分析其内容及意义。他命令所有罗马人都进行登记并用银对自己的财产估价,按照习惯宣誓保证所报各项均属真实,全部财产均已按最高价格估价,并陈报父亲系何人,自己的年龄,自己的妻子和子女的名字,每人的籍贯隶属市中哪个部落或乡间
随机试题
患儿,女,1岁,生后3个月起青紫渐加重,活动后气急,查体:生长发育明显落后,口唇、鼻尖、耳垂、指/趾青紫明显,伴杵状指趾,胸骨左缘闻及Ⅲ级收缩期杂音,肺动脉第二心音减弱。该患儿可能的诊断为
在曲线长隧道中应采用的通风方式为()。
证券清算与交割、交收两个过程统称为()。
领导给你安排的事情和相关法律、法规有冲突,你怎么办?
[2013年第41题]最近一项研究发现,海水颜色能够让飓风改变方向,也就是说,如果海水变色.飓风的移动路径也会变向。这也就意味着科学家可以根据海水的“脸色”判断哪些地方将被飓风袭击,哪些地区会幸免于难。值得关注的是,全球气候变暖可能已经让海水变色。以下哪项
下列关于关税税率的表述中,正确的有()。
1956年4月,毛泽东在《论十大关系》中提出的建设社会主义的基本方针是
设f(x)在[0,1]上连续,在(0,1)内可导,且f(0)=f(1),证明:存在ξ,η∈(0,1),使得f’(ξ)+f’(η)=0.
Whatisthefatherinterestedin?
AretheBritishpeopleEuropeans?ThismayseemastrangequestiontoAfricansandAsians,whotendtothinkofallwhitemenas
最新回复
(
0
)