CSP-J 2020 入门级 第一轮（初赛） 答案及解析

1. 在内存储器中每个存储单元都被赋予一个唯一的序号，称为（）。
   A. 地址
   B. 序号
   C. 下标
   D. 编号

答: A
计算机中每个存储单元都是1字节，都有唯一的地址。

2. 编译器的主要功能是（ ）。
   A. 将源程序翻译成机器指令代码
   B. 将源程序重新组合
   C. 将低级语言翻译成高级语言
   D. 将一种高级语言翻译成另一种高级语言

答: A
源程序是高级语言程序，如C++程序代码、Java程序代码。
编译器将源程序翻译成的是机器语言，也就是机器指令代码。因此选A。
将源程序重新组合的是连接器。
将低级语言翻译成高级语言的是反编译器。
将一种高级语言翻译成另一种高级语言的是转译器。

3. 设x=true,y=true,z=false，以下逻辑运算表达式值为真的是（ ）。
   A. (y∨z)∧x∧z
   B. x∧(z∨y)∧z
   C. (x∧y)∧z
   D. (x∧y)∨(z∨x)

答: D
A选项中最后有∧z，z为false，无论前面表达式的值为什么，任何值∧false的结果都为false，因此A的值为false。
B选项最后也有∧z，z为false，因此B的值为false。
C选项最后也有∧z，z为false，因此C的值为false。
D选项，x∧y值为true, z∨x值为true，true∨true结果为true，选D。

4. 现有一张分辨率为2048×1024像素的32位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）。
   A. 16MB
   B. 4MB
   C. 8MB
   D. 2MB

答: C
已知存储空间单位之间的关系
$1B=8b$
$1KB=1024B=2^{10}B$
$1MB=1024KB=2^{10}KB$
每个像素为32位，由于1字节=8位，32位即为4字节。
该图像占用空间$2048\ast 1024\ast 4B=2^{11}\ast 2^{10}\ast 2^2=2^{23}B=2^{13}KB=2^{3}MB=8MB$。

5. 冒泡排序算法的伪代码如下：
   输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
   算法 BubbleSort：

   1. FLAG ← n //标记被交换的最后元素位置2. while FLAG > 1 do3.     k ← FLAG -14.     FLAG ← 15.     for j=1 to k do6.         if L(j) > L(j+1) then do7.              L(j)  ↔ L(j+1)8.              FLAG ← j

对n个数用以上冒泡排序算法进行排序，最少需要比较多少次?（ ）。
A. $n^2$
B. $n-2$
C. $n-1$
D. $n$

答: C
该算法对冒泡排序做了优化，flag是上一次冒泡过程中，最后一次交换的数对的第一个数的位置。
因此在下一次进行冒泡排序前，可以保证从位置flag到位置n的元素都已经排好序了。
如果flag为1，则整个序列已经有序，排序结束。
否则进入while循环，由于从第flag个数到第n个数已经有序了，设k为flag-1，只需要对第1到第k个数进行排序。所以接下来j从1到k循环。
这是一趟冒泡过程，只要第j个数大于第j+1个数，二者交换。flag初值设为1，在冒泡过程中只要第j和第j+1个数，发生交换，将flag设为发生交换的数对中第一个数的位置。
该优化可以使得当数列接近有序时，减少冒泡过程中交换元素的次数。
当初始序列就是非递减序列时，k被设为flag-1，也就是n-1。进入while循环，flag被设为1，接下来的for循环中，总共执行k次循环，也就是执行了$n-1$次比较。没有任何一个位置j满足L(j) > L(j+1)，flag的值还是1。下一次循环时，不满足flag>1，跳出。
因此比较次数最少时，比较了$n-1次$

6. 设A是n个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])if n=1 then return A[1]else temp ← XYZ (A[1..n-1])if temp < A[n]then return tempelse return A[n]

请问算法 XYZ 的输出是什么？（）。
A. A 数组的平均
B. A 数组的最小值
C. A 数组的中值
D. A 数组的最大值

答: B
XYZ函数传入一个数组A，下标1到n。
当n不为1时，使用XYZ处理A数组下标1到n-1，返回值为temp。接下来返回temp和A[n]的较小值。
不断进行递归调用，缩小问题规模，直到n为1时，返回A[1]。
XYZ(A[1…2])这一次调用中，返回值temp为A[1]，A[n]为A[2]，返回的是A[1]和A[2]的较小值。
XYZ(A[1…3])这一次调用中，返回值temp为A[1…2]的最小值，A[n]为A[3]，求二者的最小值，返回的是A[1…3]的最小值小值。
依此类推，可知XYZ(A[1…n-1])返回值temp是A[1…n-1]的最小值，再和A[n]比较，返回的是A[1…n]的最小值，即A数组的最小值，选B。

7. 链表不具有的特点是（）。
   A. 可随机访问任一元素
   B. 不必事先估计存储空间
   C. 插入删除不需要移动元素
   D. 所需空间与线性表长度成正比

答: A
线性表是逻辑结构，链表是线性表的一种物理结构，是一种具体实现。另一种物理结构是顺序表。
A. 随机访问指的是可以以$O(1)$复杂度取到线性表中的第i个元素，如果该线性表是顺序表，是可以进行随机访问的。如果是链表，则必须从链表第1个顶点开始，通过第1个顶点找到第2个顶点，通过第2个顶点找到第3个顶点…重复执行直到找到第i个顶点，该过程的复杂度为$O(n)$，这样的访问过程不是随机访问。因此A是错的，选A。
B. 如果实现的是动态链表，进行添加或插入结点时，从堆区动态申请内存空间。在进行删除时，将申请的内存空间返还。这样就不需要预估存储空间。
C. 链表进行插入、删除操作只需要改变结点之间的连接关系即可完成，复杂度为$O(1)$，不需要移动元素。而顺序表进行插入、删除操作需要移动元素。
D. 线性表的长度就是线性表中元素的数量。对于线性表中的每个元素，链表都要为其建立一个结点，每个结点占用内存空间大小相同。如果线性表中有n个元素，实际需要从内存申请n个结点的空间，所需空间与线性表长度是成正比的。

8. 有10个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
   A. 9
   B. 10
   C. 11
   D. 12

答: A
连通图边最少时是一个树（无环连通无向图），树有n个顶点时有n-1条边。10个顶点的树有9条边，选A。

9. 二进制数1011转换成十进制数是（ ）。
   A. 11
   B. 10
   C. 13
   D. 12

答: A
其它进制数字转十进制的方法为按位权展开：$1\ast 2^3+0\ast 2^2+1\ast 2^1+1\ast 2^0=11$

10. 5个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（）种不同排列方法?
    A. 48
    B. 36
    C. 24
    D. 72

答: A
捆绑法，将两个双胞胎小朋友“捆绑”在一起，形成一个元素，剩下每个小朋友是一个元素，共4个元素，先进行全排列，方案数为$P(4,4)$，这两个小朋友内部的排列有$P(2,2)$种，根据乘法原理，最终有$P(4,4)\ast P(2,2)=4\ast 3\ast 2\ast 1\ast 2\ast 1=48$种排列方法，选A。

11. 下图中所使用的数据结构是（ )。
    
    A. 栈
    B. 队列
    C. 二叉树
    D. 哈希表

答: A
只在线性表的一端进行操作（包括插入、删除，取数据）的数据结构是栈。

12. 独根树的高度为1。具有61个结点的完全二叉树的高度为（ ）。
    A. 7
    B. 8
    C. 5
    D. 6

答: D
有n个结点的完全二叉树的高度为$\lfloor {\log }_{2}n\rfloor +1$（原理见完全二叉树的相关性质证明)
由于$32<61<64$
所以$2^5<61<2^6$
不等式取以2为底的对数
${\log }_2{2}^5<{\log }_{2}61<{\log }_2{2}^6$
$5<{\log }_{2}61<6$
$\lfloor {\log }_{2}61\rfloor +1=5+1=6$，选D。

13. 干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
    

天干 =（公历年份）除以10所得余数
地支 =（公历年份）除以12所得余数
例如，今年是2020年，2020 除以10余数为0，查表为"庚”；
2020 除以12，余数为4，查表为“子” 所以今年是庚子年。
请问1949年的天干地支是（ ）
A. 己酉
B. 己亥
C. 己丑
D. 己卯

答: C
$1949\mathrm{mod}10=9$，查表为“己”
$1949\mathrm{mod}12=5$，查表为“丑”
所以1949年的天干地支是“己丑”，选C。

14. 10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。
    A. 84
    B. 72
    C. 56
    D. 504

答: A
10个三好学生名额是完全相同的，将其分配到7个班级。这是将相同小球放入不同盒子的模型，可以使用插板法完成。
一共10个相同的小球放入7个不同的盒子，相当于把10个相同的小球放成一行，在10个小球之间的9个空隙中插入6个相同的板子，方案数为$C(9,6)=C(9,3)=(9\ast 8\ast 7)/(3\ast 2\ast 1)=84$，选A。

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

答: A
方法1：6只手套中有两副也就是4只手套完成了配对，还剩下2只手套无法完成配对。首先从5副手套中选择2副完成配对的手套，有$C(5,2)$种情况，接下来要在3副手套中找两只无法配对的手套：可以是两只手套都是左手，或右手，有$2C(3,2)$种情况，或者两只手套一只是左手，一只是右手。左手手套有3种选择，左手手套确定后右手选与左手手套不是一副的手套有2种选择，因此有$3\ast 2$种，因此总取法有$C(5,2)\ast (2C(3,2)+3\ast 2)=(5\ast 4)/2\ast (2\ast 3+3\ast 2)=10\ast 12=120$，选A。
方法2：使用补集转化思路，首先在5副手套中选择2副完成配对的手套，有$C(5,2)$种情况，而后要在3副手套中选出2只手套无法完成配对，我们先考虑在3副手套共6只手套中选出2只手套的所有情况，共有$C(6,2)$种情况，从中减去两只手套能配对的3种情况，剩下的就是不能配对的情况。总取法数为$C(5,2)\ast (C(6,2)-3)=(5\ast 4)/2\ast (6\ast 5/2-3)=10\ast 12=120$

二、阅读程序

阅读程序(1)
阅读程序(2)
阅读程序(3)

三、完善程序

完善程序(1)
完善程序(2)