第1章NOIP普及组(CSPJ)历年试题分析
1.12020 CCF入门级(CSPJ)试题B卷及解析
1.1.12020 CCF入门级(CSPJ)试题
一、 单项选择题(共15题，每题2分，共计30分； 每题有且仅有一个正确选项)
1. 在内存储器中每个存储单元都被赋予一个唯一的序号，称为()。
A. 下标 B. 地址 C. 序号 D. 编号
2. 编译器的主要功能是()。
A. 将源程序翻译成机器指令代码B. 将一种高级语言翻译成另一种高级语言
C. 将源程序重新组合D. 将低级语言翻译成高级语言
3. 设x=true，y=true，z=false，以下逻辑运算表达式值为真的是()。
A. (x∧y)∧zB. x∧( z∨y)∧z
C. (x∧y)∨(z∨x) D. (y∨z)∧x∧z
4. 现有一张分辨率为2048×1024像素的32位真彩色图像。请问要存储这张图像，需要多大的存储空间?()
A. 4MBB. 8MB C. 32MBD. 16MB
5. 冒泡排序算法的伪代码如下。
输入： 数组L,n≥1。
输出： 按非递减顺序排序的L。
算法BubbleSort：
1.FLAG←n //标记被交换的最后元素位置
2.while FLAG>1 do
3.k ← FLAG-1
4.FLAG ← 1
5.for j=1 to k do
6.if L(j)> L(j+1)then do
7.L(j)<-> L(j+1)
8.FLAG ← j
对n个数用以上冒泡排序算法进行排序，最少需要比较多少次?()
A. nB. n-2 C. n^2D. n-1
6. 设A是n个实数的数组，考虑下面的递归算法：
XYZ(A［1..n］)
1.if n=1 then return A［1］
2.else temp ← XYZ(A［1..n-1］)
3.if temp<A［n］
4.then return temp
5.else return A［n］
请问算法XYZ的输出是什么?()
A. A数组的平均B. A数组的最小值
C. A数组的最大值D. A数组的中值
7. 链表不具有的特点是()。
A. 插入删除不需要移动元素B. 可随机访问任一元素
C. 不必事先估计存储空间D. 所需空间与线性表长度成正比
8. 有10个顶点的无向图至少应该有()条边才能确保是一个连通图。
A. 10B. 12C. 9D. 11
9. 二进制数1011转换为十进制数是()。
A. 10B. 13C. 11D. 12
10. 5个小朋友并排站成一列，其中有两个小朋友是双胞胎。如果要求这两个双胞胎必须相邻，则有()种不同的排列方法。
A. 24B. 36C. 72D. 48
11. 下面所使用的数据结构是()。
压入A成［A］压入B成［B,A］弹出B成［A］压入C成［C,A］
A. 哈希表B. 二叉树C. 栈D. 队列
12. 独根树的高度为1。具有61个结点的完全二叉树的高度为()。
A. 7B. 5C. 8D. 6
13. 干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
天干=(公历年份)除以10所得余数
地支=(公历年份)除以12所得余数
天干甲乙丙丁戊己庚辛壬癸
4567890123
地支子丑寅卯辰巳午末申西戌亥
45678910110123
例如，今年是2020年，2020 除以10余数为0，查表为“庚”； 2020 除以12余数为4，查表为“子”，所以今年是庚子年。
请问1949年的天干地支是()。
A. 己亥B. 己丑C. 己卯D. 己酉
14. 10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有()种不同的分配方案。
A. 56 B. 84C. 72D. 504
15. 有5副不同颜色的手套(共10只手套，每副手套左右手各1只)，一次性从中取6只手套，请问恰好能配成两副手套的不同取法有()种。
A. 30B. 150C. 180D. 120
二、 阅读程序(程序输入不超过数组或字符串定义的范围； 判断题正确填√； 错误填×； 除特殊说明外，判断题每题1.5分，单选题每题3分，共计40分)
1.
01#include "cstdlib"
02#include "iostream"
03using namespace std;
04
05char encoder［26］ ={'C', 'S', 'P', 0};
06char decoder［26］;
07
08string st;
09
10int main(){
11int k=0;
12for (int i=0;i<26;++i)
13if (encoder［i］!=0)++k;
14for (char x='A';x<='Z';++x){
15bool flag=true;
16for (int i=0;i<26;++i)
17if (encoder［i］==x){
18flag=false;
19break;
20}
21if (flag){
22encoder［k］=x;
23++k;
24}
25}
26for (int i=0;i<26;++i)
27decoder［encoder［i］-'A'］=i +'A';
28cin>>st;
29for (int i=0;i<st.length();++i)
30st［i］=decoder［st［i］-'A'］;
31cout<<st;
32return 0;
33}
判断题
(1) 输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。()
(2) 若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。()
(3) 将第12行的“i<26”改为“i<16”，程序运行结果不会改变。()
(4) 将第26行的“i<26”改为“i<16”，程序运行结果不会改变。()
单选题
(5) 若输出的字符串为“ABCABCABCA”，则下列说法正确的是()。
A. 输入的字符串中既有A又有PB. 输入的字符串中既有S又有B
C. 输入的字符串中既有S又有PD. 输入的字符串中既有A又有B
(6) 若输出的字符串为“CSPCSPCSPCSP”，则下列说法正确的是()。
A. 输入的字符串中既有J又有RB. 输入的字符串中既有P又有K
C. 输入的字符串中既有J又有KD. 输入的字符串中既有P又有R
2.
01#include "iostream"
02using namespace std;
03
04long long n, ans;
05int k,len;
06long long d［ 1000000］;
07
08int main(){
09cin>>n>>k;
10d［0］=0;
11len=1;
12ans=0;
13for (long long i=0;i<n;++i){
14++d［0］;
15for (int j=0;j+1<len;++j){
16if (d［j］==k){
17d［j］=0;
18d［j+1］+=1;
19++ans;
20}
21}
22if (d［len-1］==k){
23d［len-1］=0;
24d［len］=1;
25++len;
26++ans;
27}
28}
29cout<<ans<<endl;
30return 0;
31 }
假设输入的n是不超过262的正整数，k 都是不超过10000的正整数，完成下面的判断题和单选题。
判断题
(1) 若k=1，则输出ans时，len=n。()
(2) 若k<1,则输出ans时，len一定小于n。()
(3) 若k<1，则输出ans时，klen一定大于n。()
单选题
(4) 若输入的n等于1015，输入的k为1，则输出等于()。
A. (1030-1015)/2B. (1030+1015)/2C. 1D. 1015
(5) 若输入的n等于205891132094649(即330)，输入的k为3，则输出等于()。
A. (330-1)/2B. 330C. 330-1D. (330+1)/2
(6) 若输入的n等于100010002000090， 输入的k为10， 则输出等于()。
A. 11112222444543B. 11122222444453
C. 11122222444543D. 11112222444453
3.
01#include "algorithm"
02#include "iostream"
03using namespace std;
04
05int n;
06int d［50］［2］;
37int ans;
08
09void dfs(int n, int sum){
10if (n==1){
11ans=max(sum, ans);
12return;
13}
14for (int i=1;i<n;++i){
15int a=d［i-1］［0］,b=d［i-1］［1］;
16int x= d［i］［0］, y= d［i］［1］;
17d［i-1］［0］ =a+ x;
18d［i-1］［1］ =b+ y
19for (int j=i;j<n-1;++j)
20d［j］［0］=d［j+1］［0］， d［j］［1］=d［j+1］［1］;
21int s= a+x+ abs(b-y);
22dfs(n-1，sum+s);
23for (int j=n-1;j>i;--j)
24d［j］［0］=d［j-1］［0］, d［j］［1］=d［j-1］［1］;
25d［i-1］［0］=a,d［i-1］［1］=b;
26d［i］［0］=x,d［i］［1］=y;
27}
28}
29
30int main(){
31cin>>n;
32for (int i=0;i<n;++i)
33cin>>d［i］［0］;
34for (int i=0;i<n;++i)
35cin>>d［i］［1］;
36ans=0;
37dfs(n, 0);
38cout<<ans<<endl;
39return 0;
40}
假设输入的n是不超过50的正整数，d［i］［0］、d［i］［1］都是不超过10000的正整数，完成下面的判断题和单选题。
判断题
(1) 若输入n为0，此程序可能会死循环或发生运行错误。()
(2) 若输入n为20，接下来的输入全为0，则输出为0。()
(3) 输出的数一定不小于输入的d［i］［0］和d［i］［1］中的任意一个。()
单选题
(4) 若输入的n为20，接下来的输入是20个9和20个0，则输出为()。
A. 1917B. 1908C. 1881D. 1890
(5) 若输入的n为30，接下来的输入是30个0和30个5，则输出为()。
A. 2020B. 2030C. 2010D. 2000
(6) 若输入的n为15，接下来的输入是15到1，以及15到1，则输出为()。
A. 2420B. 2220C. 2440D. 2240
三、 完善程序(单选题，每小题3分，共计30分)
1. (质因数分解)给出正整数n，请输出将n质因数分解的结果，结果按从小到大输出。
例如，输入n=120，程序应该输出2 2 2 3 5，表示120=2×2×2×3×5。输入保证2≤n≤109。
提示： 先从小到大枚举变量i，然后用i不停试除n来寻找所有的质因子。
试补全程序。
01#include "cstdio"
02using namespace std;
03
04int n,i;
05
06int main(){
07scanf("%d"，&n);
08for (i=(1);(2) <=n;i++){
09(3){
10printf("%d "，i);
11n=n/i;
12}
13}
14 if ((4))
15printf("%d "， (5));
16return 0;
17}
(1) 处应填()。
A. n-1B. 0C. 1D. 2
(2) 处应填()。
A. n/iB. n /(i*i)C. i*i*iD. i*i
(3) 处应填()。
A. if (i*i<=n)B. if (n%i==0)
C. while (i*i<=n)D. while (n%i==0)
(4) 处应填()。
A. n<1B. n<= 1C. i+i<=nD. i<n/i
(5) 处应填()。
A. 2B. iC. n/iD. n
2. (最小区间覆盖)给出n个区间，第i个区间的左右端点是［ai,bi］。现在要在这些区间中选出若干个，使得区间［0, m］被所选区间的并覆盖(即每一个0≤i≤m都在某个所选的区间中)。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 n和m(1≤n≤5000,1≤m≤109)。
接下来n行，每行两个整数ai，bi(0≤ai, bi≤m)。
提示： 使用贪心法解决这个问题。先用O(n2)的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
01#include "iostream"//本题需要非常强大的思维能力，难度较高。但是它是贪心问题中
02//非常经典的一类问题：线段覆盖问题
03using namespace std;.
04
05const int MAXN=5000;
06int n, m;
07struct segment{int a, b;} A［MAXN］;
08
09void sort()//排序
10{
11for (int i=0;i<n;i++)
12for (int j=1;j<n;j++)
13if ((1)) //两重循环，且(2)提示是一个交换的操作，因此是冒泡排序
14{
15segment t=A［j］;
16(2)
17}
18}
19
20int main()
21{
22cin>>n>>m;
23for (int i=0;i<n;i++){
24cin>>A［i］.a>>A［i］.b;}
25sort();
26int p=1; //第一次筛选
27for (int i=1;i<n;i++)
28if ((3)){
29A［p++］=A［i］;}
30n=p;
31int ans=0，r=0; //第二次筛选
32intq=0.
33while (r<m)
34{
35while ((4))
36q++;
37(5);
38ans++;
39}
40cout<<ans<<endl;
41return 0;
42}
(1) 处应填()。
A. A［j］.b<A［j-1］.bB. A［j］.b<A［j-1］.b
C. A［j］.a<A［j-1］.aD. A［j］.a<A［j-1］.a
(2) 处应填()。
A. A［j-1］=A［j］;A［j］=t;B. A［j+1］=A［j］;A［j］=t;
C. A［j］=A［j-1］;A［j-1］=t;D. A［j］=A［j+1］;A［j+1］=t;
(3) 处应填()。
A. A［i］.b<A［p-1］.bB. A［i］.b<A［i-1］.b
C. A［i］.b<A［p-1］.bD. A［i］.b<A［i-1］.b
(4) 处应填()。
A. q+1<n && A［q+1］.b<=rB. q+1<n && A［q+1］.a<=r
C. q<n && A［q］.a<=rD. q<n && A［q］.b<=r
(5) 处应填()。
A. r=max(r, A［q+1］.a) B. r=max(r, A［q］.b)
C. r=max(r, A［q+1］.b) D. q++
1.1.22020 CCF入门级(CSPJ)参考答案
一、 单项选择题(共15题，每题2分，共计30分)
123456789101112131415
BACBDBBCCDCDBBD
二、 阅读程序(除特殊说明外，判断题每题1.5分，单选题每题3分，共计40分)
第1题
判断题(填√或×)单选题
(1) (2) (3) (4) (5) (6)
√×√×CD
第2题
判断题(填√或×)单选题
(1) (2) (3) (4) (5) (6)
××√DAD
第3题
判断题(填√或×)单选题
(1) (2) (3) (4) (5) (6) (4分)
×√×CBD
三、 完善程序(单选题，每小题3分，共计30分)
第1题第2题
(1) (2) (3) (4) (5) (1) (2) (3) (4) (5)
DDDADCCCBB
1.1.32020 CCF入门级(CSPJ)部分试题分析
一、 单项选择题分析
1. 内存储器中的每个存储单元都需用地址区分不同的存储位置。
2. 计算机能执行的唯一语言就是机器语言，即机器指令代码。
3. 选项A、B、D表达式均与z合取，故只需验证选项C(C为真)的结果。
4. 2048×1024×32÷8÷1024=8192KB=8MB
5. 最少的比较次数就是刚好成不下降序，比较n-1次； 最多的比较次数是n×(n-1)/2。这里需要理解冒泡排序与该伪码的差异。常见的冒泡排序使用标记变量一般取值0或1，0表示本趟比较没交换元素，1反之。本例伪码标记的是一趟比较交换的最后元素的位置。
6. 3～5行表示函数返回的是较小值，XYZ为递归函数，故选B。
10. 捆绑法： 两个双胞胎相邻，所以方案就是4的全排列4!=24，然后双胞胎自己的全排列是2!=2,得数是24×2=48。
12. 完全二叉树的性质： 满二叉树结点数是2h-1，h为高度，计算一下即可知。［log261］=6。
14. ［方法一］10个人站成一排，每班至少要1名，就有9个空，然后插入6个板子把他们隔开，即从9个里选6个，就是C69=84。
［方法二］每班先给一个名额，问题就变成了7个班级分3个名额。3个名额： 可以分成3份，两份或者一份。总方案数就是： C37+C27+C17=35+42+7=84。
15. ［方法一］本题还是高中组合数学中的一种题型。先从5双手套中取完整的两双，方案是组合数C25=10； 然后从剩下的3双中，取不同色的两只手套是先从3双中取两双C23=3； 然后再从两双中各取一，是C12×C12=4； 最后应用乘法原理，得数是10×3×4=120。
［方法二］先选出两副成套的，然后剩余6只选1只，然后剩下的不能匹配成套的4只手套选1只，这里会出现后面两只手套先选后选导致的重复，所以方案数要除以2。总方案数就是： (C25×C16×C14)/2=120。
二、 阅读程序
1. 第5行考核字符数组初始化的概念。第12、13行循环测试encoder数组中的元素个数k，k值标识该数组的下一个可用单元。第14～25行的主要功能就是设置encoder数组的初值，第26、27行初始化数组decoder。
encoder［］={C S P A B D E F G H I J K L M N O Q R T U V W X Y Z}，共26个字母。
decoder［］={D E A F G H I J K L M N O P Q C R S B T U V W X Y Z}。
字母表={A B C D E F G H I J K L M N O P Q R S T U V W X Y Z}。
第28～30行，输入字符串st，并依据第30行的语句替换st串，显然，decoder数组中字母序号若与字母表一致，则输出结果不变。如输入字符串XYZ，则输出也是XYZ。
本例程序有点类似于加密程序，关键在于看懂程序各部分的功能。各问题均可用模拟方法解决。
2. 由于数据规模很大，要正确回答题目的问题首先要看懂题目的功能。本题的功能有点像日历表或钟表，以钟表为例： 每过60秒分针加1，每过60分钟时针加1，每过24小时日期加1……只是本题的进位制与日历时钟不一样，通过输入的k，低位由0～k-1循环一遍，高位加1，每位的进制都是k。
欲知程序的功能，最常见的方法是先模拟执行一下。假设输入n=10，k=3，则初态为： n=10，k=3，d［0］=0，len=1，ans=0； 程序核心就在于第13行开始的双重循环内。
当i=0，1时： d［0］=1,2
当i=2时： d［0］=3
第15行的循环因为len=1仍不执行，但d［len-1］=k成立，故此时有：
d［0］=0,d［1］=1,len=2,ans=1；
当i=5时： j=0时j+1<len成立，故此时有：
d［0］=0,d［1］=2,len=2,ans=2；
当i=8时： j=0时j+1<len成立，故此时有：
d［0］=0,d［1］=3,len=2,ans=3； 同时有：
d［len-1］=k，即d［1］=3成立，故此时有：
d［0］=1,d［1］=0,d［2］=1,len=3,ans=4；
程序输出4。
分析数组d的变化情况就能清楚理解程序的功能。再来看看程序输出的ans，分析代码不难发现，ans的值实际上记录的是触发进位的次数，在第13～28行的代码中，核心的是两个if语句，每个if语句都是对触发进位而修正d［］、ans及len的值。len记录的是d数组中有效数据个数，即d的实际长度。所以程序的功能是： 对于k<1的输入，实现十进制数n转换为k进制数的计数法求解过程。
(1) 用n=5,k=1简单模拟一下即可知，每次都会触发进位，即ans=n，但len=2。k=1时，这是本程序的一个特例，len值不随n增大而增大，原因在于第2个if语句只会被执行一次。
(2) 用n=2,k=2简单模拟一下即可知，ans=2,len=2。
(3) 由前面的模拟可知，输入n、k,且k<1时，外循环i从0到n-1变化，i每k次递增都会触发d［0］数据重置，即触发进位计数，而d［1］每次数据变化都会触发计数，而d［1］=k时又会触发高位计数，同理可推知d［2］，d［3］，…，d［len］的变化情况。所以有：
ans≤k0+k1+…+klen-1=(klen-1)/(k-1)
等比数列求和，当n是k的幂次时取最大值。
klen<n成立。
(5) 因为n=3,k=3时ans=1(k0)； n=9,k=3时ans=4(k0+k1)； n=27,k=3时ans=13(k0+k1+k2)……求解结果符合问题(3)的分析。故本题选A。
(6) 根据前面的分析过程可知ans是如何求解的，但限于问题规模太大，且n非k的整数幂，用模拟法求解该结果已不现实。
［方法一］利用前两题的分析过程及公式直接求解。
［方法二］本题可以利用倍数关系来求解，即每次除k(10)，而后把每次的商相加。
方法一： 利用公式求解方法二: n/k
如n=1000时会产生多少次进位呢？从百位到千位，只有1次； 从十位到百位，有10次； 从个位到十位，有100次，共计111次。即ans=k0+k1+k2=100+101+102=111。所以对非零项求解相加即可。
9
2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1
+) 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 2 0 0 0 0 9
1 0 0 0 1 0 0 0 2 0 0 0 0
1 0 0 0 1 0 0 0 2 0 0 0
1 0 0 0 1 0 0 0 2 0 0
1 0 0 0 1 0 0 0 2 0
1 0 0 0 1 0 0 0 2
1 0 0 0 1 0 0 0
1 0 0 0 1 0 0
1 0 0 0 1 0
1 0 0 0 1
1 0 0 0
1 0 0
1 0
+)1
1 1 1 1 2 2 2 2 4 4 4 4 5 31 1 1 1 2 2 2 2 4 4 4 4 5 3
［方法三］利用等比数列计算公式及程序的求解过程可以直接估算：
ans=int((n-(k-1))/(k-1))=int(100010002000081/9)=11112222444453
3. 为便于分析理解，先对程序代码进行分析并加注部分注释如下。
09void dfs(int n, int sum){//递归共进行n-1层
10if (n==1){
11ans=max(sum, ans);
12return;
13}
14for (int i=1;i<n;++i){//每层，选择数组d的第0～n-1行里相邻两行进行合并
15int a=d［i-1］［0］,b=d［i-1］［1］;
16int x= d［i］［0］, y= d［i］［1］;
17d［i-1］［0］ =a+ x;
18d［i-1］［1］ =b+ y
19for (int j=i;j<n-1;++j)//合并后把空出的地方用后面的行补上
20d［j］［0］=d［j+1］［0］， d［j］［1］=d［j+1］［1］;
21int s= a+x+ abs(b-y); /*每次sum的增加：相邻两行第0列之和加第1列之差的绝对值*/
22dfs(n-1，sum+s); //递归
23for (int j=n-1;j>i;--j)//递归返回时还原现场操作
24d［j］［0］=d［j-1］［0］, d［j］［1］=d［j-1］［1］; //后移
25d［i-1］［0］=a,d［i-1］［1］=b; /*还原的目的是用原始数据进行下一组相邻行的尝试*/
26d［i］［0］=x,d［i］［1］=y;
27}
28}
29
30int main(){
37 dfs(n, 0); //最终的ans是所有合并方案中sum值最大的
38cout<<ans<<endl;
39}
代码大意： 函数名说明是一个深搜的算法，代码基本是按照深搜模板来的。看搜的是什么：
s=a+x+abs(b-y)
ans+=s
a、b为上一行两列数字的值，x、y为本行两列数字的值，这里输入的值都为正值，所以 输出的 ans 的最大值实际就是从第二行到最后一行s 累加。
根据题目描述及加上的注释可知，本题是针对一个两列的二维数组，不断选出相邻的两行进行合并，直到合并成一行为止。结果为每次合并时相邻两行第0列之和+第1列之差的绝对值。
每次选两行会产生很多种方案，ans为其中加和最大的方案。本题与信奥经典型题“石子合并”有异曲同工之处。但此题会用更多的贪心思想。
(1) 输入n为0，什么都没做，因为第10和14行都不成立，程序会立即返回主函数，直接输出ans=0，结束程序，不会发生错误。
(2) 输入n为20，接下来的输入全为0，运算过程中所有s都是0，ans也是0。
(3) 这里减法，所以 ans 可能小于输入的 d［i］［1］,例如，若n=1，ans=0，是小于d数组的。
输入：
20023
输出：
1
(4) 第二列为0，可以忽略，用Sn表示前n项的和，这里计算的就是：
S2+S3+S4+…+S20=2×9+3×9+4×9+…+20×9=1881。
(5) 这里不会出现 b<y 的情况，所以可以去掉绝对值符号，用Sn表示前n项的和，这里计算的就是：
S1-5+S2-5+S3-5+…+S29-5=0×5+1×5+2×5+…+28×5=2030。
(6) 因为n较大，难以发现规律，可以让n=4或n=6为例，模拟执行并找出规律。
输入的两列数字是一样的，计算的内容：
s=a+x+abs(b-y)； ans+=s；
此时不会出现b<y的情况，所以可以去掉绝对值符号，x，y抵消，s=a+b，
所以ans=2×(S1+S2+S3+S4+…+S14)=2240。
本题的思维分析及计算工作量非常大，考场上需要根据自己的特点采取一些合适的策略，只有找出规律才能确保正确选择。
三、 完善程序
1. 质因数分解
(1) 因子最小为2，所以选i=2。
(2) 因子最大为n，所以选i*i。
(3) 由题目可知，一个因子可能被分解出好多次，所以选D。
(4) 分解完成后，n的值为 1 或者质数，否则还有<n的质因数。
(5) 不是1的话需要单独输出，即剩下的为质数。
2. 最小区间覆盖
本题需要非常强大的思维能力，难度较高。问题本质上其实是贪心问题中非常经典的一类问题： 线段覆盖问题。sort()函数由两重循环构成，且(2)提示是一个交换的操作，因此是冒泡排序，主函数中做了两次筛选操作。
(1) 按照区间起点进行排序，选C。
(2) 基础的交换代码，选C。
(3) 筛掉起点靠后同时终点靠前的区间，这样的区间不可能选用，选C。
(4) 此时剩余的区间逐个选用，选B。
(5) 选用最后一个区间，更新r，选B。
说明： 本题是经典的线段覆盖问题，所以不熟悉的读者需要自己补习。
1.22019入门级(CSPJ)C++语言试题A卷及解析
1.2.12019 CCF入门级(CSPJ)试题
一、 单项选择题(共15题，每题 2 分，共计 30 分； 每题有且仅有一个正确选项)
1. 中国的国家顶级域名是()。
A. .cnB. .chC. .chnD. .china
2. 二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是()。
A. 01 0010 1000 1011B. 01 0010 1001 0011
C. 01 0010 1000 0001D. 01 0010 1000 0011
3. 一个32位整型变量占用()字节。
A. 32B. 128C. 4D. 8
4. 若有如下程序段，其中s、a、b、c均已定义为整型变量，且a、c均已赋值(c<0)
s=a;
for (b=1;b<=c;b++) s=s-1
则与上述程序段功能等价的赋值语句是()。
A. s=a-c;B. s=a-b;C. s=s-c; D. s=b-c;
5. 有100个已经排好序的数据元素，采用折半查找时，最大的比较次数为()。
A. 7B. 10C. 6D. 8
6. 链表不具有的特点是()。
A. 插入删除不需要移动元素B. 不必事先估计存储空间
C. 所需要的空间与线性表长度成正比D. 可随机访问任何一个元素
7. 把8个同样的球放在5个同样的袋子里，允许有空袋子，总共有多少种分法？()
A. 22B. 24C. 18D. 20
图11
8. 一棵二叉树如图11所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的最大下标至少为()。
A. 6B. 10C. 15D. 12
9. 100以内最大的素数是()。
A. 89B. 97C. 91D. 93
10. 319与377的最大公约数是()。
A. 27B. 33C. 29D. 31
11. 小胖想减肥，教练给他制定了两套方案。方案一： 每次连续跑3km可以消耗300千卡(耗时半小时)； 方案二： 每次连续跑5km可以消耗600千卡(耗时1小时)。小胖每周周一到周四可以抽出半小时跑步，周五到周日能抽出1小时跑步。另外，教练建议小胖每周最多跑21km，否则会损伤膝盖。请问小胖每周最多通过跑步消耗多少千卡？（）
A. 3000B. 2500C. 2400D. 2520
12. 一副纸牌中除掉大小王有52张牌，4种花色，每种花色13张。假设从这52张牌中随机选择13张，则至少()张牌花色一样。
A. 4B. 2C. 3D. 5
13. 一些数字可以颠倒过来看，例如0、1、8颠倒过来还是其本身，6颠倒过来是9，9颠倒过来是6，其他数字颠倒过来则构不成数字。类似地，一些多位数也可以颠倒过来看，例如106颠倒过来是901。假如某个城市的车牌是由5位数字组成，每一位可以取0～9，问这个城市最多几个车牌颠倒过来恰好是其本身？()
A. 60B. 125C. 75D. 100
14. 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其后序遍历序列为（）。
A. ABCDEFGHIJB. ABDEGHJCFI
C. ABDEGJHCFID. ABDEGHJFIC
15. 以下哪个奖项是计算机科学科学领域的最高奖项？()
A. 图灵奖B. 鲁班奖C. 诺贝尔奖D. 普利策奖
二、 阅读程序(程序输入不超过数组或字符串定义的范围； 判断题正确填√,错误填×； 除特殊说明外，判断题每题1.5分，单选题每题3分，共计40分)
1.
01#include <cstdio>
02#include <cstring>
03using namespace std;
04char st［100］;
05int main(){
06scanf("%s", st);
07int n=strlen(st);
08for (int i=1;i<=n;++i){
09if (n % i==0){
10char c=st［i-1］;
11if (c>='a')
12st［i-1］=c-'a'+'A';
13}
14}
15printf("%s", st);
16return 0;
17}
判断题
(1) 输入的字符串只能由小写字母或大写字母组成。()
(2) 若将第8行的“i=1”改为“i=0”，程序运行时会发生错误。()
(3) 若将第8行的“i<=n”改为“i*i<=n”,程序运行结果不变。()
(4) 若输入的字符串全部由大写字母组成，那么输出的字符串就同输入的字符串一样。()
单选题
(5) 若输入的字符串长度为18,那么输入的字符串与输出的字符串相比至多有()个字符不同。
A. 18B. 6C. 10D. 1
(6) 若输入的字符串长度为()，那么输入的字符串与输出的字符串相比，至多有36个字符不同。
A. 36B. 100000C. 1D. 128
2.
01#include <cstdio>
02using namespace std;
03int n, m;
04int a［100］, b［100］;
05
06int main(){
07scanf("%d%d", &n, &m);
08for (int i=1;i<=n;++i){
09a［i］=b［i］=0;}
10for (int i=1;i<=m;++i){
11int x, y;
12scanf("%d%d", &x, &y);
13if (a［x］<y && b［y］<x){
14if (a［x］>0){
15b［a［x］］=0;}
16if (b［y］>0){
17a［b［y］］=0;}
18a［x］=y;
19b［y］=x;
20}
21}
22int ans=0;
23for (int i=1;i<=n;++i){
24if (a［i］==0){
25++ans;}
26if (b［i］==0){
27++ans;}
28}
29printf("%d", ans);
30return 0;
31}
假设输入的n和m都是正整数，x和y都是在［1, n］范围内的整数，完成下面的判断题和单选题。
判断题
(1) 当m<0时，输出的值一定小于2n。()
(2) 执行完第27行的"++ans"时，ans一定是偶数。()
(3) a［i］和b［i］不可能同时大于0。()
(4) 若程序执行到第13行时，x总是小于y，那么第15行不会被执行。()
单选题
(5) 若m个x两两不同，且m个y两两不同，则输出的值为()。
A. 2n-2mB. 2n+2C. 2n-2D. 2n
(6) 若m个x两两不同，且m个y都相等，则输出的值为()。
A. 2n-2B. 2nC. 2mD. 2n-2m
3.
01#include <iostream>
02using namespace std;
03const int maxn=10000;
04int n;
05int a［maxn］;
06int b［maxn］;
07int f(int l, int r, int depth){
08if (l>r){
09return 0;}
10int min=maxn, mink;
11for (int i=l;i<=r;++i){
12if (min>a［i］){
13min=a［i］;
14mink=i;
15}
16}
17int lres=f(l, mink-1, depth+1);
18int rres=f(mink+1, r, depth+1);
19return lres+rres+depth*b［mink］;
20}
21int main(){
22cin>>n;
23for (int i=0;i<n;++i){
24cin>>a［i］;}
25for (int i=0;i<n;++i){
26cin>>b［i］;}
27cout<<f(0, n-1, 1)<< endl;
28return 0;
29}
判断题
(1) 如果a数组有重复的数字，则程序运行时会发生错误。()
(2) 如果b数组全为0,则输出为0。()
单选题
(3) 当n=100时，最坏情况下，与第12行的比较运算执行的次数最接近的是()。
A. 5000B. 600C. 6D. 100
(4) 当n=100时，最好情况下，与第12行的比较运算执行的次数最接近的是()。
A. 100B. 6C. 5000D. 600
(5) 当n=10时，若b数组满足，对任意0<=i<n，都有b［i］=i+1，那么输出最大为()。
A. 386B. 383C. 384D. 385
(6) 当n=100时，若b数组满足，对任意0<i<71，都有b［i］=1，那么输出最小为()。
A. 582B. 580C. 579D. 581
三、 完善程序(单选题，每小题3分，共计30分)
1. (矩阵变幻)有一个奇幻的矩阵，在不停地变幻，其变幻方式为： 数字 0 变成矩阵0001数字1变成矩阵1110，最初该矩阵只有一个元素0，变幻n次后，矩阵会变成什么样？
例如，矩阵最初为［0］，矩阵变幻1次后为0001，矩阵变幻2次后为0001000100011110。
输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。试补全程序。
提示：
<<表示二进制左移运算符，例如，(11)2<<2=(1100)2
而“^ ”表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为
0，反之为 1。
01#include <cstdio>
02using namespace std;
03int n;
04const int max_size=1<<10;
05
06int res［max_size］［max_size］;
07
08void recursive(int x, int y, int n, int t){
09if (n==0){
10res［x］［y］=①;
11return;
12}
13int step=1 <<(n-1);
14recursive(②, n-1, t);
15recursive(x, y+step, n-1, t);
16recursive(x+step, y, n-1, t);
17recursive(③, n-1, !t);
18}
19
20int main(){
21scanf("%d", &n);
22recursive(0, 0,④);
23int size= ⑤;
24for (int i=0;i<size;i++){
25for (int j=0;j<size;j++)
26printf("%d", res［i］［j］);
27puts("");
28}
29return 0;
30}
(1) ①处应填()。
A. n%2B. 0 C. t D. 1
(2) ②处应填()。
A. x-step,y-stepB. x,y-step
C. x-step,y D. x,y
(3) ③处应填()。
A. x-step,y-stepB. x+step,y+step
C. x-step,y D. x,y-step
(4) ④处应填()。
A. n-1,n%2B. n,0 C. n,n%2 D. n-1,0
(5) ⑤处应填()。
A. 1<<(n+1)B. 1<<n C. n+1D. 1<<(n-1)
2. (计数排序)计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将n对10000以内的整数从小到大排序。
例如，有3对整数(3,4)、(2,4)、(3,3)，那么排序之后应该是(2,4)、(3,3)、(3,4)。
输入第一行为n，接下来n行，第i行有两个数a［i］和b［i］，分别表示第i对整数的第一关键字和第二关键字。
从小到大排序后输出。
数据范围： 1<n<107，1<a［i］,b［i］<104。
提示： 应先对第二关键字排序，再对第一关键字排序。数组ord［］存储第二关键字排序的结果，数组res［］存储双关键字排序的结果。
试补全程序。
01#include <cstdio>
02#include <cstring>
03using namespace std;
04const int maxn=10000000;
05const int maxs=10000;
06
07int n;
08unsigned a［maxn］, b［maxn］,res［maxn］, ord［maxn］;
09unsigned cnt［maxs+1］;
10
11int main(){
12scanf("%d", &n);
13for (int i=0;i<n;++i){
14scanf("%d%d", &a［i］, &b［i］);}
15memset(cnt, 0, sizeof(cnt));
16for (int i=0;i<maxs;++i){
17①; } //利用 cnt 数组统计数量
18for (int i=0;i<n;++i){
19cnt［i+1］+=cnt［i］;}
20for (int i=0;i<n;++i)
21②; //记录初步排序结果
22memset(cnt, 0, sizeof(cnt));
23for (int i=0;i<n;++i){
24③; } //利用 cnt 数组统计数量
25for (int i=0;i<maxs;++i){
26cnt［i+1］+=cnt［i］;}
27for (int i=n-1;i>=0;--i){
28④ ; //记录最终排序结果
29for (int i=0;i<n;i++){
30printf("%d %d", ⑤);}
31return 0;
32}
(1) ①处应填()。
A. ++cnt ［i］B. ++cnt［b［i］］
C. ++cnt［a［i］*maxs+b［i］］ D. ++cnt［a［i］］
(2) ②处应填()。
A. ord［cnt［a［i］］］=i B. ord［cnt［b［i］］］=a［i］
C. ord［cnt［a［i］］］=b［i］ D. ord［cnt［b［i］］］=i
(3) ③处应填()。
A. ++cnt［b［i］］B. ++cnt［a［i］*maxs+b［i］］
C. ++cnt［a［i］］D. ++cnt ［i］
(4) ④处应填()。
A. res［cnt［a［ord［i］］］］=ord［i］
B. res［cnt［b［ord［i］］］］=ord［i］
C. res［cnt［b［i］］］=ord［i］
D. res［cnt［a［i］］］=ord［i］
(5) ⑤处应填()。
A. a［i］, b［i］
B. a［res［i］］, b［res［i］］
C. a［ord［res［i］］］j b［ord［res［i］］］
D. a［res［ord［i］］］j b［res［ord［i］］］
1.2.22019 CCF入门级(CSPJ)参考答案
一、 单项选择题(共15题，每题2分，共计30分)
123456789101112131415
ADCAADCCBCCACBA
二、 阅读程序(除特殊说明外，判断题每题1.5分，单选题每题3分，共计40分)
第1题
判断题(填√或×)单选题
(1) (2) (3) (4) (5) (6)
×√×√BB
第2题
判断题(填√或×)单选题
(1) (2) (3) (4) (5) (6)
√×××AA
第3题
判断题(填√或×)单选题
(1) (2) (3) (4) (5) (6)
×√ADDB
三、 完善程序(单选题，每小题3分，共计30分)
第1题第2题
(1) (2) (3) (4) (5) (1) (2) (3) (4) (5)
CDBBBBDCAB
1.2.32019 CCF入门级(CSPJ)部分试题分析
一、 单项选择题分析
1. 信息网络常识，中国的顶级域名是.cn。
2. 逻辑位运算基本知识，当且仅当两位上均为1的时候结果才为1。
0&0=0； 1&0=0； 0&1=0； 1&1=1
3. 常识，一字节是8位，32/8=4。
4. s初始化为a，for循环执行了c次-1，所以s=a-c。
5. 即二分法，每次比较可以缩减一半的范围，26<100<27，所以查找7次。
6. 链表只能从有标记的头尾指针依次访问元素，无法随机访问。
7. 因为球和袋子一样，即求把8拆分成1～5个数有多少种方法。按个数枚举得1个数到5个数分别有1、4、5、5、3种，总共18种。
【详细分析】保证分法升序就能没有遗漏枚举了，实际考场中采用此方法是最稳妥的，可以避免推错。
问题： 把8个同样的球放在同样的5个袋子里，允许有的袋子空着不放，问共有多少种不同的分法？提示： 如果8个球都放在一个袋子里，无论是放哪个袋子，都只算同一种分法。
解析： 把问题合成，先思索5个袋子都不空的状况，再思索4个袋子不空的状况，以此类推，最后思索只运用一个袋子的状况(这种分法只要1种)，把一切子状况的分法数相加求出总分法。
进一步剖析，运用k个袋子装n个球(袋子不空)，一共有几种分法的问题能够转换为k个数相加等于n的种数问题。
运用5个袋子分8个球则有3种：
1+1+1+1+4=8
1+1+1+2+3=8
1+1+2+2+2=8
运用4个袋子分8个球则有5种：
1+1+1+5=8
1+1+2+4=8
1+1+3+3=8
1+2+2+3=8
2+2+2+2=8
运用3个袋子分8个球则有5种：
1+1+6=8
1+2+5=8
1+3+4=8
2+2+4=8
2+3+3=8
运用2个袋子分8个球则有4种：
1+7=8
2+6=8
3+5=8
4+4=8
运用1个袋子分8个球则有1种：
8=8
因而，该问题的答案即为一切子状况下的和，3+5+5+4+1=18。