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

admin2019-08-15 78

问题关于堆的一些问题：
(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)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

在一个双链表中，在p结点之前插入q结点的操作是()。

某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。

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

求函数y=(x>0)哪一点上的切线与直线y=x成60°角?

下列各项中，除哪项外，均是大定风珠的组成中药物

患者女，25岁，近来发热、乏力、体重下降、关节肌肉疼痛来院就诊。查体：面部可见紫红色蝶形红斑，抗Sm抗体阳性。可能会引起此病的因素中哪项不正确

某宗地估价用了4种估价方法，其评估结果为1000元/平方米、1040元/平方米、980元/平方米、1020元/平方米，经分析可确定各自权重为0.4、0.3、0.2、0.1，则采用加权平均法确定其评估结果为()元/平方米。

我国现行《港口工程可靠性设计统一标准》GB5158规定，永久性港口工程结构的设计使用年限为()年。

2009年2月2日，甲与乙签订了一份租赁合同，合同中约定：甲将自己唯一的挖掘机租给乙，租期为2009年3月1日至2010年3月1日。但是在2009年2月25日甲却将此挖掘机租给了丙，租期为2009年2月25日至2009年6月25日，则()。

汉高祖刘邦想废太子(吕后所生长子，即汉惠帝刘盈)，而立戚姬之子刘如意为新太子。御史大夫周昌说：“臣口不能言，然臣期期知其不可。陛下欲废太子，臣期期不奉诏。”周昌极力反对汉高祖废太子的原因是()。

中国吝啬鬼形象的典型代表人物是()。

国防精神是民族之魂，国防精神既是建设强大国防的思想基础，又是社会主义精神文明建设的重要组成部分，同时也是国家经济建设的巨大动力。国防精神是指一个国家的公民抵御外侮、反抗侵略，维护()的强烈意识。

Publicimagereferstohowacompanyisviewedbyitscustomers,suppliersandstockholders,bythefinancialcommunity,bythe

计算机408

学硕统考专业

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：建隆二年，赵匡胤采取了()的措施，收夺武将的兵权

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱，其基本理由是他们()

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：对于二里头文化的发现的意义，下列选项表述最准确的是()

下列选项中，不属于西汉农业发展状况的是()

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

在一个双链表中，在*p结点之前插入*q结点的操作是()。

某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。

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

求函数y=(x>0)哪一点上的切线与直线y=x成60°角?

下列各项中，除哪项外，均是大定风珠的组成中药物

患者女，25岁，近来发热、乏力、体重下降、关节肌肉疼痛来院就诊。查体：面部可见紫红色蝶形红斑，抗Sm抗体阳性。可能会引起此病的因素中哪项不正确

某宗地估价用了4种估价方法，其评估结果为1000元/平方米、1040元/平方米、980元/平方米、1020元/平方米，经分析可确定各自权重为0.4、0.3、0.2、0.1，则采用加权平均法确定其评估结果为()元/平方米。

我国现行《港口工程可靠性设计统一标准》GB5158规定，永久性港口工程结构的设计使用年限为()年。

2009年2月2日，甲与乙签订了一份租赁合同，合同中约定：甲将自己唯一的挖掘机租给乙，租期为2009年3月1日至2010年3月1日。但是在2009年2月25日甲却将此挖掘机租给了丙，租期为2009年2月25日至2009年6月25日，则()。

汉高祖刘邦想废太子(吕后所生长子，即汉惠帝刘盈)，而立戚姬之子刘如意为新太子。御史大夫周昌说：“臣口不能言，然臣期期知其不可。陛下欲废太子，臣期期不奉诏。”周昌极力反对汉高祖废太子的原因是()。

中国吝啬鬼形象的典型代表人物是()。

国防精神是民族之魂，国防精神既是建设强大国防的思想基础，又是社会主义精神文明建设的重要组成部分，同时也是国家经济建设的巨大动力。国防精神是指一个国家的公民抵御外侮、反抗侵略，维护()的强烈意识。

Publicimagereferstohowacompanyisviewedbyitscustomers,suppliersandstockholders,bythefinancialcommunity,bythe

在一个双链表中，在p结点之前插入q结点的操作是()。