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

admin2018-08-12 47

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

选项

答案(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：由于第i层上的结点数至多是2^i-1，以它为根的二叉树的深度为h一i+1，则调用[*92]次筛选算法时总共进行的关键字比较次数不超过下式之值： [*] 提示：此题考查的知识点是堆的基本定义及效率。堆定义为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/rMRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下面哪项条约没有涉及德国的赔款问题?()

“国际工人协会”宣布成立后，10月协会选出了第一任主席，他是()。

雍正皇帝为加强专制主义皇权而采取的主要措施包括()。①扩充内阁六部②增设南书房③撤销议政处④增设军机处

在1875年宪法中关于法国立法权的叙述，不正确的是()。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

有关斯巴达国家建立传说的社会改革是()。

下列选择中，()不是操作系统关心的主要问题。

将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。

票据上有伪造、变造的签章的，不影响票据上其他真实签章的效力，下列说法错误的是：()

中共中央2015年中央经济工作会议提出推进()，是适应我国经济发展新常态的必然要求。

Inafamilywheretherolesofmenandwomenarenotsharplyseparatedandwheremanyhouseholdtasksaresharedtoagreateror

外科治疗门静脉高压症最主要的目的是()。

关于中药饮片的储存与养护叙述不正确的是

工程建设项目后评价阶段的主要内容为()。

在长期中,总供给曲线是一条()。

下列关于现代服务的说法中，正确的是()。

A、 B、 C、 D、 D