首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2017-01-04
83
问题
关于堆的一些问题:
(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
学硕统考专业
相关试题推荐
分析南斯拉夫走上自治道路的原因。
试述印度非暴力不合作运动。
希腊城邦体制的特点。
以下内容不属于中国共产党为解决中西部落后问题,巩固发展国防事业而采取的三线建设的是()。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
春秋时期的鲁国初税亩和战国时期以商鞅变法为代表的各国变法,在历史上产生了深刻的影响。这些变法的最大作用和产生的最主要的社会后果是()。
改革开放以后,我国农村产业结构巨大的转变表现在()。
在20世纪60年代末,日本发展成为资本主义世界第二号经济强国的诸多因素中,不包括()。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
操作系统技术中临界区是指()。
随机试题
跟语音、词汇相比,语法具有更明显的_____、稳固性和民族性。
在选用胀接加端面焊的结构形式时,________比较合适。
设函数z=ex+y,则dz=__________。
毛泽东在《关于正确处理人民内部矛盾的问题》中提出文化工作的方针是( )
天麻钩藤饮治疗眩晕证时,应具备的其他主症是
药品监督管理部门在日常监督检查工作中,发现甲药品零售企业在柜台销售标示乙医院配制的治疗痤疮的外用膏剂。经立案调查,查实乙医院具有《医疗机构制剂许可证》,但在未取得制剂批准文号情况下,由医院制剂部门擅自配制,后经乙医院药剂人员丙购买并出售给甲药品零售企业。甲
下列哪一项不属于我国基金行业快速发展阶段的特点?()
请运用中国法制史的理论知识对下列材料进行分析,并回答下列问题。《明史·刑法志一》:“建文帝即位,谕刑官曰:‘《大明律》,皇祖所亲定,命朕细阅,较前代往往加重,盖刑乱国之典,非百世通行之道也。’”《明史·刑法志二》:“盖太祖用重典以惩一时
f(χ1,χ2,χ3,χ4)=XTAX的正惯性指数是2,且A2=2A=O,该二次型的规范形为_______.
请设置当前选中文本框格式为垂直“顶部居中”,内部左右边距各为“3厘米”。
最新回复
(
0
)