2. 考研
  3. 最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 (1)画出在图中插入关键字为5的结点后的

最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 (1)画出在图中插入关键字为5的结点后的

admin2017-01-04  44
问题 最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。

    (1)画出在图中插入关键字为5的结点后的最小最大堆。
    (2)画出在图中插入关键字为80的结点后的最小最大堆。
    (3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。
选项
答案此题考查的知识点是堆的算法。将插入的元素放到最后，然后调整，方法同第13题。 (1)加入关键字值为5的结点后，最小最大堆如下图。 [*] (2)加入关键字值为80的结点后，最小最大堆如下图。 [*] (3)从插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元素所在层次数，以确定其插入层是最大层还是最小层。若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直到满足小堆定义或到达根结点：若插入元素不小于双亲，则调大堆，直到满足大堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖先调堆，直到满足小堆定义或到达根结点。 void MinMaxHeapIns(RecType R[]，int n){ ／／假设R[1．．n一1]是最小最大堆，插入第n个元素，把R[1．．n]调成最小最大堆 j=n；R[0]=R[j]； h=log2n+1； ／／求高度 if(h％2==0){ ／／插入元素在偶数层，是最大层 i=n／2； if(R[0]．key＜R[i]．key){ ／／插入元素小于双亲，先与双亲交换，然后调小堆 R[j]=R[i]； j=i／4； while(j＞0&&R[j]＞R[i]){ R[i]=R[j]；i=j；j=i／4；} ／／调小堆 R[i]=R[0]i } else{ ／／插入元素大于双亲，调大堆 i=n；j=i／4； while(j＞0&&R[j]＜R[i]){R[i]=R[1]；i=j；j=i／4；} R[i]=R[0]； } } else{ ／／插入元素在奇数层，是最小层 i=n／2： if(R[0]．key＞R[i]．key){ ／／插入元素大于双亲，先与双亲交换，然后调大堆 R[j]=R[i]； j=i／4； while(j＞0&&R[j]＜R[i]){ R[i]：R[j]=i：j；j=i／4； } ／／调大堆 R[i]=R[0]； } else{ ／／插入元素小于双亲，调小堆 i=n；j=i／4； while(j＞0&&R[j]＞R[i]){ R[i]=R[j]；i=j；j=i／4；} R[i]=R[0]； } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/9QRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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