2022年CSP-J初赛
一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）
1420
1770
1540
2200
在计算机中，以下哪个选项描述的数据存储容量最小？（ ）
字节（byte）
比特（bit）
字（word）
千字节（kilobyte）
考虑一个有向无环图，该图包括4条有向边：(1,2)，(1,3)，(2,4)，和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）
4，2，3，1
1，2，3，4
1，2，4，3
2，1，3，4
给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）
EDBGFCA
EDGBFCA
DEBGFCA
DBEGFCA
假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）
1111，1110，101，100，110，0
1010，1001，1000，011，010，00
000，001，010，011，10，11
1010，1011，110，111，00，01
数1010102和1668的和为（ ）。
101100002
2368
15810
A016
后缀表达式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”对应的中缀表达式是（ ）
((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3
6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
(6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3
6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3
以下关于高精度运算的说法错误的是（ ）。
高精度计算主要是用来处理大整数或需要保留多位小数的运算。
大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。
小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明一共有（ ）种选择时间段的方案。
31
18
21
33
根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）。
6
7
8
9
假设有一个链表的节点定义如下：
struct Node {
int data;
Node* next;
};
现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）
Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
Node* newNode = new Node; newNode->data = 42; head->next = newNode;
Node* newNode = new Node; newNode->data = 42; newNode->next = head;
阅读下述代码，请问修改data的value成员以存储3.14，正确的方式是（ ）。
union Data{
int num;
float value;
char symbol;
};
union Data data;
data.value = 3.14;
value.data = 3.14;
data->value = 3.14;
value->data = 3.14;
八进制数123456708 和076543218的和为（ ）。
222222218
211111118
221111118
222222118
在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）。
unsigned
const
static
mutable
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特 殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
第1题 判断
16. 删去第 7 行与第 13 行的 unsigned，程序行为不变。
第2题 判断
17. 将第 7 行与第 13 行的 short 均改为 char，程序行为不变。
第3题 判断
18. 程序总是输出一个整数“0”。
第4题 判断
19. 当输入为“2 2”时，输出为“10”。
第5题 判断
20. 当输入为“2 2”时，输出为“59”。
第6题 单选
21. 当输入为“13 8”时，输出为（ ）。
A.“0”
B. “209”
C. “197”
D. “226”
第1题 判断
当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）
第2题 判断
输出的两行整数总是相同的。（ ）
第3题 判断
当 m 为 1 时，输出的第一行总为 n。（ ）
第4题 单选
算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。
第5题 单选
当输入为“20 2”时，输出的第一行为（ ）。
4
5
6
20
第6题 单选
当输入为“100 100”时，输出的第一行为（ ）。
6
7
8
9
假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：
第1题 判断
28.该算法最准确的时间复杂度分析结果为O(logn+k)
第2题 判断
29.当输入为“9801 1”时，输出的第一个数为“99”。
第3题 判断
30.对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。
第4题 判断
31.该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）
第5题 单选
32.当输入为“2 1”时，输出的第一个数最接近（ ）。
A. 1
B. 1.414
C. 1.5
D. 2
第6题 单选
33.当输入为“3 10”时，输出的第一个数最接近（ ）。
A. 1.7
B. 1.732
C. 1.75
D. 2
第7题 单选
34.当输入为“256 11”时，输出的第一个数（ ）。
A. 等于16
B. 接近但小于16
C. 接近但大于16
D. 前三种情况都有可能
第1题 单选
①处应填（ ）
n % i == 0
n % i == 1
n % (i-1) == 0
n % (i-1) == 1
第2题 单选
②处应填（ ）
n / fac[k]
fac[k]
fac[k]-1
n / (fac[k]-1)
第3题 单选
③处应填（ ） A. B. C. D.
(i-1) * (i-1) == n
(i-1) * i == n
i * i == n
i * (i-1) == n
第4题 单选
④处应填（ ） A. B. C. D.
n-i
n-i+1
i-1
I
第5题 单选
⑤处应填（ ）
n / fac[k]
fac[k]
fac[k]-1
n / (fac[k]-1)
（2）（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给 定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色 都与起始像素颜色相同），替换为给定的颜色。试补全程序。
第1题 单选
①处应填（ ）
image[r][c] == prev_color
image[r][c] != prev_color
image[r][c] == new_color
image[r][c] != new_color
第2题 单选
②处应填（ ）
image[cur.r+1][cur.c] = new_color
image[cur.r][cur.c] = new_color
image[cur.r][cur.c+1] = new_color
image[cur.r][cur.c] = prev_color
第3题 单选
③处应填（ ）
Point(pt.r, pt.c)
Point(pt.r, pt.c+1)
Point(pt.r+1, pt.c)
Point(pt.r+1, pt.c+1)
第4题 单选
④处应填（ ）
prev_color = image[p.r][p.c]
new_color = image[p.r][p.c]
image[p.r][p.c] = prev_color
image[p.r][p.c] = new_color
第5题 单选
⑤处应填（ ）
queue.push(p)
queue.push(pt)
queue.push(cur)
queue.push(Point(ROWS,COLS))
以下哪个不是操作系统？（ ）
Linux
Windows
Android
HTML