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

admin2018-08-12 61

问题关于堆的一些问题：
(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://www.kaotiyun.com/show/rMRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

三大战役的先后顺序是()

为了巩固政治统治、发展经济，南京国民政府采取了一系列的财政、经济改革，下列选项中不正确的是()

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

下列属于中国近代军阀共同特点的是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

论述隋朝加强中央集权和巩固统一的措施。

《凡尔赛条约》中，战胜国以()方式处置德国的全部海外殖民地。

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

针对哮喘病因的治疗措施是

2006年9月成立的期货交易所是()。

下面为人体基本轴的是()。

特发性心肌炎是

妇科门诊，一位35岁的已婚女性，主诉外阴瘙痒。阴道检查时见白带多而稀薄，呈灰黄色泡沫状，擦去白带见阴道黏膜有散在的红点。根据此女病人的临床表现，考虑必须做的特殊化验项目是

已知城市某一水平输水管，管的长度l=4000m，管的直径d=250mm，管的沿程阻力系数λ=0．023，若要保证输水管通过的流量Q=50L／s，则输水管进口所需要的水压是()。

在信息处理中，首先应()。

学生回答选择题时所使用的记忆过程主要是()

A、大学生学习B、大学生住宿C、大学生洗衣服D、大学生相处B根据短文内容，可知短文谈论的是大学生住宿问题，所以选B。