2. 考研
  3. 关于堆的一些问题： 对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

关于堆的一些问题： 对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?

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

计算机408

学硕统考专业

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