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

admin2018-08-12 46

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下列选项中不属于《国际联盟盟约》内容的是()。

对《魏玛宪法》的内容和影响叙述不正确的是()。

以海地和巴西为例，论述19世纪拉丁美洲民族独立运动类型多样化的历史依据。

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。

操作系统采用页式存储管理方法，要求()。

作业成本法的基本理念有()。

翼外肌痉挛的主要临床特征是

由股票的上涨家数和下降家数的比值推断股票市场多空双方力量对比的技术指标是(　　)。

下列人员中，属于车辆购置税纳税义务人的是()。

信托是随着商品经济的发展而出现的一种财产管理制度，其本质是()。

德育对象千差万别，德育目标、任务、职责多种多样，这突出体现了德育工作者劳动的()

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

【胡格诺战争】(FrenchwarsofReligion)南京大学1999年世界古代中世纪史真题

WhydoesoldJakelookterriblydepressed?

计算机408

学硕统考专业

下列选项中不属于《国际联盟盟约》内容的是()。

对《魏玛宪法》的内容和影响叙述不正确的是()。

以海地和巴西为例，论述19世纪拉丁美洲民族独立运动类型多样化的历史依据。

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。

操作系统采用页式存储管理方法，要求()。

作业成本法的基本理念有()。

翼外肌痉挛的主要临床特征是

由股票的上涨家数和下降家数的比值推断股票市场多空双方力量对比的技术指标是( )。

下列人员中，属于车辆购置税纳税义务人的是()。

信托是随着商品经济的发展而出现的一种财产管理制度，其本质是()。

德育对象千差万别，德育目标、任务、职责多种多样，这突出体现了德育工作者劳动的()

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

【胡格诺战争】(FrenchwarsofReligion)南京大学1999年世界古代中世纪史真题

WhydoesoldJakelookterriblydepressed?

由股票的上涨家数和下降家数的比值推断股票市场多空双方力量对比的技术指标是(　　)。