首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2017-01-04
122
问题
关于堆的一些问题:
(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
学硕统考专业
相关试题推荐
试通过分析北京人的体质特征,说明“劳动创造了人本身”是科学真理。
评述抗战的三个阶段。
戊戌维新运动失败的原因和教训。
《关于建国以来党的若干历史问题的决议》的主要内容及其意义。
如何全面分析十月革命的历史条件及特点?
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
当代科技革命说明:作为第一生产力的(),是推动现代生产力发展的最活跃因素,并且是现代社会进步的决定性力量。
宁夏回族自治区的设立时间是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
欧洲历史上第一部系统完备的法典是()。
随机试题
关于连续性和可用性管理的描述,不正确的是:________。
新一轮服务贸易谈判的方式是
第一度房室传导阻滞心电图PR间期应( )
口服铁剂治疗有效的缺铁性贫血患者,下列检查最先上升的是
A公司以30万元的价格向B公司订购一台机床,根据合同约定,A公司以银行承兑汇票支付价款。2010年3月1日,A公司签发一张以B公司为收款人、金额为30万元的银行承兑汇票(承兑银行已经签章),到期日为2010年9月1日。A公司将该汇票交给采购经理甲,拟由其携
NewVacationPolicyAllvacationdaysmustbetakenwithinthecalendaryearwithwrittenrequestssubmittedandapprovedby
2008年随着国际金融危机的出现和蔓延,中国饮料行业也几乎进入了寒冬。然而,大型食品饮料企业A公司却能够在饮料行业独树一帜,销售量不断提升。2008年,A公司与央视、部分省级电视台建立了长期广告发布合作机制,以确保自己的广告能在第一时间赢
家庭社会工作者应具备哪些能力?( )
《中华人民共和国未成年人保护法》中的未成年人指的是未满()周岁的公民。
Inhisclassicnovel,ThePioneers,JamesFenimoreCooperhashishero,alanddeveloper,takehiscousinonatourofthecity
最新回复
(
0
)