问题 问答题

阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。

[说明]

某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m个位置。对于元素值重复的情况,依次放入第m-1、m-2、…个位置。例如,如果元素值小于等于4的元素个数有10个,其中元素值等于4的元素个数有3个,则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。

算法具体的步骤为:

步骤1:统计每个元素值的个数。

步骤2:统计小于等于每个元素值的个数。

步骤3:将输入元素序列中的每个元素放入有序的输出元素序列。

[C代码]

下面是该排序算法的C语言实现。

(1)常量和变量说明

R:常量,定义元素取值范围中的取值个数,如上述应用中R值应取6。

i:循环变量。

n:待排序元素个数。

a:输入数组,长度为n。

b:输出数组,长度为n。

c:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。

(2)函数sort

1 void sort(int n, int a[], int b[]) {

2 int c[R], i;

3 for(i=0; i< (1) ; i++) {

4 c[i]=0;

5 }

6 for(i=0; i<n; i++) {

7 c[a[i]]= (2) ;

8 }

9 for(i=1; i<R; i++) {

10 c[i]= (3) ;

11 }

12 for(i=0; i<n; i++) {

13 b[c[a[i]]-1]= (4) ;

14 c[a[i]]=c[a[i]]-1;

15    }

16  }

根据说明和C代码,填充C代码中的空缺(1)~(4)。

答案

参考答案:

(1)R

(2)c[a[i]]+1

(3)c[i]+c[i-1]

(4)a[i]

解析:

本题考查算法设计与分析技术以及算法的C语言实现,是比较传统的题目,要求考生细心分析题目中所描述的内容。

根据题中说明,第3到第5行代码进行c数组的初始化,c数组的长度为R,在C语言中,下标从0开始,因此空格(1)中填写R。第6到第8行检查a数组的每一个元素。如果元素的值为i,则增加c[i]的值。因此c[a[i]]=c[a[i]]+1,空格(2)填写c[a[i]]+1。完成第6行到第8行的代码后,c[i]中就存放了等于i的元素的个数。第9到第11行,通过在数组c中记录计数和,c[i]=c[i-1]+c[i],可以确定对每一个i=0,1,…,R-1,有多少个元素是小于或等于i的。因此空格(3)填写c[i-1]+c[i]。第12行到第15行把数组a中每个元素a[i]放在输出数组b中与其相应的最终位置上,b[c[a[i]]-1]=a[i],因此空格(4)填写a[i]。由于可能存在相同元素,因此每次将一个值a[i]放入数组b中时,都要减小c[i]的值。下面以一个例子来说明排序过程。

设a={4,1,3,4,3,4},R=5,即待排序的元素值在{0,1,2,3,4}中,其排序过程如下图所示。

图中(a)为输入数组a,(b)为初始化后的c数组,(c)为统计数组a中每个元素后的c数组,(d)为计数和,即统计小于等于i的元素个数后的c数组。(e)到(j)是将a数组中的元素依次放到b数组的过程,(k)是数组a和数组b的元素对应关系。

[*]

选择题
填空题