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

admin2019-08-15 62

问题关于堆的一些问题：
(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

学硕统考专业

义和团发展到高潮的标志是()

卡诺莎事件

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。

路由器采用()方式来发送IP分组。

指令字长为12位，每个地址码为3位，采用扩展操作码的方式，设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。

设有A，B，C，D4台主机都处在同一个物理网络中，A主机的IP地址是192．155．28．112，B主机的IP地址是192．155．28．120，C主机的IP地址是192．155．28．135，D主机的IP地址是192．155．28．202。共

脱氧剂的主要作用是对熔渣和焊缝脱氧。

患者男，28岁。有吸毒史，HIV、HBV抗体均阳性，近2天口腔黏膜出现白色斑片，该患者最有可能感染

下列哪项是痰湿内阻所致头晕的表现

男，50岁。否认吸烟史。胸部X线片见左上肺孤立、球形、分叶状阴影，直径约3cm。初步诊断肺癌，可能的病理类型是()

下列属于附子的炮制品的是()。

WholesalepricesinJulyrosemoresharplythanexpectedandatafasterratethanconsumerprices,【C1】______thatbusinesseswer

在用例建模的过程中，若几个用例执行了同样的功能步骤，这时可以把这些公共步骤提取成独立的用例，这种用例称为(110)。在UML的用例图上，将用例之间的这种关系标记为(111)。(111)

ThefirstEnglishcolonyinAmericawasfoundedin______in1607.

Accordingtothesurvey,______percentofforeignstudentshavenoAmericanfriends.

Onelunchtime,MayWardwasdoinghershoppinginalocalsupermarket,whenshesuddenlyslippedandfell.Shewasbadlyshaken