2. 计算机
  3. 阅读下列说明和c代码，回答问题1至问题3，将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的

阅读下列说明和c代码，回答问题1至问题3，将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的

admin2012-03-21  72
问题 阅读下列说明和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=0;
   5    }
   6    for(i=0; i＜n; i++)  {
   7    c[a]=  (2)  ;
   8    }
   9    for(i=1; i＜R; i++)  {
   10    c=  (3)  ;
   11    }
   12    for(i=0; i＜n; i++)  {
   13    b[c[a]-1]=  (4)  ;
   14    c[a]=c[a]-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的值。因此c[a]=c[a]+1，空格(2)填写c[a]+1。完成第6行到第8行的代码后，c中就存放了等于i的元素的个数。第9到第11行，通过在数组c中记录计数和，c=c[i-1]+c，可以确定对每一个i=0，1，…，R-1，有多少个元素是小于或等于i的。因此空格(3)填写c[i-1]+c。第12行到第15行把数组a中每个元素a放在输出数组b中与其相应的最终位置上，b[c[a]-1]=a，因此空格(4)填写a。由于可能存在相同元素，因此每次将一个值a放入数组b中时，都要减小c的值。下面以一个例子来说明排序过程。
   设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的元素对应关系。
转载请注明原文地址:https://www.kaotiyun.com/show/7lDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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