对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第1个元素为基准的一次划分的结果为 ( )A．(5,1,4,3,6,2,8,7)B．(5,1,4,3,2,6,7,8)C．(5,1,4,3,2,6,8,7)D．(8,7,6,5,4,3,2,1)

一组记录的关键字序列为(46,79,56,38,40,84)

(1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果(给出逐次交换元

素的过程，要求以升序排列)。

(2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。

对下列4个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准。在第一趟划分过程中，元素移动次数最多的序列是______。

A．70，75，82，90，23，16，10，68

B． 70，75，65，23，10，16，90，82

C． 82，75，70，16，10，90，68，23

D． 23，10，16，70，82，75，68，90

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素（即将元素从小到大排序后，取第k个元素）。 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序的序列划分为不大于基准值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。 例如，整数序列“19, 12, 30, 11,7,53, 78, 25"的第3小元素为12。整数序列“19,12,7,30,11,11,7,53,78,25,7"的第3小元素为7。 函数partition（int a[ ], int low,int high）以a[low]的值为基准，对a[low]、a[low+1]、…、 a[high]进行划分，最后将该基准值放入a[i] (low≤i≤high)，并使得a[low]、a[low+1]、，．．、 A[i-1]都小于或等于a[i]，而a[i+1]、a[i+2]、．．、a[high]都大于a[i]。 函教findkthElem(int a[],int startIdx,int endIdx,inr k)在a[startIdx]、a[startIdx+1]、...、a[endIdx]中找出第k小的元素。

【代码】 include <stdio.h> include <stdlib.h> Int partition（int a [ ]，int low, int high） {//对 a[low..high]进行划分，使得a[low..i]中的元素都不大于a[i+1..high]中的元素。 int pivot=a[low]； //pivot表示基准元素 Int i=low,j=high; while(（ 1） ){ While(i<j&&a[j]>pivot)--j; a[i]=a[j] While(i<j&&a[i]<=pivot)++i; a[j]=a[i] } （2） ； //基准元素定位 return i； } Int findkthElem（int a[ ]，int startIdx，int endIdx, int k） {//整数序列存储在a[startldx..endldx]中，查找并返回第k小的元素。 if (startldx<0 ||endIdx<0 || startIdx>endIdx || k<1 ||k-1>endIdx ||k-1<startIdx) Return-1; //参数错误 if(startIdx<endldx){ int loc=partition(a, startIdx, endldx)； ∥进行划分，确定基准元素的位置 if (loc==k-1) ∥找到第k小的元素 return （3） ； if(k-1 <loc) //继续在基准元素之前查找 return findkthElem(a, （4） ,k）； else ／／继续在基准元素之后查找 return findkthElem(a， （5） ，k); } return a[startIdx]； } int main() { int i, k; int n; int a[] = {19, 12, 7, 30, 11, 11, 7, 53, 78, 25, 7}; n= sizeof(a)／sizeof(int) //计算序列中的元素个数 for (k=1;k＜n+1；k++){ for(i=0;i＜n;i++){ printf(“%d/t”,a[i]); } printf(“\n”); printf(“elem %d=%d\n,k,findkthElem(a,0,n-1,k));//输出序列中第k小的元素 } return 0； }

A.48，30，50，56，66，89，94，87，100

B.30，50，48，56，66，89，94，100，87

C.50，30，48，66，56，89，94，87，100

D.50，30，48，56，66，89，94，87，100

对序列(70，75，82，90，23，16)用快速排序方法进行排序，以序列的第一个元素为划分的基准。在第一趟划分后数据元素的排列是( )。

A．16，75，82，90，23，70

B．16，70，82，90，23，75

C．16，23，70，90，82，75

D．16，23，82，90，70，75

对序列{49，38，65，97，76，13，27，50}采用快速排序方法进行排序，以第一个元素为基准元素得到的划分结果是(55)。

A．13，27，38，49，76，97，65，50

B．27，38，13，49，76，97，65，50

C．27，38，13，49，50，76，65，97

D．27，13，38，49，76，97，65，50

根据枢轴元素(或基准元素)划分序列而进行排序的是（ ）。

A. 快速排序 B. 冒泡排序 C. 简单选择排序 D. 直接插入排序