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

admin2017-01-04 70

问题关于堆的一些问题：
(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://kaotiyun.com/show/SLRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

论述太平天国起义对晚清政局的影响。(中南大学2014年中国近代史真题)

关于“尊王攘夷”运动，不正确的说法是()。

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

世界天文史上最早实地测量子午线的记录是由谁进行的?()

公元前356年和前350年，()先后两次任用商鞅进行变法。

元朝在中央设置中书省、地方则设置行中书省，其目的是()。

詹天佑自主设计修建了中国第一条铁路是在()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

在协议数据单元中，控制信息所不包括的内容是()。

用量限为500V的直流电压表测量有效值为220V的工频电压，指针将指示在()。

χ2＋Y2＝1在空间表示________曲面。

A．镰形红细胞B．环形红细胞C．红细胞大小不均匀D．泪滴形红细胞E．靶形红细胞骨髓纤维化常见的是

中庭空间的特点不包括()。

会计信息系统的网络组成部分包括()。

证券登记结算公司履行的职能包括(　　)。

WhatdoesJimthinkofcricket?

计算机408

学硕统考专业

论述太平天国起义对晚清政局的影响。(中南大学2014年中国近代史真题)

关于“尊王攘夷”运动，不正确的说法是()。

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

世界天文史上最早实地测量子午线的记录是由谁进行的?()

公元前356年和前350年，()先后两次任用商鞅进行变法。

元朝在中央设置中书省、地方则设置行中书省，其目的是()。

詹天佑自主设计修建了中国第一条铁路是在()。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

在协议数据单元中，控制信息所不包括的内容是()。

用量限为500V的直流电压表测量有效值为220V的工频电压，指针将指示在()。

χ2＋Y2＝1在空间表示________曲面。

A．镰形红细胞B．环形红细胞C．红细胞大小不均匀D．泪滴形红细胞E．靶形红细胞骨髓纤维化常见的是

中庭空间的特点不包括()。

会计信息系统的网络组成部分包括()。

证券登记结算公司履行的职能包括( )。

WhatdoesJimthinkofcricket?

证券登记结算公司履行的职能包括(　　)。