2. 计算机
  3. 阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后，取第k个元素)。 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后，取第k个元素)。 对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基

admin2017-11-28  45
问题 阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第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(low≤i≤high)，并使得a[low]，a[low+1]，…a[i—1]都小于或等于a，而a[i+1]，a[i+2]，…a[high]都大于a。
函数findkthElem(int a[]，int startldx，int endldx，int k)在a[startldx]，a[startldx+1]…，a[endIdx]中找出第k小的元素。
【代码】
#include
#include
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(ipivot)一一j；
a=a[j]；
while(i<=pivot)++i；
a[j]=a；
}
(2)；    ／／基准元素定位
return i；
  }
int findkthElem(int a[]，int startIdx，int endIdx，int k)
{／／整数序列存储在a[startIdx．．endIdx]中，查找并返回第k小的元素。
if(startIdx<0 ‖endIdx<0 ‖startIdx>endIdx ‖ k<1‖ k—l>endIdx ‖
k一1return一1；    ／／参数错误
if(startIdxint loc=partition(a，startIdx，endIdx)；
／／进行划分，确定基准元素的位置
if(loc==k一1)    ／／找到第k小的元素
return  (3)  ；
if(k一1return 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，  7 8，  25，  7}；
n=sizeof(a)／sizeof(int)；    ／／计算序列中的元素个数
for(k=1；  kfor(i=0；  iprintf(“％d＼t”，a)；
}
printf(“＼n”)；
printf(“elem％d=％d＼n”，  k，  findkthElem(a，0，n一1，k))；
／／输出序列中第k小的元素
}
return 0；
}
选项
答案(1)i
解析 本题考查C程序中数组、函数参数和排序算法的应用。
根据题目说明中提供的信息，利用快速排序查找给定序列中第k小的元素。
首先分析程序的逻辑结构、每个函数的作用和主要变量的含义及作用，然后再具体分析每个函数的运算逻辑。
函数partition(int a[]，int low，int high)对保存在数组a中的元素序列进行划分，也就是指定第一个元素为基准，通过逐个扫描序列中的元素，将大于基准的其他元素移动到序列的后半区，将不大于基准的其他元素移动到序列的前半区，在这个过程中，对于本来就在后半区且大于基准的元素则保持不动，同理，对于本来就在前半区且小于或等于基准的元素保持其原来所在位置。
根据函数中已给出的语句，先从序列的后端开始向前扫描，遇到一个小于或等于基准的元素为止，语句如下：
while  (  ipiVot  )  一一j；
然后通过“a=a[j]”将不大于基准的元素a[j]往前移了。
之后从序列的前端开始向后扫描，遇到一个大于基准的元素为止，语句如下：
while  (  i<=pivot  )  ++i；
然后通过“aD]：a”将大于基准的元素a往后移了。
显然易见，重复上面的过程直到基准元素的位置被确定下来，也就是“i=j”为止，因此空(1)处应填入“i=pivot”或“a[j]=pivot”或其等效方式。
函数findkthElem(int a[]，int startldx，int endldx，int k)的功能是在数组a[startldx．．endldx]中查找并返回第k小的元素。该函数中，通过调用pattition不断地对序列进行划分，直到找到所需元素。调用语句如下：
loc=partition(a，startIdx，endIdx)；／／进行划分，确定基准元素的位置由于C语言中数组下标从0开始，即第一个元素的下标为0，元素在数组中的下标与元素的序号正好相差1。对于第一次调用，当得到基准元素的位置为loc，也就是说基准元素前面有loc个元素，而基准元素在序列中为第loc+1个元素，因此，此时若loc==k一1，则基准元素正好就是第k小的元素，即空(3)处填入“a[loc]”或其等效表示。若非如此，则k-1由于是将所要找的元素的序号与其在数组中的下标直接绑定，也就是需要找出正好在下标为k一1位置上的元素，保证下标为0~k-2的元素都不大于a[k-1]即可。因此，若下一步需到前半区继续查找，则要找的元素仍然为第k个，因此空(4)处所在的完整语句为“return findkthElem(a，startldx，loc一1，k)；”若下一步需到后半区继续查找，则要找的元素仍然为第k个，因此空(5)处所在的完整语句为“return findkthElem(a，loc+1，endldx,k)；”程序中在递归调用的语句中保留了第1个参数和第4个参数，而将表示基准元素之前的前半区和之后的后半区参数留给考生解答，客观上降低了理解的难度，因此考生应重点把握程序的整体逻辑结构。
转载请注明原文地址:https://kaotiyun.com/show/49jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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