首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2018-08-12
43
问题
关于堆的一些问题:
(1)堆的存储表示是顺序的,还是链接的?
(2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大O表示法)?
选项
答案
(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点,在最下两层上。 (3)在建含有n个元素、深度为h的堆时,其比较次数不超过4n,推导如下: 由于第i层上的结点数至多是2
i-1
,以它为根的二叉树的深度为h一i+1,则调用[*92]次筛选算法时总共进行的关键字比较次数不超过下式之值: [*] 提示:此题考查的知识点是堆的基本定义及效率。堆定义为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/rMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列有关《布列斯特和约》的说法中,错误的一项是()。
全国高校院系调整的具体时间是()。
论述罗马共和国早期对外征服的过程和历史意义。
在19世纪晚期到20世纪初期时,英法经济发展缓慢下来的共同原因是()。①技术装备相对落后②战败的割地赔款③资本大量输出④资源和劳动力的匮乏
在巴黎和会上,法国要求严厉制裁德国的目的是()。
有关斯巴达国家建立传说的社会改革是()。
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
在一个按字节编址的计算机中,若数据在存储器中以小端方案存放。假定int型变量i的地址为08000000H,i的机器数为01234567H,地址:08000000H单元的内容是()。
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
随机试题
影响导流能力的主要因素有哪些?
政府机关的信息工作主要包括()
男,25岁。1年来牙龈逐渐肿大。检查:全口牙龈乳头及龈缘肿胀,上下前牙明显。龈乳头呈球状,突起,前牙牙龈呈分叶状,质地坚硬,略有弹性,呈粉红色,不出血,无疼痛,龈沟加深,菌斑软垢较多,11、21牙部分冠折断,已行根管治疗。上述检查仍不能确诊,在用药史上
A.淋巴细胞增殖反应试验B.免疫球蛋白检测C.RT—PCR技术D.黏附分子测定E.CHso溶血试验T细胞免疫缺陷选择
A、苯醌、萘醌B、苯醌、萘醌中醌环上有未被取代的结构C、蒽醌D、有α-羟基蒽醌或邻羟基蒽醌E、醌类化合物无色甲蓝反应()
以下有关ADR.叙述中,不属于“病因学B类药物不良反应”的是
关于减刑,下列哪一选项是正确的?()
在其他条件不变的情况下,()的上升对劳动力需求产生的替代效应会导致劳动力需求量下降。[2007年真题]
2010年,福建省国内旅游人数和国内旅游收入分别达到11417万人和1135.07亿元,比上年增长17.6%和18.8%,全省住宿业实现营业额127.09亿元,比上年增长18.9%,增幅比上年提高7.0个百分点。全省限额以上正餐企业、快餐企业和饮
关系模式中,表示实体间n:m联系是通过增加一个(53)。
最新回复
(
0
)