2. 计算机
  3. 阅读下列说明、流程图和算法进行填空。 下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，

阅读下列说明、流程图和算法进行填空。 下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，

admin2010-02-13  41
问题 阅读下列说明、流程图和算法进行填空。
   下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以4为基准数的划分过程如图8-34所示。
   算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
   算法如下。
   void sort(int A[]，int L，int H)  {
      if (L＜H)  {
         k=p(A,L,H)；    //p()返回基准数在数组A中的下标
         sort((4))；    //小于基准数的元素排序
         sort((5))；    //大于基准数的元素排序
      }
   }
选项
答案(1)j--;(2)i++;(3)A[i]←pivot 或 A[j]←pivot;(4)A, L, k-1;(5)A, k+1,H
解析 本题的快速排序思想是：首先，以待排序序列的第1个元素为基准，将序列中所有小于基准元素的元素排到基准元素的一边，将序列中所有大于基准元素的元素排到基准的另一边。具体放在哪一边，要根据排序的升降而定。这样，就以基准元素为界，将原序列划分成了两个部分，然后再分别对这两个部分递归进行快速排序，直到无法再划分为止。这样，整个序列就被排序了。
   题目中已经给出了快速排序的划分算法，我们要做的就是将划分算法的流程图和
快速排序的递归函数补充完整。
   先看来流程图，pivot←A[low]就是将数组A的第1个元素赋给pivot，作为基准元素。然后，分别将数组的下界和上界赋给i和j(i←low;j←high)，我们可以将 i和j理解为分别指向数组首和尾的两个指针。注意，其中的i指向的位置是基准元素所在位置。接下来是一个循环，循环条件为i＜j。
   在循环体中，首先从后往前寻找比基准元素小的元素，这是通过一个子循环来完成的。循环条件i＜j&&A[j]＞pivot的意思是，如果j所指的元素比基准元素大，并且j还在i的后面的话，我们应该把j往前移动1位，所以第1空应该填j--或其他等价形式。如果找到比基准元素小的元素或者j已经移动到i的位置了，则循环结束。下面的语句A←A[j]刚就是将找到的元素移动到i所指位置。注意，现在可以将j所指位置看作是基准元素的位置，但是可以暂时不用把基准元素赋给A[j]。接下来的子循环跟前面的很类似，循环条件是i＜j&&A＜pivot，如果i所指元素小于基准元素，且i并没有超过j，那么就应该将i往前移动1位，所以第2空应该填i++或其他等价的形式。直到i＞=j(i和j已经重合，所有元素都遍历完了)，或者A＞=pivot(在基准元素位置j的左边找到比基准元素大的元素了)，则该子循环结束。然后执行A[j]←A，将找到的元素跟基准元素交换位置，不过基准元素可以暂时不用赋给A，因为它还要跟其他元素交换位置。
   如果子循环不是因为i＞=j结束的，那么外循环就会继续。直到所有大于基准元素的元素都被排到基准元素后面，小于基准元素的元素都被排到基准元素前面。外循环结束时，i和j一定是重合的，现在可以把基准元素写入它们所指的位置中去了。所以，第3空可以填A←pivot或A[j]←pivot。
   现在来看快速排序的递归函数sort()，在函数中首先判断下界L是否小于上界H，这一点很重要，因为它是递归函数回溯的条件。如果L＜H，则表示需排序的元素个数不为0。在if子句中，首先调用前面分析过的划分算法p()函数，将数组A的 L～H范围进行一次划分，然后递归调用了两次sort()。很显然，这两次应该分别对划分出的前半部分和后半部分分别排序。所以，第(4)、(5)空应该分别填A,L, k-1和A,k+1,H,或者把它们的位置交换也可以。
转载请注明原文地址:https://kaotiyun.com/show/TpjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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