CSP-S 2022 提高级 第一轮 阅读程序（2）

【题目】CSP-S 2022 提高级 第一轮 阅读程序21#includeiostream23usingnamespacestd;45constintMAXN105;67intn,m,k,val[MAXN];8inttemp[MAXN],cnt[MAXN];910voidinit()11{12cinnk;13for(inti0;in;i)cinval[i];14intmaximumval[0];15for(inti1;in;i)16if(val[i]maximum)maximumval[i];17m1;18while(maximumk){19maximum/k;20m;21}22}2324voidsolve()25{26intbase1;27for(inti0;im;i){28for(intj0;jk;j)cnt[j]0;29for(intj0;jn;j)cnt[val[j]/base%k];30for(intj1;jk;j)cnt[j]cnt[j-1];31for(intjn-1;j0;j--){32temp[cnt[val[j]/base%k]-1]val[j];33cnt[val[j]/base%k]--;34}35for(intj0;jn;j)val[j]temp[j];36base*k;37}38}3940intmain()41{42init();43solve();44for(inti0;in;i)coutval[i];45coutendl;46return0;47}假设输入的 n 为不大于 100 的正整数k 为不小于 2 且不大于 100 的正整数val[i]在 int 表示范围内完成下面的判断题和单选题判断题1.这是一个不稳定的排序算法。 2.该算法的空间复杂度仅与 n 有关。 3.该算法的时间复杂度为O(m(nk))。 单选题1.当输入为“5 3 98 26 91 37 46”时程序第一次执行到第 36 行val[]数组的内容依次为 。A. 91 26 46 37 98B. 91 46 37 26 98C. 98 26 46 91 37D. 91 37 46 98 262.若 val[i]的最大值为 100k 取 时算法运算次数最少。A. 2B. 3C. 10D. 不确定3.当输入的 k 比 val[i]的最大值还大时该算法退化为 算法。A. 选择排序B. 冒泡排序C. 计数排序D. 桶排序【题目考点】1. 基数排序【解题思路】40intmain()41{42init();43solve();44for(inti0;in;i)coutval[i];45coutendl;46return0;47}先看主函数首先调用了init()函数应该是初始化了什么东西。然后调用solve()应该是解决了什么问题最后输出val数组的值。val数组为结果。接下来按顺序看各个函数先看init()10voidinit()11{12cinnk;13for(inti0;in;i)cinval[i];14intmaximumval[0];15for(inti1;in;i)16if(val[i]maximum)maximumval[i];17m1;18while(maximumk){19maximum/k;20m;21}22}输入n和k然后输入n个数字到val数组。maximum这个词一看就是要求最大值后面果然是循环求val数组的最大值最大值为maximum。接下来只要maximum大于等于k就除以km增加1。这是在求maximum在k进制下的位数。比如k是10 maximum是123一开始m为1第1次判断maximum k满足条件maximum除以k后变为12m变为2。第2次判断maximum k满足条件maximum除以k后变为1m变为3。第3次判断maximum k不满足条件m为3即123是3位数。24voidsolve()25{26intbase1;27for(inti0;im;i){28for(intj0;jk;j)cnt[j]0;29for(intj0;jn;j)cnt[val[j]/base%k];30for(intj1;jk;j)cnt[j]cnt[j-1];31for(intjn-1;j0;j--){32temp[cnt[val[j]/base%k]-1]val[j];33cnt[val[j]/base%k]--;34}35for(intj0;jn;j)val[j]temp[j];36base*k;37}38}而后看solve()函数base变量的意义一会儿再确定。进行i从0~m-1进行m次循环。每次循环内部进行了多次循环。首先使cnt数组下标0~k-1都设为0即数组清零。而后j从0~n-1循环n是数值个数为val数组的长度因此这一次循环是遍历val数组。对val数组中的每个元素val[j]求val[j]/base%k结合base初值为1每次循环结束时base * k根据经验可以了解到val[j]/base%k是在取val[j]的某一位数字具体来说是val[j]在k进制下的第i位数字最低位为第0位例如十进制下个位是第0位十位是第1位例va[j] 123, k 10base1, val[j]/base%k 123/1%10 3base10, val[j]/base%k 123/10%10 2base10, val[j]/base%k 123/100%10 1而cnt[val[j]/base%k]的意思就是将val[j]在k进制下的第i位数字进行计数。统计val数组中各个数第i位的数字出现的个数。cnt[x]表示在val数组所有数的第i位中数字x出现的个数。由于是k进制数字因此一位数可以出现的数字只能是0~k-1因此cnt的下标范围是0~k-1。接下来j从1~k-1执行cnt[j] cnt[j - 1]是将cnt组变为原cnt数组的前缀和cnt[x]表示在val数组所有数的第i位中数字0~x出现的总次数。现在需要按照val数组的第i位为val数组中的元素进行排序使用temp数组临时保存排序后的元素。以下用x表示val[j]/base%k即val[j]下k进制下的第i位的数字。数字0~x出现的总次数为cnt[x]那么val[j]就是排序后的第cnt[x]个数字应该在下标cnt[x]-1的位置。因此设temp[cnt[x]-1] val[j];即temp[cnt[val[j]/base%k]-1] val[j];接下来下一个第i位的数字为x的val数组中的数值可以认为是排序后的第cnt[x]-1个数字在temp中的下标应该比之前减1所以cnt[x]--下一次还是通过temp[cnt[x]-1] val[j];把数值赋值到temp数组中。为了保持排序的稳定性对于val数组中第i位数字相同的各个数值在val数组中靠后的数值赋值到temp数组中也应该是靠后的。由于对temp数组的赋值顺序是从后向前赋值的(表示赋值位置的cnt[x]不断减少)因此遍历val数组的顺序也应该是从后向前遍历的。最后把temp数组中的元素复制到val数组中。该过程即可以将val数组中的元素按照第i位的数字从小到大排序。i从0~m-1循环先按第0位从小到大排序然后按第1位从小到大排序而后按第2位。。。最后一次按第m-1位从小到大排序每次排序使用的是稳定的计数排序的方法共有基数个桶即k个桶。该排序算法叫做基数排序。【答案及解析】判断题1.这是一个不稳定的排序算法。 答F。基数排序是多趟计数排序计数排序是稳定的排序算法整体也是稳定的排序算法。2.该算法的空间复杂度仅与 n 有关。 答F。val数组的长度为n而cnt数组的长度为k即数值的基数。基数排序的空间复杂度与数字个数n与基数k都有关空间复杂度为O(nk)O(nk)O(nk)3.该算法的时间复杂度为O(m(nk))。 答T。第27行进行m次循环循环内部有进行n次的循环也有进行k次的循环。因此时间复杂度为O(m(nk))O(m(nk))O(m(nk))单选题1.当输入为“5 3 98 26 91 37 46”时程序第一次执行到第 36 行val[]数组的内容依次为 。A. 91 26 46 37 98B. 91 46 37 26 98C. 98 26 46 91 37D. 91 37 46 98 26答D5个数3进制第一次执行到36行时只是按照这5个数字在3进制下的第0位从低到高进行排序。数字在3进制下第0位的数字为该数值除以3的余数十进制数值98269137463进制第0位数字22111由于排序是稳定的因此相同数值按照原顺序排列根据3进制第0位数字排序后的结果为91 37 46 98 26选D。2.若 val[i]的最大值为 100k 取 时算法运算次数最少。A. 2B. 3C. 10D. 不确定答D因为有进行n次的循环第29、31、35行该题没有给出n是多少n的大小会影响运算次数因此无法只靠k的大小决定运算次数。3.当输入的 k 比 val[i]的最大值还大时该算法退化为 算法。A. 选择排序B. 冒泡排序C. 计数排序D. 桶排序答C。当k比val的最大值更大时m1相当于所有val数组的数值在k进制下只有1位数。val[j] / base % k的值就是val[j]cnt数组就是计数数组用来统计val数组中每个数值出现的次数。最后根据各个数值出现的次数输出。这样的排序算法是计数排序。桶排序是更大的概念凡是使用哈希函数将数值分到多个桶中的排序算法都可以算是桶排序。计数排序是一种特殊的桶排序基数排序是进行了多趟的基数排序也可以归类为桶排序。该题更准确地说还是退化为计数排序。