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

admin2019-08-15 42

问题关于堆的一些问题：
(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://jikaoti.com/ti/aMGjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

清政府在鸦片战争中战败的主要原因是()。

雅尔塔会议和波茨坦会议在内容上的一致之处是()。

卡诺莎事件

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法)，分析其死锁的可能性并提出解决方案。Philosopheri：d0{wait(chopstick[i]；wait(ch

一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。

打开发动机盖，如果是电动机减速后直接驱动转向器，则为_______。

表证的发热特点是

[2013年，第1题]已知向量α＝(-3，-2，1)，β＝(1，-4，-5)，则｜α×β｜等于()。

关于自营业务的财产管理，下列说法正确的有(　　)。

某企业2014年至2019年历年产销量和资金变化情况如下表所示，2020年预计销售量为1500万件，请预计2020年的资金需要量。

元代中央最高行政机构为尚书省，多由太子兼任()

下列关于万方数据资源的说法中，正确的是()。

全国人大的最高监督权包括()

ConsideringhowjazzistranscribedinChinese(jueshi),youmaybemisledintoassumingthatitisanaristocraticculturalfor

Dearsir,ThankyouforyourletteronMarch15.Weknowthatyouwanttoorder10000piecesofRainbowRaincoatModel2.

计算机408

学硕统考专业

清政府在鸦片战争中战败的主要原因是()。

雅尔塔会议和波茨坦会议在内容上的一致之处是()。

卡诺莎事件

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法)，分析其死锁的可能性并提出解决方案。Philosopheri：d0{wait(chopstick[i]；wait(ch

一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。

打开发动机盖，如果是电动机减速后直接驱动转向器，则为_______。

表证的发热特点是

[2013年，第1题]已知向量α＝(-3，-2，1)，β＝(1，-4，-5)，则｜α×β｜等于()。

关于自营业务的财产管理，下列说法正确的有( )。

某企业2014年至2019年历年产销量和资金变化情况如下表所示，2020年预计销售量为1500万件，请预计2020年的资金需要量。

元代中央最高行政机构为尚书省，多由太子兼任()

下列关于万方数据资源的说法中，正确的是()。

全国人大的最高监督权包括()

ConsideringhowjazzistranscribedinChinese(jueshi),youmaybemisledintoassumingthatitisanaristocraticculturalfor

Dearsir,ThankyouforyourletteronMarch15.Weknowthatyouwanttoorder10000piecesofRainbowRaincoatModel2.

关于自营业务的财产管理，下列说法正确的有(　　)。