试题四（共15 分） 阅读下列说明和C代码 回答问题 1 至问题3 将解答写在答题纸的对应栏内。 【说明】

参考答案：试题四分析本题考查算法设计与分析技术以及算法的c语言实现，是比较传统的题目，要求考生细心分析题目中所描述的内容。【问题1】根据题中说明，第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]]+l。完成第6行到第8行的代码后，c[i]中就存放了等于i的元素的个数。第9到第11行，通过在数组c中记录计数和，c[i]=c[i-1]+c[i]，可以确定对每一个i=0,1,…,R-l，有多少个元素是小于或等于i的。因此空格(3)填写c[i-1]+c[i]。第12行到第15行把数组a中每个元素a[i]放在输出数组b中与其相应的最终位置上，b[c[a[il]-1]=a[i]，因此空格(4)填写a[i]。由于可能存在相同元素，因此每次将一个值a[i]放入数组b中时，都要减小c[i]的值。下面以一个例子来说明排序过程。设a={4,l,3,4,3,4},R=5，即待排序的元素值在{0,l,2,3,4}中，其排序过程如下图所示。图中(a)为输入数组a，(b)为初始化后的c数组，(c)为统计数组a中每个元素后的c数组，(d)为计数和，即统计小于等于i的元素个数后的c数组。(e)到(j)是将a数组中的元素依次放到b数组的过程，(k)是数组a和数组b的元素对应关系。 【问题2】根据上述C代码，第3到第5行代码的for循环所花时间为Θ(R)。第6到第8行的for循环所花时间为Θ(n)。第9到第11行的for循环所花时间为Θ(R)。第12到第15行for循环所花时间为Θ(n)。因此整个算法的时间复杂度为Θ(n+R)。若R远小于n或者R=Θ(n)时，时间复杂度可以表示为Θ(n)。【问题3】从图(k)可以看出，算法不稳定。算法不稳定的原因在于将数组a中元素放到数组b中时，是从数组a的第一个元素开始，依次取出元素放到数组b中。这样，相同的两个元素值，在数组a中的相对位置和在数组b中的相对位置正好相反。若从数组a的最后一个元素开始，依次向前取元素放到b数组中，可以保持相同元素的相对位置。因此将第12行的代码for(i=0；i<n；i++)改为for(i=n-1；i>0；i--)，则排序算法是稳定的。参考答案（共15分）【问题1】(8分)(1)R (2)c[a[i]]+l (3)c[i]+c[i -1] (4)a[i] 【问题2】（4分）(5)O（n+R）或者O(n)或n或线性 (6)O（n+R）或者O(n)或n或线性 【问题3】（3分）不稳定。修改第12行的for循环为：for(i=n-1；i＞=0；i--){即可。