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

admin2019-08-15 65

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

严复翻译的《天演论》一书的出版时间是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题后晋一个节度使说：“天子宁有种耶?兵强马壮者为之!”这说明五代十国分裂局面的实质是()

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

以下叙述不正确的是()。

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

循环队列用数组A[0．．m～1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为()。

下面关于进程的叙述中，正确的是()。

在使用信号量机制实现互斥时，互斥信号量的初值一般为()：而使用信号量机制实现同步时，同步信号量的初值一般为()。

下列哪些是使用呼吸机的护理要点（）

对放射敏感性的理解，正确的是

搜集有关基准地价的资料，包括搜集估价对象宗地所在城镇的()。

有关部门在对一在建住宅小区工程的行政执法联合检查中发现，该工程尚未取得施工许可证，也未取得工程规划许可证，施工图设计文件也未按规定经过审查。根据《建筑工程施工许可管理办法》规定，可以()。

在我国支付清算网络体系中，起到中枢作用的系统有()。

两个同心圆线圈，大圆半径为R，通有电流I1；小圆半径为r，通有电流I2，方向如图3。若r＜＜R(大线圈在小线圈处产生的磁场近似为均匀磁场)，当它们处在同一平面内时，小线圈所受磁力矩的大小为()。

下列选项中，哪一行为构成正当防卫?()

什么是资产负债表日后事项?如何区分资产负债表日后调整事项和非调整事项?