问答题
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。
[说明]
下面的函数sort(int n,int a[])对保存在数组a中的整数序列进行非递减排序。由于该序列中的元素在一定范围内重复取值,因此排序方法是先计算出每个元素出现的次数并记录在数组b中,再从小到大顺序地排列各元素即可得到一个非递减有序序列。例如,对于序列6,5,6,9,6,4,8,6,5,其元素在整数区间[4,9]内取值,因此使数组元素b[0]~b[5]的下标0~5分别对应数值4~9,顺序地扫描序列的每一个元素并累计其出现的次数,即将4的个数记入b[0],5的个数记入b[1],依此类推,9的个数记入b[5]。最后依次判断数组b的每个元素值,并将相应个数的数值顺序地写入结果序列即可。
对于上例,所得数组b的各个元素值如下:
b[0]
|
b[1]
|
b[2]
|
b[3]
|
B[4]
|
b[5]
|
1
|
2
|
4
|
0
|
1
|
1
|
那么在输出序列中写入1个4、2个5、4个6、1个8、1个9,即得4,5,5,6,6,6,6,8,9,从而完成排序处理。
[C函数]
void sort(int n,int a[])
{ int *b;
int i, k, number;
int minimum=a[0],maximum=a[0];
/*minimum和maximum分别表示数组a的最小、最大元素值*/
for(i=1; i<n; i++){
if(______) minimum=a[i];
eiSe
if (______) maximum=a[i];
}
number=maximum-minimum+1;
if(number<=1)return;
b=(int*)calloc(number,sizeof(int));
if(!b) return;
for(i=0;i<n; i++){/*计算数组a的每个元素值出现的次数并记入数组b */
k=a[i]-minimum; ++b[k];
}
/*按次序在数组a中写入排好的序列*/
i=______;
for(k=0; k<number; k++)
for(; ______; --b[k] )
a[i++]=minimum+______;
}
【正确答案】
【答案解析】a[i]<minimum,或a[i]<=minimum,或其等价形式
a[i]>maximum,或a[i]>=maximum,或其等价形式
0
b[k],或b[k]>0,或b[k]!=0,或其等价形式
k
[解析] 本题考查C程序的基本语法和运算逻辑。
首先应认真分析题目中的说明,然后确定代码结构和各变量的作用。
空(1)和(2)所在for语句的功能是求出数组a中的最小元素minimum和最大元素maximum。在设置了minimum和maximum的初始值后,空(1)处的判断条件是只要目前的元素a[i]小于。minimum,就需要更新。minimum,反之,空(2)处的判断条件是只要目前的元素a[i]大于maximum,就需要更新maximum,因此空(1)处应填入a[i]<minimum或其等价方式,空(2)处应填入a[i]>maximum或其等价方式。minimum和maximum的作用是要确定计数数组b的大小。
根据题目中的描述,序列中的每个元素a[i]都对应到计数数组b[]的一个元素b[k],对应方式为:k=a[i]-minimum,其中minimum是数组a中的最小元素,显然在计数时,一个数值出现一次,就在对应的b[k]中累加一次。
空(3)~(5)所在的语句组是产生排序后的序列,重新写入数组a。首先需明确变量i和k的作用,根据它们在该语句组中的出现位置,i用于表示数组a的元素下标,k用于表示数组b中元素的下标,因此,空(3)处应填入0,使得从数组a中下标为0的数组元素开始。通过循环控制“for(k=0; k<number;k++)”已经明确数组b的下标变化方式,而需要写入数组a的元素个数表示在b[k]中,所以“for(; ______; --b[k])”中空(4)处应填入“b[k]>0”或其等价形式。由于b[k]中记录的是元素k+minimum的出现次数,所以空(5)处应填入“k”,从而将元素值恢复后再写回去。