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

admin2019-08-01 86

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

选项

答案(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://kaotiyun.com/show/S3Ci777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

两河流域分为两部分，其中南部称为()。

下列哪一个不是罗马王政时代的管理机构?()

二次大战后，主要资本主义国家经历了增长时期，首先开始这个进程的国家是()。

在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。

论述雅典和罗马通过对外扩张成为帝国的过程，并分析雅典帝国短暂而罗马帝国长久的原因。

三国同盟和三国协约两大军事集团最终形成的时间是()。

制瓷业是光彩夺目的一个手工业部门，北宋的制瓷业的重心在黄河流域和中原地区。回答问题：()创于唐，盛于北宋，以白瓷著名，为宋代印花白瓷的精品

1947年，刘邓大军千里跃进大别山，揭开了战略反攻的序幕。据此回答问题：中共中央将战略决战的方向首先指向的是()

假脱机技术(SPOOLing)中，被利用来做虚拟设备的是()。

普希金在波尔金诺时完成的诗体长篇小说是()

化脓性炎组织内浸润的炎细胞主要是

麻黄连翘赤小豆汤合五味消毒饮治疗水肿的证候是

外科的急性感染是指病程在

对于犯罪嫌疑人、被告人有权获得辩护原则理解错误的是：()

国际货物买卖合同中的“溢短装条款”是指：()

成本分析的方法主要有()。

人们常用“小荷才露尖尖角，早有蜻蜓立上头”来形容初露头角的新人。下面与此蕴含相同哲理的诗句有()。

列宁指出：社会主义将来是什么样子，什么时候达到完备的形式，这些我们不知道，也不能说。只有未来的建设者才能具体描述未来的样子。我们现在所知道的只是一些基本原则。列宁所说的这些基本原则是()

计算并填写下表。