2. 计算机
  3. 阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子

阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子

admin2016-11-11  29
问题 阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列)，然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。函数quicksort(int a[]，int n)实现了快速排序，其中，n个整数构成的待排序列保存在数组元素a[0]～a[n一1]中。
【C代码】
    #include
    Void quicksort(int a[]，  int n)
    {
       int  i，j；
       int pivot=a[0]；                            ／／设置基准值
       i=0；j=n一1；
       while  (i＜j){
          while(i＜j＆＆___________(1)) j--；    ／／大于基准值者保持在原位置
          if  (i＜j)  {  a=a[j]；i++；)
          while(i＜j＆＆__________(2)) i++；       ／／不大于基准值者保持在原位置
           if  (i＜j)  {a[j]=a；j--；}
   }
    a=pivot；    ／／基准元素归位
    if(i＞1)
    ___________(3)；    ／／递归地对左子序列进行快速排序
    if(n—i一1＞1)
    ___________(4)；    ／／递归地对右子序列进行快速排序
    }
    int main()
    {
       int i，arr[]={23，56，9，75，18，42，11，67)；
       quicksort(___________(5))；    ／／调用quicksort对数组arr[]进行排序
       for(i=0；i         printf("％d＼t"，arr)；
       return 0；
    }
选项
答案(1)a[j]＞pivot 或a[j]＞=pivot或等价形式 (2)a[i]＜=pivot或a[i]＜pivot 或等价形式 (3)quicksort(a，i)或quicksort(a，j)或等价形式 (4)quicksort(a+i+l，n一i一1) 或quicksort(a+j+1，n一j一1) 或等价形式 注：a+i+1可表示为&a[i+1]，a+j+1可表示为&a[j+1] (5)arr，sizeof(arr)／sizeof(int) 注：sizeof(arr)／sizeof(int)可替换为8
解析 本题考查C程序设计基本技能及快速排序算法的实现。
    题目要求在阅读理解代码说明的前提下完善代码，该题目中的主要考查点为运算逻辑和函数调用的参数处理。
    程序中实现快速排序的函数为quicksort，根据该函数定义的首部，第一个参数为数组参数，其实质是指针，调用时应给出数组名或数组中某个元素的地址；第二个参数为整型参数，作用为说明数组中待排序列(或子序列)的长度。
    快速排序主要通过划分来实现排序。根据说明，先设置待排序列(或子序列，存储在数组中)的第一个元素值为基准值。划分时首先从后往前扫描，即在序列后端找出比基准值小或相等的元素后将其移到前端，再从前往后扫描，即在序列前端找出比基准值大的元素后将其移动到后端，直到找出基准值在序列中的最终排序位置。再结合注释，空(1)处应填入“a[j]＞pivot”，使得比基准值大者保持在序列后端。空(2)处应填入“a＜=pivot”，使得不大于基准值者保持在前端。
    在完成1次划分后，基准元素被放入a，那么分出来的左子序列由a[0]～a[i一1]这i个元素构成，右子序列由a[i+1]～a[n－1]构成，接下来应递归地对左、右子序列进行快排。
因此，结合注释，空(3)应填入“quicksort(a，i)”或其等价形式，以对左子序列的i个元素进行快排，也可以用&a[0]代替其中的a，它们是等价的，a与&a[0]都表示数组的起始地址。
    空(4)所在代码实现对右子序列进行快排。右子序列由a[i+1]～a[n—1]构成，其元素个数为n一1一(i+1)+1，即n一i一1，显然元素a[i+1]的地址为&a[i+1]或a+i+1，所以空(4)应填入“quicksort(a+i+1，n—i一1)”或其等价形式。
  在main函数中，空(5)所在代码首次调用函数quicksort对main函数中的数组arr进行快排，因此应填入“arr,sizeof(arr)／sizeof(int)”或其等价形式。
转载请注明原文地址:https://kaotiyun.com/show/g9jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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