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

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

admin2019-08-15  46
问题 关于堆的一些问题：
    (1)堆的存储表示是顺序的，还是链接的?
    (2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
    (3)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大0表示法)?
选项
答案(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下： 由于第i层上的结点数至多是2i-1，以它为根的二叉树的深度为h一i+1，则调用[n／2]次筛选算法时总共进行的关键字比较次数不超过下式之值： [*]2i-1×2(h一i)=[*]2i×(h一i)=[*]2h-j×j≤(2n)[*]j／2j≤4n 提示：此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K1，K2，…，Kn，当且仅当该序列满足如下性质(简称为堆性质)： (1)Ki≤K2i且Ki≤K2i+1或 (2)Ki≥K2i且Ki≥K2i+1(1≤i≤n)。Ki相当于二叉树的非叶结点，K2i则是左孩子，k2i+1是右孩子。
解析
转载请注明原文地址:https://jikaoti.com/ti/aMGjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)