2. 计算机
  3. 阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 下面的流程图1—5用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数

阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 下面的流程图1—5用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数

admin2013-01-05  69
问题 阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。
   【说明】
   下面的流程图1—5用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：

【算法说明】
   将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数血p(int A[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，iht L；int H)的功能是实现数组A中元素的递增排序。
   【算法】
   void sort(int A[]，int1，int H)  {
           if  (L＜H)  {
        k=p(A, L, R)：    //p()返回基准数在数组A中的下标
        sort((4))；    //小于基准数的元素排序
        sort((5))；    //大于基准数的元素排序
        }
   }
选项
答案(1)j-- (2) i++ (3)A[i]←pivot或[j]←pivot (4)A，L，k-1或A，L，k (5)A，k+I，H或A，k，H
解析 题目考查快速排序算法。快速排序采用了一种分治的策略，通常称为分治法，其基本思想足：将原问题分解为若干个规模更小，但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
   快速排序的具体过程为：第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成2组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大十该排序码，并把该记录排在这2组中间，这个过程称为一次划分。第二步，采用同样的方法，对划分出来的2组元素分别进行快速排序，直到所有记录都排到相应的位置为止。
   在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量pivot
中，如图中的第①步所示。这样基准元素在数组中占据的位置就空闲出来了，因此下一步就从后向前扫描。如图中的第②步所示，找到一个比基准元素小的元素时为止，将其前移，如图中的第③步所示。然后再从前向后扫描，如图中的第④步所示，找到一个比基准元素大的元素时为止，将其后移，如图中的第⑤步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置为止，如图中的第⑥步所示。
   由题目中给出的流程图可知，以第一个元素作为基准数，并将A[low]备份至pivot，i用于从前向后扫描的位置指示器，其初值为low，j用于从后往前扫描的位置指示器，其初值为high。当i＜j时进行循环：
   1．从后向前扫描数组A，在i＜j的情况下，如果被扫描的元素A刚＞pivot，就继续向前扫描(j--)；如果被扫描的元素A[j]＜pivot就停止扫描，并将此元素的值赋给目前空闲着的A。
   2．这时，再从前向后扫描，在i＜j的情况下，如果被扫描的元素A刚＜pivot，就继续向后扫描(i++)；如果被扫描的元素A[j]＞pivot就停止扫描，并将此元素的值赋给目前空闲着的A[j]。
   3．这时又接第(1)步，直到i＞j时退出循环。退出循环时，将pivot赋给当前的A (A←pivot)。
   递归函数的目的是执行一系列调用，直到到达某一点时递归终止。为了保证递归函数正常执行，应该遵守下面的规则：
   1．每当一个递归函数被调用时，程序首先应该检查基本的条件是否满足，例如，某个参数的值等于0，如果是这种情形，函数应停止递归。
   2．每次当函数被递归调用时，传递给函数一个或多个参数，应该以某种方式变得“更简单”，即这些参数应该逐渐靠近上述基本条件。例如，一个正整数在每次递归调用时会逐渐变小，以至最终其值到达0。
   本题中，递归函数sort(iht A[]，int L int H)有3个参数，分别表示数组A及其下界和上界。根据流程图可知，这里的L相当于流程图中的i，这里的H相当于流程图中的j。因为p()返回基准数所在数组A中的下标，也就是流程图中最后的“A←pivot”中的i。根据快速排序算法，在第一趟排序后找出了基准数所在数组A中的下标，然后以该基准数为界 ＜基准数在数组中的下标为k)，把数组A分成2组，分别是A[L，…，k-1]和A[k+l，…， H]，最后对这2组中的元素再使用同样的方法进行快速排序。
转载请注明原文地址:https://www.kaotiyun.com/show/QYDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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