企业官网建设流程全解析

【题目】

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

1#include<iostream>23usingnamespacestd;45constintMAXN=105;67intn,m,k,val[MAXN];8inttemp[MAXN],cnt[MAXN];910voidinit()11{12cin>>n>>k;13for(inti=0;i<n;i++)cin>>val[i];14intmaximum=val[0];15for(inti=1;i<n;i++)16if(val[i]>maximum)maximum=val[i];17m=1;18while(maximum>=k){19maximum/=k;20m++;21}22}2324voidsolve()25{26intbase=1;27for(inti=0;i<m;i++){28for(intj=0;j<k;j++)cnt[j]=0;29for(intj=0;j<n;j++)cnt[val[j]/base%k]++;30for(intj=1;j<k;j++)cnt[j]+=cnt[j-1];31for(intj=n-1;j>=0;j--){32temp[cnt[val[j]/base%k]-1]=val[j];33cnt[val[j]/base%k]--;34}35for(intj=0;j<n;j++)val[j]=temp[j];36base*=k;37}38}3940intmain()41{42init();43solve();44for(inti=0;i<n;i++)cout<<val[i]<<;45cout<<endl;46return0;47}

假设输入的 n 为不大于 100 的正整数，k 为不小于 2 且不大于 100 的正整数，val[i]在 int 表示范围内，完成下面的判断题和单选题：
判断题
1.这是一个不稳定的排序算法。（ ）
2.该算法的空间复杂度仅与 n 有关。（ ）
3.该算法的时间复杂度为O(m(n+k))。（ ）
单选题
1.当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 36 行，val[]数组的内容依次为（ ）。
A. 91 26 46 37 98
B. 91 46 37 26 98
C. 98 26 46 91 37
D. 91 37 46 98 26

2.若 val[i]的最大值为 100，k 取（ ）时算法运算次数最少。
A. 2
B. 3
C. 10
D. 不确定
3.当输入的 k 比 val[i]的最大值还大时，该算法退化为（ ）算法。
A. 选择排序
B. 冒泡排序
C. 计数排序
D. 桶排序

【题目考点】

1. 基数排序

【解题思路】

40intmain()41{42init();43solve();44for(inti=0;i<n;i++)cout<<val[i]<<;45cout<<endl;46return0;47}

先看主函数，首先调用了init()函数，应该是初始化了什么东西。然后调用solve()，应该是解决了什么问题，最后输出val数组的值。val数组为结果。
接下来按顺序看各个函数，先看init()

10voidinit()11{12cin>>n>>k;13for(inti=0;i<n;i++)cin>>val[i];14intmaximum=val[0];15for(inti=1;i<n;i++)16if(val[i]>maximum)maximum=val[i];17m=1;18while(maximum>=k){19maximum/=k;20m++;21}22}

输入n和k，然后输入n个数字到val数组。maximum这个词一看就是要求最大值，后面果然是循环求val数组的最大值，最大值为maximum。
接下来只要maximum大于等于k，就除以k，m增加1。这是在求maximum在k进制下的位数。

比如k是10， maximum是123，一开始m为1，
第1次判断maximum >= k满足条件，maximum除以k后变为12，m变为2。
第2次判断maximum >= k满足条件，maximum除以k后变为1，m变为3。
第3次判断maximum >= k不满足条件，m为3，即123是3位数。

24voidsolve()25{26intbase=1;27for(inti=0;i<m;i++){28for(intj=0;j<k;j++)cnt[j]=0;29for(intj=0;j<n;j++)cnt[val[j]/base%k]++;30for(intj=1;j<k;j++)cnt[j]+=cnt[j-1];31for(intj=n-1;j>=0;j--){32temp[cnt[val[j]/base%k]-1]=val[j];33cnt[val[j]/base%k]--;34}35for(intj=0;j<n;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= 10
base=1, val[j]/base%k = 123/1%10 = 3
base=10, val[j]/base%k = 123/10%10 = 2
base=10, 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(n+k)O(n+k)O(n+k)
3.该算法的时间复杂度为O(m(n+k))。（ ）
答：T。第27行进行m次循环，循环内部有进行n次的循环也有进行k次的循环。因此时间复杂度为O(m(n+k))O(m(n+k))O(m(n+k))
单选题
1.当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 36 行，val[]数组的内容依次为（ ）。
A. 91 26 46 37 98
B. 91 46 37 26 98
C. 98 26 46 91 37
D. 91 37 46 98 26
答：D
5个数，3进制，第一次执行到36行时，只是按照这5个数字在3进制下的第0位从低到高进行排序。数字在3进制下第0位的数字为该数值除以3的余数

由于排序是稳定的，因此相同数值按照原顺序排列，根据3进制第0位数字排序后的结果为91 37 46 98 26，选D。
2.若 val[i]的最大值为 100，k 取（ ）时算法运算次数最少。
A. 2
B. 3
C. 10
D. 不确定
答：D
因为有进行n次的循环（第29、31、35行），该题没有给出n是多少，n的大小会影响运算次数，因此无法只靠k的大小决定运算次数。

3.当输入的 k 比 val[i]的最大值还大时，该算法退化为（ ）算法。
A. 选择排序
B. 冒泡排序
C. 计数排序
D. 桶排序
答：C。
当k比val的最大值更大时，m=1，相当于所有val数组的数值在k进制下只有1位数。val[j] / base % k的值就是val[j]，cnt数组就是计数数组，用来统计val数组中每个数值出现的次数。最后根据各个数值出现的次数输出。这样的排序算法是计数排序。
桶排序是更大的概念，凡是使用哈希函数将数值分到多个桶中的排序算法，都可以算是桶排序。计数排序是一种特殊的桶排序，基数排序是进行了多趟的基数排序，也可以归类为桶排序。该题更准确地说，还是退化为计数排序。