关于堆的一些问题：对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

admin2019-08-01 26

问题关于堆的一些问题：
对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

选项

答案在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：由于第i层上的结点数至多是2^i-1，以它为根的二叉树的深度为h-i+1，则调用[n／2]次筛选算法时总共进行的关键字比较次数不超过下式之值： [*]

解析此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K₁，K₂，…，K_n，当且仅当该序列满足如下性质(简称为堆性质)：
(1)k_i≤K₂，且k_i≤K_2i+1或
(2)k_i≥K₂；且k_i≥K_2i+1(1≤i≤n)。k_i相当于二叉树的非叶结点，K_2i则是左孩子，k_2i+1是右孩子。

转载请注明原文地址:https://kaotiyun.com/show/HNCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

关于堆的一些问题：对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

计算机408

学硕统考专业

下列选项中，控制了西域政权的是()。

明清时期专制主义空前加强，据此回答问题：以下关于明朝“废行省、设三司”的措施评价最正确的是()

西汉初年代表黄老政治思想的著作，是陆贾的()。认为“道莫大于无为，行莫大于谨敬”。

1900年10月修订《英、德扬子协定》规定:将中国之江河及沿海各口岸各国贸易及其他正当经济活动，自由开放，毫无差别并知会各国。该协定:

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

下面元件存取速度最快的是()。

操作数地址存放在寄存器的寻址方式叫()。

在下列事件中，哪个不是设备分配中应该考虑的问题()。

呼吸链：

食管原位癌是指（）

复方鱼腥草片的功能是()。

根据生命周期曲线的变化，可以推断出处于()的产品，销售量将迅速增加；处于()的产品，销售量较为稳定；处于()的产品，销量急剧下降。

高层建筑的给水系统和热水系统必须进行合理的竖向分区并加设()。

开展小组工作实务的基础是小组工作的()。

ForanincreasingnumberofstudentsatAmericanuniversities,Oldissuddenlyin.Thereasonisobvious:thegrayingofAmerica

"AtBoozAllen,we’reshapingthefutureofcyber-security,"trumpetsarecruitingmessageonthewebsiteofBoozAllenHamilton

数据库的逻辑结构设计任务就是把转换为与所选用的DBMS支持的数据模型相符合的过程。

Childrenhavebeensaidtohavebrain-injuredchildsyndrome,hyperactive(极度活跃的)childsyndromeandattention-deficitdisorder

关于堆的一些问题： 对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

计算机408

学硕统考专业

下列选项中，控制了西域政权的是()。

明清时期专制主义空前加强，据此回答问题：以下关于明朝“废行省、设三司”的措施评价最正确的是()

西汉初年代表黄老政治思想的著作，是陆贾的()。认为“道莫大于无为，行莫大于谨敬”。

1900年10月修订《英、德扬子协定》规定:将中国之江河及沿海各口岸各国贸易及其他正当经济活动，自由开放，毫无差别并知会各国。该协定:

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

下面元件存取速度最快的是()。

操作数地址存放在寄存器的寻址方式叫()。

在下列事件中，哪个不是设备分配中应该考虑的问题()。

呼吸链：

食管原位癌是指（）

复方鱼腥草片的功能是()。

根据生命周期曲线的变化，可以推断出处于()的产品，销售量将迅速增加；处于()的产品，销售量较为稳定；处于()的产品，销量急剧下降。

高层建筑的给水系统和热水系统必须进行合理的竖向分区并加设()。

开展小组工作实务的基础是小组工作的()。

ForanincreasingnumberofstudentsatAmericanuniversities,Oldissuddenlyin.Thereasonisobvious:thegrayingofAmerica

"AtBoozAllen,we’reshapingthefutureofcyber-security,"trumpetsarecruitingmessageonthewebsiteofBoozAllenHamilton

数据库的逻辑结构设计任务就是把转换为与所选用的DBMS支持的数据模型相符合的过程。

Childrenhavebeensaidtohavebrain-injuredchildsyndrome,hyperactive(极度活跃的)childsyndromeandattention-deficitdisorder

关于堆的一些问题：对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?