首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2019-08-01
66
问题
关于堆的一些问题:
(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://kaotiyun.com/show/S3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述隋唐科举制的内容和意义。
现代人种出现于人类发展过程中的哪一个时期?()
晋察冀抗日根据地
下列关于20世纪历史的叙述,全部错误的是()。①朝鲜建国的时间早于中国②1948年3月,英国、法国、比利时、荷兰、卢森堡5国缔结了《合作和集体防御条约》即《五国和约》③1950年,周恩来到达莫斯科,中苏缔结了《中苏互不侵犯条约》,标志着社会主
论述科举制度的演变及其历史作用。
对三国鼎立局面的形成起到关键性作用的战役是()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。据此回答问题:中共中央将战略决战的方向首先指向的是()
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
IEEE754标准规定的64位浮点数格式中,符号位为1位,阶码为11位,尾数为52位。则它所能表示的最小规格化负数为()。
随机试题
对于传入侧支性抑制的描述,恰当的是
目前国际上最常用的评定帕金森病外科治疗疗效的方法为
A.异丙基肾上腺素B.腺苷C.肾上腺素D.硝苯地平E.利多卡因阵发性室性心动过速,可选用
用友报表系统中,用户可以根据自己的需要设置相应的关键字。()
X企业购入Y企业一批产品,价款50000元,增值税税率17%,付款条件为2/10,N/30。产品已入库,货款暂欠。则( )。
WindowsXP中鼠标器的单击操作方式可用来完成()操作。
InanoldfactorybuildinginlowerManhattanafintechstartupisseekinganswerstoaquestionthathastormentedteachersand
A、 B、 C、 D、 D
Deathcomesquicklyinthemountains.Eachwinterholidaymakersarecaughtunawaresastheyhappilyskiawayfromthefixedrun
Forthispart,youareallowed30minutestowritealettertoyourpenfriendinAmerica,introducingoneoftheChinesefestiv
最新回复
(
0
)