首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2018-08-12
39
问题
关于堆的一些问题:
(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
学硕统考专业
相关试题推荐
1935年,中共确定建立抗日民族统一战线的方针是在()。
规定了电流、电动势、电阻等概念的物理学家是()。
1927年蒋介石在南京建立政权,其新特点是()
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
王艮创立的()是中国封建社会后期的第一个启蒙学派,其从者大都致力于封建道德的普及宣传工作。
“文化大革命”结束后,在纠正“文化大革命”错误的过程中,整个过程受到()的严重阻碍。
中国近代第一所外语学校、同时也是新式学堂的是()。
假设磁头当前位于第105道,正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35,45,12,68,110,180,170,195,采用SCAN调度(电梯调度)算法得到的磁道访问序列是____。
随机试题
发包人收到承包人提交的最终结清申请单,并在规定时间内予以核实后,向承包人签发()。
在Word编辑状态下,通过( )可以选中整个文档内容。
陈先生与另一个合伙人在A市共同兴办了一家合伙企业甲,出资比例为5:5。2010年年初,陈先生向其主管税务机关报送了2009年度的所得税申报表和会计决算报表以及预缴个人所得税纳税凭证。该合伙企业年度会计报表反映:合伙企业2009年度的主营业务收入70万元,投
纸质书是一个多页共存的实体,一件有其完整物质形态的物品,由封面、扉页、目录、前言、主体、后记等要素构成,其本身就是一个占据一定空间的艺术品。这是纸质书与电子书的根本区别。在传递信息这一功能上,电子书与纸质书没有区别;但二者一是虚拟,一是实体,一是单面,一是
资本结构问题:375万现金流(EBIT),750万的债务,rB=10%,初始该公司想把提高到50%。(北京大学2017年真题)求相同公司(无负债/全权益)的R0。
某研究人员在2004年对一些12~16岁的学生:进行了智商测试,测试得分为77~135分。4年之后再次测试,这些学生的智商得分为87~143分。仪器扫描显示,那些得分提高了的学生,其脑部比此前呈现更多的灰质(灰质是一种神经组织,是中枢神经的重要组成部分)。
《中华人民共和国标准化法》将我国标准分为国家标准、地方标准等(35)级。
Text…【C1】______Thanksgivingturkey,it’shardtofind【C2】______"American"food.TheUnitedStatesisalandof【C3】______
一个成熟的公共服务系统一旦建立起来,它将成为社会持续发展的重要推动力量。
Thebraindrain(人才流失)isauniversalphenomenon,andcountriesthatdon’tfaceuptothenewrealitywillbelosingsomeofthe
最新回复
(
0
)