首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2017-01-04
85
问题
关于堆的一些问题:
(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
学硕统考专业
相关试题推荐
论述清初恢复、发展生产的措施
刘秀采取了哪些措施来增加皇权?
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
洪秀全以宗教手段组织起义,主要利用的是()。
在20世纪60年代末,日本发展成为资本主义世界第二号经济强国的诸多因素中,不包括()。
材料一1870年代初的南部,虽然也不时出现针对黑人的种族暴行,但在日常生活中,黑人基本能与白人同车船、共饭桌、游公园。但这种情况并没有持续多久。随着前白人奴隶主“重新夺回”南部各州政权,许多州在维护社会秩序名义下,制定了各种法律,规定黑人与白人必
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
实现一个经典的“读者一写者”算法时,若当前临界区中有读者访问,写者再来时必须在临界区外面等候,如果其后读者源源不断地到达,按策略他们均可以进入临界区,始终保持临界区中有读者访问,那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题,我们修改访问策略,
随机试题
公民、法人和其他组织对外交行为可以提起的行政诉讼()
法律的通过须经过法律制定机关代表中的一定法定人数的赞成,通常普通法律须经过全国人大代表的()
在集中式主存的阵列处理机中,处理单元数为4,为了使4×4的二维数组A的各元素aij(i=0~3,j=0~3)在行、列、主/次对角线上均能实现无冲突访问,请问数组各元素在存储器各分体(分体号从0开始)中的分布情况(假设a00已存放在分体号为3,体内地址为0
A.含硫氨基酸B.支链氨基酸C.芳香族氨基酸D.亚氨基酸缬氨酸是
患者,女,56岁。慢性肾衰患者。患者体质虚弱,活动受限,护士在为患者翻身时,操作错误的是
温和灸所属的灸法种类是()
小儿生长发育最快的阶段是
若某一企业的经营处于盈亏临界状态,错误的说法是( )。
“市卫生局:你局《关于拟录用高校硕士毕业生的函》(×卫函〔2002〕15号)收悉。”这是市人事局给卫生局所发的文。从文中的信息可以推断()
下列属于受教育者的义务的是()。
最新回复
(
0
)