首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2019-08-01
35
问题
关于堆的一些问题:
(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://jikaoti.com/ti/CDGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述清末新政的内容及其影响。
中国古代的经济、文化中心本来在北方,后来移到了南方。请结合史实对这一转移过程进行述评。
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:明朝推行一条鞭法中“一”的内容是()
中国共产党在抗日民主根据地实行的土地政策是()。
中国第一条自行设计修建的铁路是在()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
真值0在原码、反码和补码机器数形式下()。
著名的网络OSI七层模型是由()组织提出来的。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
下列选项中,属于法的规范作用的有
肾上腺神经母细胞瘤超声表现描述错误的是
A.痰脓腥臭B.痰稠黄胶结C.痰稀薄多沫或痰白而黏D.痰少黏稠难出E.痰如白沫量多
A.血虚动风B.热极生风C.阴虚动风D.疫毒攻心E.肝阳化风舌红少津而颤动的病机是()
我国消费税从()年开始正式施行。
长江股份有限公司系上市公司(以下简称“长江公司”),为增值税一般纳税人,销售商品适用的增值税税率为17%,所得税采用资产负债表债务法核算,适用的所得税税率为25%。除特别说明外,不考虑除增值税、所得税以外的其他相关税费,所售资产均未计提减值准备。销售商品均
发放股票股利与发放现金股利相比,具有的优点有()。
下列选项中,()不是保险与赌博的区别。
神经衰弱疲劳具有()。
PASSAGEONEAccordingtothecontext,whatdoestheword"trepidation"mean?
最新回复
(
0
)