试题预览
1
解析题
20分
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第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 (startIdx<0 ||endIdx<0 || startIdx > endIdx || k<1 ||k-1>endIdx ||k-1<startIdx)
return-1; //参数错误
if(startIdx<endIdx){
int loc=partition(a, startIdx, endIdx); //进行划分,确定基准元素的位置
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;
}