首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2017-01-04
111
问题
关于堆的一些问题:
(1)堆的存储表示是顺序的,还是链接的?
(2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大0表示法)?
选项
答案
(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点,在最下两层上。 (3)在建含有n个元素、深度为h的堆时,其比较次数不超过4n,推导如下: 由于第i层上的结点数至多是2
i-1
,以它为根的二叉树的深度为h一i+1,则调用[n/2]次筛选算法时总共进行的关键字比较次数不超过下式之值: [*] 提示:此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K
1
,K
2
,…,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/SLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
分析南斯拉夫走上自治道路的原因。
1907年召开的第二国际斯图加特代表大会上,争论最激烈的问题是()。
中华人民共和国恢复了在联合国合法席位的时间是()。
下列关于清朝军机处的叙述,不正确的是()。
为了巩固政治统治、发展经济,南京国民政府采取了一系列的财政、经济改革,下列选项中不正确的是()
下列关于罗马共和国政治制度的叙述,不正确的是()。
我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是()。
可重定位内存分区的目的为了()。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统并不一定死锁。
操作系统技术中临界区是指()。
随机试题
成人上腹部CT检查前30分钟口服阳性对比剂的量是
为了更准确地了解唇舌部位的病变范围和性质,临床检查时一般用
有关改善羊水过多压迫症状的护理措施,以下错误的是()
消防喷头的最少布置数量:
根据《工程建设项目施工招标投标办法》(国家八部委局第30号令),工程施工招标投标活动依法由()负责,任何单位和个人不得以任何方式非法干涉工程招标投标活动。
关于贷款重组的方式,下列说法正确的有()。
民事主体在法律允许的范围内有完全的意志的自由,自主实施民事法律行为,参加民事法律关系,任何单位和个人都不得非法干预。这体现了()。
人体必需的六类营养素中有三大热能营养素,在体内经过氧化可能产生能量,下列不属于热能营养素的是()。
若系统中有5个并发进程涉及某个相同的变量A,则变量A的相关临界区是由几个临界区构成?
ItissaidthatinEnglanddeathispressing,inCanadainevitableandinCaliforniaoptional.Smallwonder.Americans’lifeexp
最新回复
(
0
)