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

admin2019-08-15 32

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

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()

以下是二战后美国经济发展的排列组合，其中最正确的一组是()

【纳赛尔】(GamalAbdelNasser，1918—1970)北京师范大学2000年世界现当代史真题；南京大学2013年国际关系史真题

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

计算机系统采用补码运算是为了()。

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

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

以下关于CPU的叙述中，错误的是()。

A．黑珠B．两眦血络C．眼睑D．白睛E．瞳仁根据眼的五轮分属，属肺的是

前后所签订的三个合同(　　)。飞龙公司的出资(　　)。

下列关于飞机库防火设计中电气设计的说法错误的是()。

商业银行的整体风险控制环境的四项要素不包括()。

一般银行系统默认的基金分红形式是()。

潜水艇能够上浮和下沉是通过_______来实现的。

在侦查活动中，只有在为了确定下列哪些问题时，才可以对被害人、犯罪嫌疑人的人身进行检查（）。

光纤通信就是利用光波在光导纤维中传递各种信息，光纤通信的优点有()。

HadWilliamreceivedfivemorevotesinthelastelection,he______ourchairmannow.

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：下列有关“甲骨文”的表述，不确切的是()

以下是二战后美国经济发展的排列组合，其中最正确的一组是()

【纳赛尔】(GamalAbdelNasser，1918—1970)北京师范大学2000年世界现当代史真题；南京大学2013年国际关系史真题

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

计算机系统采用补码运算是为了()。

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

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

以下关于CPU的叙述中，错误的是()。

A．黑珠B．两眦血络C．眼睑D．白睛E．瞳仁根据眼的五轮分属，属肺的是

前后所签订的三个合同( )。飞龙公司的出资( )。

下列关于飞机库防火设计中电气设计的说法错误的是()。

商业银行的整体风险控制环境的四项要素不包括()。

一般银行系统默认的基金分红形式是()。

潜水艇能够上浮和下沉是通过_______来实现的。

在侦查活动中，只有在为了确定下列哪些问题时，才可以对被害人、犯罪嫌疑人的人身进行检查（）。

光纤通信就是利用光波在光导纤维中传递各种信息，光纤通信的优点有()。

HadWilliamreceivedfivemorevotesinthelastelection,he______ourchairmannow.

前后所签订的三个合同(　　)。飞龙公司的出资(　　)。