2. 计算机
  3. 阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。 【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot时，采用从left、right和mid=[(left+right)/2]中取中间值，并交换到right位置的办

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。 【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot时，采用从left、right和mid=[(left+right)/2]中取中间值，并交换到right位置的办

admin2009-02-15  38
问题 阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。
【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot时，采用从left、right和mid=[(left+right)/2]中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为T，left和right是待排序子区间的最左端点和最右端点。
void quicksort (int a[], int left, int right) {
     int temp;
  if (left＜right)  {
     hat pivot = median3 (a, left, right);                   //三者取中子程序
     int i = left, j = right-1;
     for(;;){
       while (i ＜j && a ＜ pivot) i++;
       while (i ＜j && pivot ＜ a[j]) j--;
       if(i＜j){
           temp = a;  a[j] = a;  a = temp;
           i++; j--;
     }
       else break;
   }
    if (a ＞ pivot)
          {temp = a; a = a[right]; a[right] = temp;}
    quicksort(  (1)  );                                     //递归排序左子区间
    quieksort(a,i+1 ,right);                                //递归排序右子区间
}
}
void median3 (int a[], int left, int right)
{ int mid=(2);
   int k = left;
   if(a[mid] ＜ a[k])k = mid;
   if(a[high] ＜ a[k]) k = high;                      //选最小记录
   int temp = a[k]; a[k] = a[left]; a[left] = temp;  //最小者交换到 left
   if(a[mid] ＜ a[right])
       {temp=a[mid];  a[mid]=a[right];  a[right]=temp;}
}
消去第二个递归调用 quicksort (a,i+1,right)。 采用循环的办法:
void quicksort (int a[], int left, int right) {
            int temp;  int i,j;
         (3)  {
               int pivot = median3(a, left, right);             //三者取中子程序
               i = left; j = righi-1;
               for (;; ){
               while (i＜j && a ＜ pivot)i++;
               while (i＜j && pivot ＜a[j]) j--;
               if(i ＜j) {
                    temp = a; a[j]; = a; a=temp;
                    i++; j--;
           }
               else break;
        }
          if(a＞pivot){(4);a=pivot;}
          quicksoft ((5));                //递归排序左子区间
          left = i+1;
       }
     }
选项
答案(1)a，left，i-1 (2)(left+right+1)/2 (3)while(left＜right) (4)a[right)=a[i] (5)a，left, i-1
解析 (1)a，left，i-1
   递归排序左子区间，从left到i-1元素，不包括i元素。
(2)(left+right+1)/2
    三者取中子程序median3(a，left，right)，取基准记录pivot时，采用从left、right和 mid=[(left+right)/2]中取中间值，并交换到right位置的办法。
(3)while(left＜right)
   循环直到left和right相遇。
(4)a[right)=a
   若a＞pivot则让a[right]=a而让a=pivot；。
(5)a，left, i-1
   递归排序左子区间，从left到i-1元素，不包括i元素。
转载请注明原文地址:https://www.kaotiyun.com/show/xMDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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