2020 CSP-J（入门级）C++初赛试题全解析

一、单项选择题(共15题，每题2分，共计30分;每题有且仅有一个正确选项)

1.在内存储器中每个存储单元都被赋予-一个唯一的序号，称为(B)。
A.下标B.地址C.序号D.编号
答案B  解析：内存按地址编址
2.编译器的主要功能是(A)。
A.将源程序翻译成机器指令代码B.将一种高级语言翻译成另一一种高级语言
C.将源程序重新组合D.将低级语言翻译成高级语言
答案A: 解析：编译型：将源码直接转换为二进制代码，生成目标程序，然后将目标程序连接成可执行的程序。流程为：高级语言源码—编译—>目标程序—连接—>可执行程序。
3.设x=true，y=true，z=false，以下逻辑运算表达式值为真的是(C)。
A.(x∧y)∧zB.x∧(z∨y)∧zC)(x∧y)∨(z∨x)D.(y∨z)∧x∧z
答案：C解析：与：∧and&&    或：∨or||   非：¬!NOT  异或：^  优先级：括号＞非＞与＞异或,或

4.现有一-张分辨率为2048x1024像素的32位真彩色图像。请问要存储这张图像，需要多大的存储空间?(B)。
A.4MB  B.8MB  C.32MB   D.16MB
答案：B解析：1位为1bit,1byte=8bit,2048*1024*32/8=8*(1024/1024)=8MB

5.冒泡排序算法的伪代码如下:
输入:数组L,n≥1。
输出:按非递减顺序排序的L。
算法BubbleSort:
1.FLAG←n//标记被交换的最后元素位置
2.whileFLAG>1do
3k←FLAG-1
4FLAG←1
5forj=1tokdo
6ifL(j)>L(j+1)thendo
7.L(j)<->L(j+1)
8.FLAG←j
对n个数用以上冒泡排序算法进行排序，最少需要比较多少次?(D)。
A.n    B.n-2    C.n²    D.n-1
答案：D解析：最少的比较次数就是数组本身已经有序，只需要比较n-1次；最多的比较次数是n*(n-1)/2;

6.设A是n个实数的数组，考虑下面的递归算法:
XYZ(A[1..n])
1.if  n=1thenreturnA[1]
2.else temp←XYZ(A[1..n-1])
3.if temp<a[n]
4.then returntemp
5 else returnA[n]
请问算法XYZ的输出是什么?(</a[n]
B)。
A.A数组的平均       B.A数组的最小值

C.A数组的最大值.    D.A数组的中值

答案：B 代码解析如下，分析代码可知，题目是求n个数的最小数：

int XYZ(int a[],int n)

{

    if(n==1)

        return a[1];

    else

    {

        int temp=XYZ(a,n-1);

        return min(temp,a[n]);

    }

}

7.链表不具有的特点是(B)。
A.插入删除不需要移动元素     B.可随机访问任一元素
C.不必事先估计存储空间       D.所需空间与线性表长度成正比
答案：B解析：可随机访问任一元素是线性表的特点。
8.有10个顶点的无向图至少应该有(C)条边才能确保是一个连通图。
A.10  B.12   C.9  D.11
答案：C 解析：n个顶点的无向图，至少需要n-1条边，才能构成连通图。

9.二进制数1011转换成十进制数是(C)。
A.10  B.13  C.11  D.12
答案：C  解析：1+2+8=11

10.五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有(48)种不同排列方法?
A.24   B.36    C.72     D.48
答案：D解析：捆绑法求解：两个双胞胎是一个单位，所以方案就是4的全排列4!==24，然后双胞胎自已的全排列是2,得数是24*2==48
11.下图中所使用的数据结构是(C)。

A.哈希表    B.二叉树   C.栈   D.队列
答案：C解析：简单数据结构常识题,典型的栈结构,先进后出
12.独根树的高度为1。具有61个结点的完全二叉树的高度为(D)。
A.7     B.5      C.8         D.6
答案：D解析：完全二叉树的性质：满二叉树是(2^高度-1),数一数也可以知道了,floor(log2n)+1=6
13.干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个
天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
天干=(公历年份)除以10所得余数

例如，今年是2020年，2020除以10余数为0，查表为“庚";2020除以12,余数为4，查表为“子”，所以今年是庚子年。
请问1949年的天干地支是(B)
A.己亥B.己丑C.己卯D.己酉
答案：B解析：1949=9，因此是已 1949=5，因此是丑

14.10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有(B)种不同的分配方案。
A.56   B.84   C.72   D.504
答案：B解析：指“10个三好学生不加区分，分配进7个不同班级”，这样就是插板法组合数C₉⁶=84

15.有五副不同颜色的手套(共10只手套，每副手套左右手各1只)，一次性从中取6只手套，请问恰好能配成两副手套的不同取法有(D)种。
A.30  B.150  C.180  D.120

答案：D 解析：先从五双手套中取完整的两双，方案是组合数C(5,2)==10;
然后，从剩下的三双中，取不同色的两只手段，是先从三双中取两双C(3,2)==3
然后，再从两双中各取一，是C(2,1)*C(2,1)==4;
乘法原理，得数是10*3*4=120

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填v,错误填x;除特殊说明外，判断题1.5分，选择题3分，共计40分)

判断题
1)输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。(true)答案：true 解析：因为数组大小为26，所以只能是大写字母，如果有小写字母会越界。

2)若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。

答案：false根据decoder字符串的值，如果输入是T~Z之间的字母，输出是一样的。
3)将第12行的“i<26”改为“i<16”，程序运行结果不会改变。(true)
答案:true 解析：第12行是统计字符数，由于默认有3个字母，因此修改循环的值不影响统计结果。

4)将第26行的“i<26”改为“i<16”，程序运行结果不会改变。(false)
答案：false解析：这个程序通过encoder,decoder两次转换产生一个乱序字符串，利用乱序字符串加密encoder="CSPABDEFGHIKLMNOQRTUVWXYZ"

decoder="DEAFGHIKLMNOPQCRSBTUVWXYZ"

单选题
5)若输出的字符串为“ABCABCABCA"，则下列说法正确的是(C)。
A.输入的字符串中既有A又有P    B.输入的字符串中既有S又有B
C.输入的字符串中既有S又有P    D.输入的字符串中既有A又有B
答案：C 解析：输出中有ABC，对应decoder[2]、decoder[18]、decoder[15],则输入的字符分别为字符CSP。

6)若输出的字符串为“CSPCSPCSPCSP”，则下列说法正确的是(D)。
A.输入的字符串中既有J又有RB.输入的字符串中既有P又有K
C.输入的字符串中既有J又有KD.输入的字符串中既有P又有R
答案：D 解析：输出中有ABC，对应decoder[15]、decoder[17]、decoder[13],则输入的字符分别为字符PRN。

假设输入的n是不超过2^62的正整数，k都是不超过10000的正整数，完成下面的判断题和单选题:
判断题
1)若k=1，则输出ans时，len=n。(false)

答案：false 解析：当k为1时，n为1，1进制的1，len为2，所以错误。
2)若k>1,则输出ans时，len一定小于n。(false)

答案：false  解析：输入n为1且k>1时，ans=n
3)若k>1，则输出ans时，k^len一定大于n。(true)
代码的作用是十进制的n转换成k进制的数字，输出的ans为进位的次数,len为结果的长度。

答案：true 解析：n转化为len位的k进制数字值最大值为k^len-1，因此k^len>n。

单选题
4)若输入的n等于10^15,输入的k为1，则输出等于(D)。
A.(10^30-10^15)/2   B.(10^30+10^15)/2  C.1    D.10^15
答案：D 解析：当输入的k为1时，会直接进位，len为2，但是后面触发不了len++的条件，结果就是，len一直是2，每次d[0]++都会进位，输出ans=n

5)若输入的n等于205,891,132,094,649(即3^30)，输入的k为3，则输出等于(A)。
A.(3^30-1)/2   B.3^30   C.3^30-1  D.(3^30+1)/2
答案：A

解析：

第1位，每k次运算进位1次；

第2位，每k2次运算进位1次；

……

因此第1位，会产生3^30/3次进位，第2位会产生3^30/3^2次进位……最后一位，会产生1次进位。

因此答案=3^30/3+3^30/3^2+…+1

根据等比数列求和公式Sn=(3^30–1)/(3-1)

6)若输入的n等于100,010,002,000,090，输入的k为10，则输出等于(D)
A.11,112,222,444,543B.11,122,222,444,453
C.11,122,222,444,543D.11,112,222,444,453
答案:D

解析：

同上一问：

第1位进位次数=100010002000090/10次

第2位进位次数=100010002000090/100次

…

最后一位进位次数=1次

对上述数值求和可得D

程序解析：每次将前两项合并，并清除一项，累计计算：a+x+abs(b-y)的和。

假设输入的n是不超过50的正整数，d[i][0]、d[i][1]都是不超过
10000的正整数，完成下面的判断题和单选题:
判断题
1)若输入n为0，此程序可能会死循环或发生运行错误。(false)

答案：法false 解析：输入n为0，什么都没做，结束程序。
2)若输入n为20，接下来的输入全为0，则输出为0。(true)

答案：true 解析：全是0，运算过程中所有s都是0，ans也是0
3)输出的数一定不小于输入的d[i][0]和d[i][1]的任意一个。(false)

答案：false 解析：这里减法，所以ans可能小于输入的d[i][1],例如输入：00和55  输为0

单选题
4)若输入的n为20，接下来的输入是20个9和20个0，则输出为(C)。
A.1917B.1908C.1881D.1890
答案：C 解析：第二列为0，可以忽略。第1次合并：9+9=9*2第2次合并：18+9=9*3第3次合并：27+9=9*4 …第19次合并：9*29 因此和=9*2+9*3+…+9*20=1881

5)若输入的n为30，接下来的输入是30个0和30个5，则输出为(B)。
A.2020B.2030C.2010D.2000
答案：B 解析：第1次合并：5-5=0 第2次合并：5+5-5=5=5*1 第3次合并：10+5-5=10=5*2

… 第29次合并：5*30-5=5*28 求和=5*(1+2+…+28)=2030

6)(4分)若输入的n为15，接下来的输入是15到1，以及15到1，则输出为(D)。
A.2420   B.2220  C.2440  D.2240
答案 ：D 解析：对于第1列：第1次合并=15+14第2次合并=15+14+13…第14次合并=15+14+13+12+…+1  15*14+14*14+13*13+…+1*1=1225 对于第2列：第1次合并=15-14 第2次合并=15+14-13 第3次合并=15+14+13-12……第14次合并=15+14+13+12+…+2-1 15*13+14*12+…+3*1=1001，这里加上14个1  最终答案是：2240

三、完善程序(单选题，每小题3分，共计30分)
1.
(质因数分解)给出正整数n,请输出将n质因数分解的结果，结果从小
到大输出。
例如:输入n=120,程序应该输出22235，表示120=2*2*2*3*5。输入保证2≤n≤10^9。
提示:先从小到大枚举变量i，然后用i不停试除n来寻找所有的质因子。
试补全程序。

1)处应填(D)
A.n-1   B.0  C.1  D.2

答案：D解析：因子最小为2，所以选i=2

2)处应填(D)
A.n/I  B.n/(i*i)   C.i*i*I  D.i*i

答案：D 解析：因子最大为根号n所以选i*i

3)处应填(D)
A.if(i*i<=n) B.if(n%i==0)  C.while(i*i<=n) D.while(n%i==0)

答案：D解析：由题目可知，一个因子可能被分解出好多次

4)处应填(A)
A.n>1   B.n<=1   C.i+i<=n   D.i<n i<="" span="">

答案：A解析：分解完成后，n的值为1或者质数，判断剩余的是不是质数。

5)处应填(D)
A.2   B.i  C.n/I  D.n
答案：D 解析：不是1的话需要单独输出

2.(最小区间覆盖)给出n个区间，第i个区间的左右端点是[a_i,b_i]。现在要在这些区间中选出若干个，使得
区间[0,m]被所选区间的并覆盖(即每一个0≤i≤m都在某个所选的区间中)。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数n和m(1≤n≤5000,1≤m≤10°)。
接下来n行，每行两个整数ai,bi;(0≤ai,bi≤m)。
提示:使用贪心法解决这个问题。先用θ(n2)的时间复杂度排序，然后贪心选择这些区间。
试补全程序。

1)处应填(C)
A.A[j].bA[j-1].b
C.A[j].aA[j-1].a

答案：C 解析：按照区间起点进行排序

2)处应填(C)
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;
答案：C 解析：变量交换代码
3)处应填(C)
A.A[i].bA[i-1].b
C.A[i].b>A[p-1].bD.A[i].b<a[i-1].b
</a[i-1].b
答案：C解析：筛掉起点靠后同时终点靠前的区间，因为这样的区间完整的被前面选中的区间包含了。

4)处应填(B)
A.q+1<n&&a[q+1].b<=r
B.q+1<n&&a[q+1].a<=r
C.q<n&&a[q].a<=r
D.q<n&&a[q].b<=r
</n&&a[q].b<=r
</n&&a[q].a<=r
</n&&a[q+1].a<=r
</n&&a[q+1].b<=r
答案：B解析：此时剩余的区间逐个选用，优先选用能和前一个区间连接的情况下，右端点更靠右的区间

5)处应填(B)
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++

答案：B解析：更新r为当前选中区间的右端点的值