首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 (1)画出在图中插入关键字为5的结点后的
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 (1)画出在图中插入关键字为5的结点后的
admin
2017-01-04
21
问题
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。
(1)画出在图中插入关键字为5的结点后的最小最大堆。
(2)画出在图中插入关键字为80的结点后的最小最大堆。
(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中,关键字为整数。
选项
答案
此题考查的知识点是堆的算法。将插入的元素放到最后,然后调整,方法同第13题。 (1)加入关键字值为5的结点后,最小最大堆如下图。 [*] (2)加入关键字值为80的结点后,最小最大堆如下图。 [*] (3)从插入位置进行调整,调整过程由下到上。首先根据元素个数求出插入元素所在层次数,以确定其插入层是最大层还是最小层。若插入元素在最大层,则先比较插入元素是否比双亲小,如是,则先交换,之后,将小堆与祖先调堆,直到满足小堆定义或到达根结点:若插入元素不小于双亲,则调大堆,直到满足大堆定义。若插入结点在最小层,则先比较插入元素是否比双亲大,如是,则先交换,之后,将大堆与祖先调堆;若插入结点在最小层且小于双亲,则将小堆与祖先调堆,直到满足小堆定义或到达根结点。 void MinMaxHeapIns(RecType R[],int n){ //假设R[1..n一1]是最小最大堆,插入第n个元素,把R[1..n]调成最小最大堆 j=n;R[0]=R[j]; h=log
2
n+1; //求高度 if(h%2==0){ //插入元素在偶数层,是最大层 i=n/2; if(R[0].key<R[i].key){ //插入元素小于双亲,先与双亲交换,然后调小堆 R[j]=R[i]; j=i/4; while(j>0&&R[j]>R[i]){ R[i]=R[j];i=j;j=i/4;} //调小堆 R[i]=R[0]i } else{ //插入元素大于双亲,调大堆 i=n;j=i/4; while(j>0&&R[j]<R[i]){R[i]=R[1];i=j;j=i/4;} R[i]=R[0]; } } else{ //插入元素在奇数层,是最小层 i=n/2: if(R[0].key>R[i].key){ //插入元素大于双亲,先与双亲交换,然后调大堆 R[j]=R[i]; j=i/4; while(j>0&&R[j]<R[i]){ R[i]:R[j]=i:j;j=i/4; } //调大堆 R[i]=R[0]; } else{ //插入元素小于双亲,调小堆 i=n;j=i/4; while(j>0&&R[j]>R[i]){ R[i]=R[j];i=j;j=i/4;} R[i]=R[0]; } } }
解析
转载请注明原文地址:https://jikaoti.com/ti/H6fjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述明治维新过程中土地改革的主要内容和意义。
简述第二次世界大战对战后国际关系的影响。
试简述当代资本主义经济发展的三个阶段。
开皇三年,隋文帝下令州县官吏根据户籍簿上登记的年龄,来核对本人体貌,以防诈老诈小逃避租役,是为()。
1985年2月,中共中央和国务院决定开辟的沿海经济开放区是()。
苏联实行的新经济政策与美国推行的罗斯福新政之间的相似之处是()。①面临极为困难的经济形势②最主要内容是调整和复兴工业③国家颁布法令强制干预经济④通过发展商品经济生产来恢复农业
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
下列科技文化成就,产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车
设有m个连续单元供一个栈与队列使用,且栈与队列的实际占用单元数事先不知道,但是要求在任何时刻它们占用的单元数量不超过m,试写出上述栈与队列的插入算法。
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
随机试题
在考生文件夹下的“samp1.accdb”数据库文件中已建立两个表对象(名为“职工表”和“部门表”)。请按以下要求,顺序完成表的各种操作:设置表对象“职工表”的聘用时间字段默认值为系统日期。
使血压测量值相对准确的措施不包括
《最高人民法院关于审理盗窃案件具体应用法律若干问题的解释》规定:各地高级人民法院可根据本地区经济发展状况,并考虑社会治安状况,在本解释规定的数额幅度内,分别确定本地区执行“数额较大”、“数额巨大”、“数额特别巨大”的标准。依据法理学的有关原理,下列正确的表
以下企业中,属于转让定价调查应重点选择的企业有()。
每笔个人汽车贷款只能展期()次。
客户信用评级是商业银行对客户偿债能力和偿债意愿的计量和评价,反映客户违约风险的大小。()
下列关于处理意见分歧的说法中,正确的是()。
王华被学校委派到国际交流处负责外籍老师的引进和管理工作。()
Previousresearchesonmindfulnessmeditationhaveshownsomeresultsthatinfluencepeopleformanyyears.Itshowsthatmindfu
SIGG’strendyaluminumwaterbottleshavescoredalotoffreeadvertisinginrecentyears.SIGGhasbeen【67】formorethan100y
最新回复
(
0
)