2. 计算机
  3. 阅读以下说明，将应填入(n)处的字句写在答卷纸的对应栏内。 【说明】 下面的程序为堆排序程序，其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的，是在主函数中说明

阅读以下说明，将应填入(n)处的字句写在答卷纸的对应栏内。 【说明】 下面的程序为堆排序程序，其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的，是在主函数中说明

admin2009-02-15  79
问题 阅读以下说明，将应填入(n)处的字句写在答卷纸的对应栏内。

【说明】
   下面的程序为堆排序程序，其中函数adjust(i,n)是把以R(1≤i≤┕i/2┙)为根的二叉树调整成堆的函数，假定R的左、右子树已经是堆，程序中的，是在主函数中说明的结构数组，它含有要排序的n个记录。
   【程序】
   Void adjust(i，n)
   Int i，n；
      {
     iht k,j;
     element extr;
     extr=r;
     k=i;
     j=2*i;
     while (j＜=n )
     {if ((j＜n) && (r[j].key＜r[j+1].key))
       (1);
     if (extr. key＜r[j].key)
     {
     r[k]=r[j];
     k=j;
       (2);
     }
     else
       (3);
     }
     r[k]=extr;
     }
     /*让i从┗i/2┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。*/
     void heapsort (r,n)
     list r;
     int n;
     {
     int i,1;
     element extr;
     for (i=n/2;i＞=1;- -i)
       (4);               /* 建立初始堆*/
     for (k--n;k＞=2;k- -)
     {
     extr=r[1];
     r[1]=r[k];
     r[k]=extr;
       (5);
     }
     }
选项
答案(1)j++ (2)j*=2或j=k*2 (3)j=n+1或break (4)adjust(i,n) (5)adjust(1,k-1)
解析 函数adjust(i,n)是把以R(1≤i≤┗i/2┛)为根的二叉树调整成堆的函数，假定R的左、右子树已经是堆，程序中的r是在主函数中说明的结构数组，它含有要排序的n个记录。
   Void adjust(i,n)
   Int i,n；
   {
      int k,j;
     element extr;
     extr=r;
     k=i;
     j=2*i;
     while(j＜=n)
     {if((j＜n)&&(r[j].key＜r[j+ 1].key))
     j++;
     if(extr.key＜r[j].key)
     {
     r[k]=r[j];
     k=j;
     j*=2;
     }
     else
     j=n+1;
     }
     r[k]=extr;
     }
     /* 让i从┗i/2 ┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。堆排序程序heapsort 如下*/
         void heapsort(r,n)
         list r;
          int n;
          {
          int i,l;
          element extr;
          for (i=n/2;i＞= 1 ;--i)
          adjust(i,n);   /*建立初始堆*/
          for(k=n;k＞=2;k--)
          {
          extr=r[1];
          r[1]=r[k];
          r[k]=extr;
          adjust(1,k-1);
          }
          }
    函数heapsoff的第一个for循环建立初始化。没待排序的n个记录组成—棵深度为h的完全二叉树，因此有2h-1＜n≤2h+1-1，即2h≤n＜2h+1。完全二叉树的第i层(设根结点的层次为0)上最多有2i个结点，对每个非叶结点，都要调用过程adjust，同时可能移动结点(向下移动)，第i层上的结点可能要移动的最大距离为h-i，若设向下移动一层花费的时间为c，则第i层2i个结点调整的时间最多为c*(h-i)*2i建立初始堆的全部时间应是：
   令j=h-1，则i=h-j，所以有：
   对第二个for循环，调用adjust函数n-1次，每次总是由根向下调整，调整的最大距离为log2n(实际上，调整的距离是逐渐变小的)，所以总的时间不多于c*(n-1)log2n＝O(log2n)．堆排序总的时间为：
   O(n)+O(nlog2n)=O(max(n,n log2n))=O(n log2n)
   算法需要的存储空间是存储n个记录的数组以及少量暂存单元。
   堆排序算法是不稳定的。
转载请注明原文地址:https://www.kaotiyun.com/show/bMDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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