首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2019-08-15
83
问题
关于堆的一些问题:
(1)堆的存储表示是顺序的,还是链接的?
(2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大0表示法)?
选项
答案
(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点,在最下两层上。 (3)在建含有n个元素、深度为h的堆时,其比较次数不超过4n,推导如下: 由于第i层上的结点数至多是2
i-1
,以它为根的二叉树的深度为h一i+1,则调用[n/2]次筛选算法时总共进行的关键字比较次数不超过下式之值: [*]2
i-1
×2(h一i)=[*]2
i
×(h一i)=[*]2
h-j
×j≤(2n)[*]j/2
j
≤4n 提示:此题考查的知识点是堆的基本定义及效率。堆定义为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/xKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
重庆谈判签署的文件是()。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
分时系统里,在条件相同的情况下,通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间,请简要解释之。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
一台主机申请了一个到www.ab@C@edu.cn的连接,为了获取服务器的IP地址,首先要进行DNS查询,下图为本次查询的过程,请回答如下问题:(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
某计算机系统字长为32位,包含2个选择通道和1个字节多路通道,每个选择通道上连接了2台磁盘机和2台磁带机,字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下:磁盘机:800KB/s磁带机:200KB/s
随机试题
子产的刑法思想是对( )的继承。
记忆的第一个基本过程是
常脉中有神的表现是()
A.胃脘痛暴作,畏寒喜暖B.胃痛剧烈,固定不移C.胃痛隐隐,泛吐清水D.胃痛胀满,嗳腐吞酸E.胃脘作痛,痛连两胁寒邪客胃之胃痛的主要临床表现有()
根据公司法律制度的规定,持有有限责任公司全部股东表决权10%以上的股东,在发生某些法定事由时,可以提起解散公司的诉讼,人民法院应予受理。下列各项中,属于该法定事由的有()。
2013年3月1日.甲公司签发一张出票后一个月付款的银行承兑汇票给乙公司。根据票据法律制度的规定,下列说法正确的是()。
简述会计核算的具体内容。
一个中年人住进医院,左半边身子没有知觉。有个孩子在病房里大声喧哗,被他父亲拧了一下,痛得直叫。病人说:“我真羡慕这孩子啊!”有人问:“羡慕他无忧无虑?”病人摇头。“羡慕他如花的年龄?”病人说:“不是,我羡慕他有那么敏感的疼痛。如果我能感觉到疼痛,那就意味着
A、 B、 C、 D、 C
Don’thesitatetoaskforhelpifyou____________(解决问题遇到麻烦).
最新回复
(
0
)