最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 (1)画出在图中插入关键字为5的结点后的最小最大

admin2023-02-06 71

问题最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。

(1)画出在图中插入关键字为5的结点后的最小最大堆。
(2)画出在图中插入关键字为80的结点后的最小最大堆。
(3)编写算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。

选项

答案(1)加入关键字值为5的结点后，最小最大堆如下图： [*] (2)加入关键字值为80的结点后，最小最大堆如下图： [*] (3)从插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元素所在层次数，以确定其插入层是最大层还是最小层。若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直到满足小堆定义或到达根结点；若插入元素不小于双亲，则调大堆，直到满足大堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖先调堆，直到满足小堆定义或到达根结点。 [*]

解析

转载请注明原文地址:https://kaotiyun.com/show/wowD777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

课程内容应考虑让学生了解社会、接触社会，掌握一些解决社会问题的基本技能。课程内容一旦脱离了社会，就是让学生脱离社会。()

学生在解决一个问题之后，以后遇到同样类型的问题还会采取先前的思维模式去解题。这种现象说明了什么?()

自学指导法包括指导学生预习、阅读参考书等，这一方法最突出的特点是指导学生合作学习。()

学习疲劳是指学习者由于学习过度或学习方法不当而产生的学习效率逐渐降低，并伴有渴望停止学习活动的生理和心理现象。()

美国单轨学制自下而上的结构是小学、中学，而后可以升人大学，其特点是一个系列、多种分段，即“六三三”“五三四”等。自美国单轨学制设立以来，世界上许多国家纷纷效仿，其主要原因是单轨学制有助于()。

在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这。填入画横线部分最恰当的一项是：

在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这。填入画横线部分最恰当的一项是：

在《制台见洋人》中，外国领事责问制台的原因是（）

血中增高提示胎儿宫内感染的Ig是

左向右分流型心脏病是

某投资者通过场外(某银行)投资1万元申购某上市开放式基金，假设基金管理人规定的申购费率为1．5％，申购当日基金份额净值为1．025元，则其申购手续费为()。

为各项工作提供必要警用装备、设施、器材、工具、服务等属于()。

Afewcommonmisconceptions.Beautyisonlyskin-deep.One’sphysicalassetsandliabilitiesdon’tcountallthatmuchinamana

Cityresident:Thesenewdigitalelectronicbillboardsshouldbebannedforlightpollutionsincetheyaremuchtoobright.Out

income

Whatarethestudentsmainlydiscussing?

Theroaddepartmentapologizedforanyinconveniencecausedwhileroadimprovementswereinprogress

计算机408

学硕统考专业

课程内容应考虑让学生了解社会、接触社会，掌握一些解决社会问题的基本技能。课程内容一旦脱离了社会，就是让学生脱离社会。()

学生在解决一个问题之后，以后遇到同样类型的问题还会采取先前的思维模式去解题。这种现象说明了什么?()

自学指导法包括指导学生预习、阅读参考书等，这一方法最突出的特点是指导学生合作学习。()

学习疲劳是指学习者由于学习过度或学习方法不当而产生的学习效率逐渐降低，并伴有渴望停止学习活动的生理和心理现象。()

美国单轨学制自下而上的结构是小学、中学，而后可以升人大学，其特点是一个系列、多种分段，即“六三三”“五三四”等。自美国单轨学制设立以来，世界上许多国家纷纷效仿，其主要原因是单轨学制有助于()。

在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和________居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这________。填入画横线部分最恰当的一项是：

在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和________居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这________。填入画横线部分最恰当的一项是：

在《制台见洋人》中，外国领事责问制台的原因是（）

血中增高提示胎儿宫内感染的Ig是

左向右分流型心脏病是

某投资者通过场外(某银行)投资1万元申购某上市开放式基金，假设基金管理人规定的申购费率为1．5％，申购当日基金份额净值为1．025元，则其申购手续费为()。

为各项工作提供必要警用装备、设施、器材、工具、服务等属于()。

Afewcommonmisconceptions.Beautyisonlyskin-deep.One’sphysicalassetsandliabilitiesdon’tcountallthatmuchinamana

Cityresident:Thesenewdigitalelectronicbillboardsshouldbebannedforlightpollutionsincetheyaremuchtoobright.Out

income

Whatarethestudentsmainlydiscussing?

Theroaddepartmentapologizedforanyinconveniencecausedwhileroadimprovementswereinprogress

在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这。填入画横线部分最恰当的一项是：

在公众对不同信息源的信任层级排序中，来自政府的消息历来以权威性和居于前列。同样是传谣，谣言经政府官微传播后破坏力更强，这。填入画横线部分最恰当的一项是：