关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中，最多做多少次数据比

admin2017-01-04 123

问题关于堆的一些问题：
(1)堆的存储表示是顺序的，还是链接的?
(2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大0表示法)?

选项

答案(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：由于第i层上的结点数至多是2^i-1，以它为根的二叉树的深度为h一i+1，则调用[n／2]次筛选算法时总共进行的关键字比较次数不超过下式之值： [*] 提示：此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K₁，K₂，…，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://www.kaotiyun.com/show/SLRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

分析地理大发现在世界历史上的作用与地位。

1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。

共产国际“七大”决定加强各国共产党的自主性，主要是由于()。

洪秀全以宗教手段组织起义，主要利用的是()。

希腊雅典城邦的“民众法庭审判官由公民抓签选出，任期只有一年，每个公民一生中只能担任两次审判官的职务”。此规定()。

《凡尔赛条约》中，战胜国以()方式处置德国的全部海外殖民地。

我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是（）。

论述欧洲一体化的进程及影响。

某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是____。

男性，25岁，低热盗汗3个月，结核PPD实验(+)，行胸腔穿刺抽液，当抽取草黄色液体30ml时，患者突感头晕心悸，脸色苍白，四肢凉，查体发现脉搏细弱。此时应如何处理病人

如图所示，在上部为气体下部为水的封闭容器上装有U形水银测压计，其中1、2、3点位于同一平面上，其压强关系为：

《中华人民共和国安全生产法》第二十四条规定：“生产经营单位新建、改建、扩建工程项目的安全设施，必须与主体工程同时设计、同时施工、同时投入生产和使用。安全设施投资应当纳入(　　)”。

报关企业有下列情形之一的，适用D类管理：

(2016年)下列各项属于经济周期中萧条阶段采用的财务管理战略的有()。

2010年10月19日，我国发布了《xBRL，(可扩展商业报告语言)技术规范系列国家标准和通用分类标准》。下列财务管理环境中，随之得到改善的是()。(2011年)

IwillneverforgettheyearIwasabouttwelveyearsold.Mymothertoldusthatwewouldnotbe【16】Christmasgiftsbecausethe

计算机408

学硕统考专业

分析地理大发现在世界历史上的作用与地位。

1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。

共产国际“七大”决定加强各国共产党的自主性，主要是由于()。

洪秀全以宗教手段组织起义，主要利用的是()。

希腊雅典城邦的“民众法庭审判官由公民抓签选出，任期只有一年，每个公民一生中只能担任两次审判官的职务”。此规定()。

《凡尔赛条约》中，战胜国以()方式处置德国的全部海外殖民地。

我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是（）。

论述欧洲一体化的进程及影响。

某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是____。

男性，25岁，低热盗汗3个月，结核PPD实验(+)，行胸腔穿刺抽液，当抽取草黄色液体30ml时，患者突感头晕心悸，脸色苍白，四肢凉，查体发现脉搏细弱。此时应如何处理病人

如图所示，在上部为气体下部为水的封闭容器上装有U形水银测压计，其中1、2、3点位于同一平面上，其压强关系为：

《中华人民共和国安全生产法》第二十四条规定：“生产经营单位新建、改建、扩建工程项目的安全设施，必须与主体工程同时设计、同时施工、同时投入生产和使用。安全设施投资应当纳入( )”。

报关企业有下列情形之一的，适用D类管理：

(2016年)下列各项属于经济周期中萧条阶段采用的财务管理战略的有()。

2010年10月19日，我国发布了《xBRL，(可扩展商业报告语言)技术规范系列国家标准和通用分类标准》。下列财务管理环境中，随之得到改善的是()。(2011年)

IwillneverforgettheyearIwasabouttwelveyearsold.Mymothertoldusthatwewouldnotbe【16】Christmasgiftsbecausethe

《中华人民共和国安全生产法》第二十四条规定：“生产经营单位新建、改建、扩建工程项目的安全设施，必须与主体工程同时设计、同时施工、同时投入生产和使用。安全设施投资应当纳入(　　)”。