首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 (1)画出在图中插入关键字为5的结点后的最小最大
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 (1)画出在图中插入关键字为5的结点后的最小最大
admin
2023-02-06
124
问题
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。
(1)画出在图中插入关键字为5的结点后的最小最大堆。
(2)画出在图中插入关键字为80的结点后的最小最大堆。
(3)编写算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中,关键字为整数。
选项
答案
(1)加入关键字值为5的结点后,最小最大堆如下图: [*] (2)加入关键字值为80的结点后,最小最大堆如下图: [*] (3)从插入位置进行调整,调整过程由下到上。首先根据元素个数求出插入元素所在层次数,以确定其插入层是最大层还是最小层。若插入元素在最大层,则先比较插入元素是否比双亲小,如是,则先交换,之后,将小堆与祖先调堆,直到满足小堆定义或到达根结点;若插入元素不小于双亲,则调大堆,直到满足大堆定义。若插入结点在最小层,则先比较插入元素是否比双亲大,如是,则先交换,之后,将大堆与祖先调堆;若插入结点在最小层且小于双亲,则将小堆与祖先调堆,直到满足小堆定义或到达根结点。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/wowD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《基础教育课程改革纲要(试行)》中提出,“倡导学生主动参与、乐于研究、勤于动手”“学生通过实践,增强探究和创新意识,学习科学研究的方法,发展综合运用知识的能力”。该规定要求学校的课程设置要重视培养学生()。
数学老师在考试前提醒学生,考试时若遇到难题可以放一放,先把后面相对简单的题答完了再回过头来思考。可小明却不喜欢这样,他每次都是一步一步地依照试卷的顺序答题。小明的认知风格更可能属于()。
美国心理学家波斯纳提出的教师成长公式是经验+评价:成长。()
某商场为了促销,进行掷飞镖游戏。每位参与人员投掷一次,假设掷出的飞镖均扎在飞镖板上且位置完全随机,扎中中间阴影部分区域(含边线)即为中奖。该商场预设中奖概率约为60%,仅考虑中奖概率的前提下,以下四幅图形(图中的正三角形和正方形均与圆外切或内接)最适合作为
太平洋上有一个圆形的平坦小岛,岛上遍布森林,闪电击中处于小岛边缘的树木引发森林火灾(如图所示)。假设火线是以圆弧状往小岛深处推进,问当大火烧到小岛中心位置时,过火面积占全岛面积的比例大约是多少?
站在新的历史起点上,展望建设现代化国际瓷都的未来,拥有2000年冶陶史、1000年官窑史、600年御窑史及新中国成立以来70年陶瓷生产史的景德镇,必将继续传承陶瓷文化,深度挖掘千年瓷都人文________,创新陶瓷产业,构建新时代陶瓷产品和话语体系,扩大陶
域控制器存储了域内的账户、密码和属于这个域的计算机三项信息。当计算机接入网络时,域控制器首先要鉴别这台计算机是否属于这个域,用户使用的登录账户是否存在,密码是否正确。如果三项信息均正确,则允许登录;如果以上信息有一项不正确,那么域控制器就会拒绝这个用户从这
研究人员介绍,来源于化脓链球菌的Cas9核酸酶现已广泛应用于水稻基因组编辑,有效促进了水稻功能基因组学研究和分子育种进程。Cas9在进行基因组编辑的过程中需要识别、结合一段位于编辑位点靶DNA序列末端的保守NGG序列(该保守序列被称为PAM识别序列,N为碱
对一个图进行遍历可以得到不同的遍历序列,那么导致得到的遍历序列不唯一的因素有哪些?
随机试题
固定义齿修复的缺点为
ABC公司被要求对其从1997—2000年生产和销售的某个产品进行盈利能力的评估。该产品从销售之日起有1年的质保期。以下是在财务记录上的信息:该产品的生命周期成本为
导游人员在与旅游者交往过程中如何才能处理好彼此的关系?
1995年,第八届全国人民代表大会第三次会议通过了《__________》。
某大学参加军训队列表演,组织一个方阵队伍。如果每班60人,这个方阵至少要有5个班的同学参加;如果每班70人,这个方阵至少要有4个班的同学参加。那么组成这个方阵最外层的人数应为几人?()
2010年全国水产养殖面积比上年增长4.97%。其中,海水养殖面积2080.88千公顷,占水产养殖总面积的27.21%,比上年增长11.92%;淡水养殖面积5564.34千公顷,占水产养殖总面积的72.79%,比上年增长2.59%。海水养殖面积:
若关系模式中存在非主属性对码的部分依赖,则该关系模式属于(54)。
Everycultureattemptstocreatea"universeofdiscourse"foritsmembers,awayinwhichpeoplecaninterprettheirexperience
ReadingPassage2hassixparagraphs,A-F.Choosethecorrectheadingforeachparagraphfromthelistofheadingsbelow.Write
Completethenotesbelow.WriteNOMORETHANTWOWORDSAND/ORANUMBERforeachanswer.BirminghamExhibitionExampleAnswerPur
最新回复
(
0
)