首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2019-08-01
61
问题
关于堆的一些问题:
(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
学硕统考专业
相关试题推荐
提出帝王“受命不于天。于其人”观点的唐代思想家是()。
现代人种出现于人类发展过程中的哪一个时期?()
第二次工业与第一次工业革命相比较,其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级
全国高校院系调整的时间是()。
中共八届九中全会提出的恢复和调整国民经济的方针是()。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
严复翻译的《天演论》一书的出版时间是()。
以下()协议完成了从网卡到IP地址的映射。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
随机试题
外汇
不属于HASTE序列优点的是
A.40mmol/LB.24mmol/LC.50mmol/LD.12mmol/LE.25mmoL/L
血淋,尿色深红治疗方剂是()
恶性肿瘤患者化疗期间,白细胞降至3×109/L,正确的处理是
中断供电将影响实时处理计算机及计算机网络正常工作,应按()要求供电。
张繁30多岁时她女儿出生,2008年她女儿的年龄是她的年龄的,2009年张繁多少岁?
下列哪项是恶性肿瘤的最主要诊断依据
A、Keeptheirpaycheckandbenefits.B、Dosomesoulsearching.C、Askforadvicefromtheirfriends.D、Changethejobimmediately.
A、Shewasworkingonthatday.B、ShetaughtJapanesestudents.C、Shereceivednothingfromherstudents.D、Shereceivednochoco
最新回复
(
0
)