首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2017-01-04
76
问题
关于堆的一些问题:
(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
学硕统考专业
相关试题推荐
试析北宋加强中央集权的措施及其影响。(华东师范大学1999年中国古代史真题;四川大学1999年中国古代史真题;厦门大学1999年中国古代史真题;北京师范大学2003年中国古代史真题;北京大学2004年中国古代史真题;苏州大学2004年中国古代史真题;南京大
解析两个战场的地位、作用及相互关系。
新中国成立之后都进行了哪些巩固措施?
【《关于正确处理人民内部矛盾的问题》】
在1919年巴黎和会上,日本代表对欧洲事务很少开口,故被称作“沉默的小伙伴”。日本“沉默”的主要原因是()。
关于德国工业革命,说法不正确的是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
公元9~13世纪是西欧封建庄园的兴盛时期,典型的庄园采用()的剥削方式。
《萨利克法典》提及法兰克人的一项犯罪申诉习惯。即任何必须以汤釜神判法,判定犯罪嫌疑人要用右手从沸水中取出指定物品,这表明当时法兰克王国
随机试题
高强度军事训练时,出现中暑的病因主要是
布置办公室应包括的因素有()。
下肢淋巴压在活动时为下列哪项
由曲面及z=x2+y2所围成的立体体积的三次积分为()。
在悬索桥锚碇混凝土施工中,主要检测项目有()。
下面属于资产负债表附表的是()。
一般均衡分析与局部均衡分析的区别主要表现在()。
2005年9月,()发布《保险外汇资金境外运用管理暂行办法实施细则》,允许保险公司将国家外汇管理局核准投资付汇额度10%以内的外汇资金投资在海外股票市场,投资对象限于在纽约、伦敦、法兰克福、东京、新加坡和中国香港证券交易所上市的中国企业股票。
中国古代青铜器工艺实践中,形成了较为完整的合金材料技术知识。先秦文献《考工记》记录了六类青铜器物的合金成分配比:“金有六齐:六分其金而锡居一,谓之钟鼎之齐;五分其金而锡居一,谓之斧斤之齐;四分其金而锡居一,谓之戈戟之齐;三分其金而锡居一,谓之大刃之齐;五分
假设保护方式下Pentium微处理器的(DS)=0103H,则下列______类型的段能被访问。
最新回复
(
0
)