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

admin2019-08-01 44

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式，最早提出这种方式的是()。

试述1929~1933年经济危机的根源和影响。

在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。

标志着整风运动开始向反“右派”斗争转变的重要文件是()。

下列哪两个国家是第二次工业革命的发源地和“中心”?

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

基督教产生的时间是()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

A．随机尿B．晨尿C．餐后尿D．24小时尿E．3小时尿适用于尿液白细胞排泄率检查的标本是

腹部平片示左肾下极成堆沙粒样不透光阴影，排泄性尿路造影示左肾下盏盏颈狭窄，下盏扩张呈囊袋状，最适合的手术方式

中频电疗法不包括

清理通风不良的阴沟时，可能接触到的有害气体是

直接损伤冲任，导致妇科疾病的是：

下列有关固定资产的相关内部控制的说法中，不正确的有()。

物流作业区是开展物流活动的核心区域，规划的重点是对物流作业设备的规划设计与选用。（）

医务社会工作者常用表单来记录整个服务过程，这些表单包括哪些?()

下列关于《中华民国刑法》中保安处分的说法，错误的是()。