# CSP-J 2023 第一轮试题

CSP-J 2023 第一轮试题

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？
   A. unsigned
   B. const
   C. static
   D. mutable

答：选B。
声明常量的格式是 const 数据类型 常量名 = 常量值;，例：const double PI = 3.14;

2. 八进制数$12345670_8$ 和$07654321_8$的和为（）。
   A. $22222221_8$
   B. $21111111_8$
   C. $22111111_8$
   D. $22222211_8$

答：选D
列竖式，两数相加，逢8进1。
12345670
07654321
--------------
22222211

3. 阅读下述代码，请问修改data的value成员以存储3.14，正确的方式是（ ）。

union Data {
    int num;
	float value;
	char symbol;
};
union Data data;
1
2
3
4
5
6

A. data.value = 3.14;
B. value.data = 3.14;
C. data->value = 3.14;
D. value->data = 3.14;

答：选A。
考察联合体union。一个union内可以定义多种不同的数据类型， 一个某union类型的变量中，允许装入该union中所定义的任何一种数据，这些数据共享同一段内存，以达到节省空间的目的。
联合体类型的变量通过点(.)来取其成员。data.value = 3.14的意思就是将变量data所表示的内存当做float类型，保存3.14这一值。

4. 假设有一个链表的节点定义如下：

struct Node {
    int data;
    Node* next;
};
1
2
3
4

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使
新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;

答：选A
考察单链表头插法。注意head指向的不是头结点，而是“链表头部”，也就是第一个结点。
先从堆区申请结点Node* newNode = new Node;，然后给新结点设值newNode->data = 42;，接下来把新结点的下一个结点设为链表的第一个结点newNode->next = head;，最后把指向第一个结点的指针head指向新结点head = newNode;。

5. 根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）。
   A. 6
   B. 7
   C. 8
   D. 9

答：选C
节点数固定，三叉树高度最小时，应该是上面每层都是满的，最下面一层可能不满。
考虑满三叉树每层结点数
第1层 1个
第2层 3个
第3层 9个
…
第h层 $3^{h-1}$个
h层满三叉树的总结点数为：$3^0+3^1+...+3^{h-1}=(3^h-1)/2$
当h为7时，7层满三叉树的总结点数为$(3^7-1)/2=1093$。
当h为8时，8层满三叉树的总结点数为$(3^8-1)/2=3280$。
2023个结点的三叉树结点数大于7层满三叉树的结点数，小于8层满三叉树的结点数，因此该三叉树的高度为8层。想让该树层数更多很容易，排成一条链，高度就是2023。因此一个拥有2023个节点的三叉树高度至少为8。

6. 小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有（ ）种选择时间段的方案。
   A. 31
   B. 18
   C. 21
   D. 33

答：选B
考察递推。
将问题抽象：有个7位二进制数，其中至少1位是1，要求两个1之间至少有两个0，请问这样的二进制数的个数。
d[i]表示i位二进制数中至少有1位是1，两个1之间至少有两个0的情况数。
易知d[1] = 1，d[2] = 2，d[3] = 3。
当i > 3时，
如果第i位置放1，则第i-1，i-2位置必须是0，情况数为前i-3位至少1位是1，相邻两个1之间至少两个0的的情况数，为d[i-3]，以及前i-3位全是0的情况，有1种。共d[i-3]+1种情况。
如果第i位置放0，前i-1位至少1位是1，相邻两个1之间至少两个0的情况数为d[i-1]
因此：d[i] = d[i-1]+d[i-3]+1。
d[4] = d[3]+d[1]+1 = 5
d[5] = d[4]+d[2]+1 = 8
d[6] = d[5]+d[3]+1 = 12
d[7] = d[6]+d[4]+1 = 18

7. 以下关于高精度运算的说法错误的是（ ）。
   A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算。
   B. 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
   C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
   D. 高精度加法运算的关键在于逐位相加并处理进位。

答：选C
A. 高精度计算可以处理大整数的保存和计算，对于保留多位小数的运算，可以采用定点数的形式，在高精度的数字数组中人为规定小数点的位置（即将小数写成整数乘以基数的幂的形式，而后进行整数运算)，即可完成定点数小数高精度运算。
如$1.2\ast 7.3$，可以写成：$120\ast 10^{-2}\ast 734\ast 10^{-2}=120\ast 734\ast 10^{-4}$，进行整数乘法运算后，得到$87600\ast 10^{-4}$，输出时，指定在倒数第4位前输出小数点。
B. 描述了除法竖式的书写过程，高精除低精运算确实就是在模拟除法竖式，B选项描述正确。
C. 高精度乘法的运算时间与参与运算的两个整数的位数都有关，如果两个整数的位数分别为m和n，那么高精乘高精的复杂度为$O(mn)$
D. 描述正确

8. 后缀表达式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”对应的中缀表达式是（ ）
   A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3
   B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
   C. (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3
   D. 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3

答：选A
关于通过后缀表达式建立表达式树的方法，可以进入洛谷 P1449 后缀表达式，看里面的解法2。
先根据后缀表达式建表达式树。得到：

而后中序遍历表达式树，遍历子树得到的中缀表达式两边要加括号，即可得到中缀表达式。

9. 数$101010_2$和$166_8$的和为（ ）。
   A. $10110000_2$
   B. $236_8$
   C. $158_{10}$
   D. $A{0}_{16}$

答：选D
1位8进制数字转为3位2进制数字。1位16进制数字转为4位2进制数字。把数字都尽量转为二进制数字进行比较。
$166_8=1110110_2$，$101010_2+1110110_2=10100000_2$
将各选项转为二进制：$236_8=10011110_2$，$A{0}_{16}=10100000_2$
将$158_{10}$转为8进制，使用除基取余法：
158/8=19…6
19/8=2…3
2/8=0…2
所以$158_{10}=236_8$，与B选项相同。
综上，只有D选项的值与题目给定的两个数字的加和相同。

10. 假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字
    符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）
    A. 1111，1110，101，100，110，0
    B. 1010，1001，1000，011，010，00
    C. 000，001，010，011，10，11
    D. 1010，1011，110，111，00，01

答：选A
构建哈夫曼树，每个结点自己是一棵树，权值是相应的频率（相对大小）。每次循环选择权值最小的两棵树，合并为一棵树，新的树的权值是两棵子树的权值加和。

得到哈夫曼树后，将每个结点连接到左右孩子的边上分别标注0与1（必须一个是0，一个是1，哪边是0哪边是1无所谓），从根结点到叶子结点的路径经过的边上的数字合起来就是该叶子结点表示的字符的哈夫曼编码。
我们不能确定具体各条边上标的是0还是1，但可以确定每个字母的哈夫曼编码的位数。根据哈夫曼树，a与b一定是4位，c,d,e一定是3位，f一定是1位。只有A选项满足这种情况。

11. 给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历
    结果是什么？（ ）
    A. EDBGFCA
    B. EDBGCFA
    C. DEBGFCA
    D. DBEGFCA

答：选A
二叉树已知前序中序求后序，方法参考信息学奥赛一本通 1339：【例3-4】求后序遍历
。
前序遍历根结点A，中序遍历中找到根结点A。
左子树的前序遍历序列：BDE，中序遍历序列：DEB
根结点B，左子树中序：DE，左子树前序：DE。
根结点D，看左子树中序，得到右孩子是E。
右子树的前序遍历序列：CFG，中序遍历序列：CFG
根结点C，右子树中序：FG，右子树前序：FG
根结点F，右孩子G。

对其进行后序遍历的结果是EDBGFCA，选A。

12. 考虑一个有向无环图，该图包括4条有向边：(1,2)，(1,3)，(2,4)，和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）
    A. 4，2，3，1
    B. 1，2，3，4
    C. 1，2，4，3
    D. 2，1，3，4

答：选B。
根据求拓扑排序的Kahn算法，每次删掉一个入度为0的顶点，删掉顶点的顺序就是拓扑排序。
该图的拓扑排序可以是1 2 3 4，或1 3 2 4。选B。

13. 在计算机中，以下哪个选项描述的数据存储容量最小？（ ）
    A. 字节（byte）
    B. 比特（bit）
    C. 字（word）
    D. 千字节（kilobyte）

答：选B
字节(byte)，简称B。比特(bit)，简称b。千字节(kilibyte)，简称KB。
有换算关系：1B=8b, 1KB = 1024B。
字(word)，即该计算机的字长。一个32位计算机的一个字(word)就是32位。字一定大于字节。
因此，比特描述的数据存储容量最小。

14. 一个班级有10个男生和12个女生。如果要选出⼀个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）
    A. 1420
    B. 1770
    C. 1540
    D. 2200

答：选A
方法1：正向思考。3人小组中至少包含1个女生，可以是2男1女，1男2女，或3女。情况数为：$C_{10}^2{C}_{12}^1+C_{10}^1{C}_{12}^2+C_{12}^3=540+660+220=1420$
方法2：逆向思考，补集转化。至少包含1个女生的情况数，为选出3人小组的总情况数减去不包含女生的情况数。不包含女生，即3人是3个男生。
情况数为：$C_{22}^3-C_{10}^3=1540-120=1420$

15. 以下哪个不是操作系统？（ ）
    A. Linux
    B. Windows
    C. Android
    D. HTML

答：选D
HTML是超文本标记语言，用来编写网页需要用到的语言之一。Linux，Windows，Android都是操作系统。

二、阅读程序

阅读程序(1) 第16-20题
阅读程序(2) 第21-26题
阅读程序(3) 第27-32题

三、完善程序

完善程序（1） 第33-37题
完善程序（2） 第38-42题