DAY $1（2021$ CSP-J$）$

T$8$

如果一棵二叉树只有根节点，那么这棵二叉树高度为$1$。请问高度为$5$的完全二叉树有（ ）种不同的形态？

A. $16$

B. $15$

C. $12$

D. $24$

解析：

因为前$4$层肯定都是满的，所以我们只要计算最后一层叶子结点最多的数量（满二叉树下最后一层叶子结点的数量），而第$k$层叶子结点的数量为$2^{k−1}$，$2^{5−1}=16$，所以选A。

T$10$

$6$个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有（ ）种。

A. $10$

B. $15$

C. $30$

D. $20$

解析：

先计算在$6$个人里去拿出$4$个人的情况，答案为$15$。再计算在$4$个人里拿出$2$人的情况，答案为$6$。还要计算$2$个人里去拿出$2$个人的情况，答案为$1$。将这三个数相乘，$15×6×1=90$。因为队伍的编号是不区分的，所以我们还要除以一个$3$全排列的一个答案。$3$的全排列是$6$，$90÷6=15$，所以选B。

T$15$

有四个人要从A点做一条船过河到B点，船一开始在A点。该船一次最多可坐两个人。已知这四个人中每个人独自过河时间分别为$1$，$2$，$4$，$8$，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到B点（包括从B点把船开回A点的时间）。

A. $14$

B. $15$

C. $16$

D. $17$

解析：

要使时间最小，我们的安排要尽量满足以下两个条件：

• 每次回来选过河中最小的。
• 每次过去将剩下没过和的两个最大的放在一起过河。

所以根据这两个条件我们可以这样安排：

第一次：$1$和$2$坐船过河，$2$坐船回来。

第二次：$4$和$8$坐船过河，$1$坐船回来。

第三次：$1$和$2$坐船过河。

这样的话，四个人现在已经全部从A点到了B点，总时间也为$2+2+8+1+2=15$，所以选B。

DAY $3（2022$ CSP-J$）$

T$1$

以下哪种功能没有涉及C++语言的面向对象特性支持：（ ）。

A. C++中调用printf函数

B. C++中调用用户定义的类成员函数

C. C++中构造一个class或struct

D. C++中构造来源同一基类的多个派生类

解析：

printf是C语言继承过来的语言，又因为C是面向过程的，所以printf这条语句也是面向过程的，所以选A。

T$6$

对表达式a+(b-c)$*$d的前缀表达式为（ ），其中+，-，$*$是运算符。

A. $*$+a-bcd

B. +a$*$-bcd

C. abc-d$*$+

D. abc-+d

解析：

我们将式子加入括号，那么式子就是 ((a+(b-c))$*$d)，再将运算符移至前面，那么式子就是+a$*$-bcd，所以选B。

T$9$

考虑有N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

A. $N-1$

B. $N$

C. $N+1$

D. $N^2$

解析：

因为是连通图，所以每个点都要能直通其他点，我们以两个点为例，如果要这个图是连通图，那么就要$2$条边，也就是$n$条边，所以选B。

T$10$

以下对数据结构的表述不恰当的一项为：（）。

A. 图的深度优先遍历算法常使用的数据结构为栈。

B.栈的访问原则为后进先出，队列的访问原则是先进先出。

C. 队列常常用于广度优先搜索算法。

D. 栈与队列存在本质不同，无法用栈实现队列。

解析：

D选项没有说用几个栈，所以我们可以用两个栈来模拟队列，所以选D。

T$14$

一个字符串中任意连续的字符组成的子序列称为该字符串的字串，则字符串$abcab$有（ ）个内容互不相同的子串。

A. $12$

B. $13$

C. 14

D. 15

解析：

我们来枚举一下情况：

$a$

$ab$

$abc$

$abca$

$abcab$

$5$种

$b$

$bc$

$bca$

$bcab$

$4$种

$c$

$ca$

$cab$

$3$种

现在有$5+4+3=12$种，因为空串也是字符串的子串，所以还要$+1$，$12+1=13$种，所以选B。

DAY $5（2024$ SCP-J$）$

T$3$

C++语言中，以$0b$开头的数为（ ）进制数。

A. 二进制

B. 八进制

C. 十进制

D. 十六进制

解析：

二进制的简写为B，前面加个零就是$0b$，所以选A。

T$12$

以下哪一种算法典型地使用了分治法的思想来解决问题？（ ）

A. 线形搜索

B. 快速排序

C. 冒泡排序

D. 插入排序

解析：

快速排序是将数组分为两个序列，所以选B。

T$13$

奇偶校验编码是常见的校验编码方式。对于二进制编码$A_nA_{n-1}...A_2A_1$，奇偶校验编码在编码的最后一位增加一位校验位G，并将原编码与校验位作为整体发送。校验位分为奇校验位与偶校验位，奇校验位保证$A_n\operatorname{xor}A_{n-1}\operatorname{xor}...\operatorname{xor}A_2\operatorname{xor}A_1\operatorname{xor}G=1$，偶校验位保证$A_n\operatorname{xor}A_{n-1}\operatorname{xor}...\operatorname{xor}A_2\operatorname{xor}A_1\operatorname{xor}G=0$。下列编码与校验位对应正确的是（ ）。

A. 编码$11100111$ 奇校验位 $0$

B. 编码$01100010$ 偶校验位 $0$

C. 编码$00010010$ 奇校验位 $1$

D. 编码$11100010$ 奇校验位 $1$

解析：

C选项异或后的答案是$0$，跟$1$异或以后的答案是$1$，所以是对的，选C。

DAY $6（2023$ SCP-J$）$

T$1$

网址www.luogu.com.cn当中，顶级域名是（ ）。

A. www

B. cn

C. com.cn

D. luogu

解析：

cn是中国国家顶级域名。

T$7$

观察下列代码

int a[]={5,4,3,2,1};
auto p=a+3;
auto q=&p;
(*q)++;
auto k=*p;

其中，$k$的类型以及$k$的值分别为（ ）。

A. int类型，值为$1$

B. int类型，值为$3$

C. int指针类型，值为$a$数组的下标为$3$的元素的地址

D. int指针类型，值为$a$数组的下标为$4$的元素的地址

解析：

p等于$a$的第$4$个元素，q等于p的地址，q++，那么就是第$4$个元素，选A。

T$9$

一张大小为$6114×8192$的$24$位彩色图片，使用.bmp格式储存，占用的空间大小约（ ）。

A. $144$Mib

B. $188$Mib

C. $1152$Mib

D. $48$Mib

解析：

$6114×8192×24÷8÷1024≈144$，所以选A。

T$10$

以下程序片段的时间复杂度为（ ）。

int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j+=i){
			for(int k=1;k<=n;k+=j){
				++cnt;
			}
		}
	}

提示：

$$\frac{n}{1^1}+\frac{n}{2^1}+\frac{n}{3^1}+···+\frac{n}{n^1}≈C_1×logn$$$$\frac{n}{1^2}+\frac{n}{2^2}+\frac{n}{3^2}+···+\frac{n}{n^2}≈C_2$$

其中，$C_1$，$C_2$均为常数。

A. $Θ（n^2）$

B. $Θ（n^2\log{n}）$

C. $Θ（n\log{n}）$

D. $Θ（n\log^2n）$

解析：

实际上你算一下就会发现，答案是A。

T$13$

观察如下代码片段：

union U{
		bool flag1,flag2,flag3,flag4,flag5;
		signed short a;
		unsigned short b;
		enum E{
			CardA=0,CardB=1,
			CardC=2,CardD=142857
		}e;
	}u;

其中，sizeof（u）的值为（ ）。

A. $4$

B. $8$

C. $13$

D. $16$

解析：

其实这题要求的就是int的字节，int的字节是$4$，所以选A。

T$14$

已知某种可用来维护序列的数据结构，支持$Θ（\log{n}）$想某个位置后面插入元素、$Θ（n）$查询某个元素的排名，$Θ（n\log{n}）$遍历整个序列，那么用上述三种操作实现插入排序的时间复杂度最坏为（ ）。

A. $Θ（n^2）$

B. $Θ（n^2\log{n}）$

C. $Θ（n\log{n}）$

D. $Θ（n\log^2n）$

解析：

实际上这道题目就是在问你插入排序的时间复杂度，插入排序的时间复杂度为$Θ（n^2）$，所以选A。

T$15$

今年是CCF（中国计算机学会）第（ ）次举办CSP-J/S（计算机非专业级别的软件能力认证）？

A. $27$

B. $28$

C. $5$

D. $4$

解析：

CCF（中国计算机学会）是从$2019$年开始举办CSP-J/S（计算机非专业级别的软件能力认证）的，所以到$2023$年共举办了$5$年，所以选C。

DAY $7（2023$ CSP-J$）$

T$3$

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

union Data{
	int num;
	float value;
	char symbol;
}; 
union Data data;

A. data.value=$3.14$;

B. value.data=$3.14$;

C. data->value=$3.14$;

D. value->data=$3.14$;

解析：

实际上联合体与结构体的查找方式是一模一样的，联合体与结构体在本质上也没有什么区别。只是联合体它的地址是连续的，而结构体不是。

T$6$

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

A. $31$

B. $18$

C. $21$

D. $33$

解析：

这道题目直接枚举，$1$的情况有$7$种，$2$的情况有$10$种，$3$的情况有$1$种，$7+10+1=18$种，所以选B。

T$14$

一个班级有$10$个男生和$12$个女生。如果要选出一个$3$人的小组，且小组中必须至少包含$1$个女生，那么有多少种可能的组合？（ ）

A. $1420$

B. $1770$

C. $1540$

D. $2200$

解析：

我们可以用排列组合的公式来求：

有$1$个男生的情况：$C^1_{10}×C^2_{12}=660$

有$2$个男生的情况：$C^2_{10}×C^1_{12}=540$

没有男生的情况：$C^3_{12}=220$

一共有$660+540+220=1420$种组合，所以选A。

2

老师作业

DAY $3$

$1$

推规律。

	$m$
$n$	$0$	$1$	$2$	$3$
$0$		$0$	$0$
$1$			$1$
$2$			$3$	$4$
$3$			$7$	$12$
$4$			$15$	$32$
$5$			$31$	$80$
$6$			$63$	$192$
$7$			$127$	$448$

公式为：$f[i][j]=f[i-1][j]×2+f[i-1][j-1]+1$。

$2$

最多需要$6$次。

DAY $6$

总共有$190$种情况，情况如下：

第$1$种：$1$ $2$ $1$ $2$

第$2$种：$1$ $2$ $1$ $3$

第$3$种：$1$ $2$ $1$ $4$

第$4$种：$1$ $2$ $1$ $5$

第$5$种：$1$ $2$ $1$ $6$

第$6$种：$1$ $3$ $1$ $2$

第$7$种：$1$ $3$ $1$ $3$

第$8$种：$1$ $3$ $1$ $4$

第$9$种：$1$ $3$ $1$ $5$

第$10$种：$1$ $3$ $1$ $6$

第$11$种：$1$ $3$ $2$ $3$

第$12$种：$1$ $3$ $2$ $4$

第$13$种：$1$ $3$ $2$ $5$

第$14$种：$1$ $3$ $2$ $6$

第$15$种：$1$ $4$ $1$ $2$

第$16$种：$1$ $4$ $1$ $3$

第$17$种：$1$ $4$ $1$ $4$

第$18$种：$1$ $4$ $1$ $5$

第$19$种：$1$ $4$ $1$ $6$

第$20$种：$1$ $4$ $2$ $3$

第$21$种：$1$ $4$ $2$ $4$

第$22$种：$1$ $4$ $2$ $5$

第$23$种：$1$ $4$ $2$ $6$

第$24$种：$1$ $4$ $3$ $4$

第$25$种：$1$ $4$ $3$ $5$

第$26$种：$1$ $4$ $3$ $6$

第$27$种：$1$ $5$ $1$ $2$

第$28$种：$1$ $5$ $1$ $3$

第$29$种：$1$ $5$ $1$ $4$

第$30$种：$1$ $5$ $1$ $5$

第$31$种：$1$ $5$ $1$ $6$

第$32$种：$1$ $5$ $2$ $3$

第$33$种：$1$ $5$ $2$ $4$

第$34$种：$1$ $5$ $2$ $5$

第$35$种：$1$ $5$ $2$ $6$

第$36$种：$1$ $5$ $3$ $4$

第$37$种：$1$ $5$ $3$ $5$

第$38$种：$1$ $5$ $3$ $6$

第$39$种：$1$ $5$ $4$ $5$

第$40$种：$1$ $5$ $4$ $6$

第$41$种：$1$ $6$ $1$ $2$

第$42$种：$1$ $6$ $1$ $3$

第$43$种：$1$ $6$ $1$ $4$

第$44$种：$1$ $6$ $1$ $5$

第$45$种：$1$ $6$ $1$ $6$

第$46$种：$1$ $6$ $2$ $3$

第$47$种：$1$ $6$ $2$ $4$

第$48$种：$1$ $6$ $2$ $5$

第$49$种：$1$ $6$ $2$ $6$

第$50$种：$1$ $6$ $3$ $4$

第$51$种：$1$ $6$ $3$ $5$

第$52$种：$1$ $6$ $3$ $6$

第$53$种：$1$ $6$ $4$ $5$

第$54$种：$1$ $6$ $4$ $6$

第$55$种：$1$ $6$ $5$ $6$

第$56$种：$2$ $3$ $1$ $2$

第$57$种：$2$ $3$ $1$ $3$

第$58$种：$2$ $3$ $1$ $4$

第$59$种：$2$ $3$ $1$ $5$

第$60$种：$2$ $3$ $1$ $6$

第$61$种：$2$ $3$ $2$ $3$

第$62$种：$2$ $3$ $2$ $4$

第$63$种：$2$ $3$ $2$ $5$

第$64$种：$2$ $3$ $2$ $6$

第$65$种：$2$ $4$ $1$ $2$

第$66$种：$2$ $4$ $1$ $3$

第$67$种：$2$ $4$ $1$ $4$

第$68$种：$2$ $4$ $1$ $5$

第$69$种：$2$ $4$ $1$ $6$

第$70$种：$2$ $4$ $2$ $3$

第$71$种：$2$ $4$ $2$ $4$

第$72$种：$2$ $4$ $2$ $5$

第$73$种：$2$ $4$ $2$ $6$

第$74$种：$2$ $4$ $3$ $4$

第$75$种：$2$ $4$ $3$ $5$

第$76$种：$2$ $4$ $3$ $6$

第$77$种：$2$ $5$ $1$ $2$

第$78$种：$2$ $5$ $1$ $3$

第$79$种：$2$ $5$ $1$ $4$

第$80$种：$2$ $5$ $1$ $5$

第$81$种：$2$ $5$ $1$ $6$

第$82$种：$2$ $5$ $2$ $3$

第$83$种：$2$ $5$ $2$ $4$

第$84$种：$2$ $5$ $2$ $5$

第$85$种：$2$ $5$ $2$ $6$

第$86$种：$2$ $5$ $3$ $4$

第$87$种：$2$ $5$ $3$ $5$

第$88$种：$2$ $5$ $3$ $6$

第$89$种：$2$ $5$ $4$ $5$

第$90$种：$2$ $5$ $4$ $6$

第$91$种：$2$ $6$ $1$ $2$

第$92$种：$2$ $6$ $1$ $3$

第$93$种：$2$ $6$ $1$ $4$

第$94$种：$2$ $6$ $1$ $5$

第$95$种：$2$ $6$ $1$ $6$

第$96$种：$2$ $6$ $2$ $3$

第$97$种：$2$ $6$ $2$ $4$

第$98$种：$2$ $6$ $2$ $5$

第$99$种：$2$ $6$ $2$ $6$

第$100$种：$2$ $6$ $3$ $4$

第$101$种：$2$ $6$ $3$ $5$

第$102$种：$2$ $6$ $3$ $6$

第$103$种：$2$ $6$ $4$ $5$

第$104$种：$2$ $6$ $4$ $6$

第$105$种：$2$ $6$ $5$ $6$

第$106$种：$3$ $4$ $1$ $2$

第$107$种：$3$ $4$ $1$ $3$

第$108$种：$3$ $4$ $1$ $4$

第$109$种：$3$ $4$ $1$ $5$

第$110$种：$3$ $4$ $1$ $6$

第$111$种：$3$ $4$ $2$ $3$

第$112$种：$3$ $4$ $2$ $4$

第$113$种：$3$ $4$ $2$ $5$

第$114$种：$3$ $4$ $2$ $6$

第$115$种：$3$ $4$ $3$ $4$

第$116$种：$3$ $4$ $3$ $5$

第$117$种：$3$ $4$ $3$ $6$

第$118$种：$3$ $5$ $1$ $2$

第$119$种：$3$ $5$ $1$ $3$

第$120$种：$3$ $5$ $1$ $4$

第$121$种：$3$ $5$ $1$ $5$

第$122$种：$3$ $5$ $1$ $6$

第$123$种：$3$ $5$ $2$ $3$

第$124$种：$3$ $5$ $2$ $4$

第$125$种：$3$ $5$ $2$ $5$

第$126$种：$3$ $5$ $2$ $6$

第$127$种：$3$ $5$ $3$ $4$

第$128$种：$3$ $5$ $3$ $5$

第$129$种：$3$ $5$ $3$ $6$

第$130$种：$3$ $5$ $4$ $5$

第$131$种：$3$ $5$ $4$ $6$

第$132$种：$3$ $6$ $1$ $2$

第$133$种：$3$ $6$ $1$ $3$

第$134$种：$3$ $6$ $1$ $4$

第$135$种：$3$ $6$ $1$ $5$

第$136$种：$3$ $6$ $1$ $6$

第$137$种：$3$ $6$ $2$ $3$

第$138$种：$3$ $6$ $2$ $4$

第$139$种：$3$ $6$ $2$ $5$

第$140$种：$3$ $6$ $2$ $6$

第$141$种：$3$ $6$ $3$ $4$

第$142$种：$3$ $6$ $3$ $5$

第$143$种：$3$ $6$ $3$ $6$

第$144$种：$3$ $6$ $4$ $5$

第$145$种：$3$ $6$ $4$ $6$

第$146$种：$3$ $6$ $5$ $6$

第$147$种：$4$ $5$ $1$ $2$

第$148$种：$4$ $5$ $1$ $3$

第$149$种：$4$ $5$ $1$ $4$

第$150$种：$4$ $5$ $1$ $5$

第$151$种：$4$ $5$ $1$ $6$

第$152$种：$4$ $5$ $2$ $3$

第$153$种：$4$ $5$ $2$ $4$

第$154$种：$4$ $5$ $2$ $5$

第$155$种：$4$ $5$ $2$ $6$

第$156$种：$4$ $5$ $3$ $4$

第$157$种：$4$ $5$ $3$ $5$

第$158$种：$4$ $5$ $3$ $6$

第$159$种：$4$ $5$ $4$ $5$

第$160$种：$4$ $5$ $4$ $6$

第$161$种：$4$ $6$ $1$ $2$

第$162$种：$4$ $6$ $1$ $3$

第$163$种：$4$ $6$ $1$ $4$

第$164$种：$4$ $6$ $1$ $5$

第$165$种：$4$ $6$ $1$ $6$

第$166$种：$4$ $6$ $2$ $3$

第$167$种：$4$ $6$ $2$ $4$

第$168$种：$4$ $6$ $2$ $5$

第$169$种：$4$ $6$ $2$ $6$

第$170$种：$4$ $6$ $3$ $4$

第$171$种：$4$ $6$ $3$ $5$

第$172$种：$4$ $6$ $3$ $6$

第$173$种：$4$ $6$ $4$ $5$

第$174$种：$4$ $6$ $4$ $6$

第$175$种：$4$ $6$ $5$ $6$

第$176$种：$5$ $6$ $1$ $2$

第$177$种：$5$ $6$ $1$ $3$

第$178$种：$5$ $6$ $1$ $4$

第$179$种：$5$ $6$ $1$ $5$

第$180$种：$5$ $6$ $1$ $6$

第$181$种：$5$ $6$ $2$ $3$

第$182$种：$5$ $6$ $2$ $4$

第$183$种：$5$ $6$ $2$ $5$

第$184$种：$5$ $6$ $2$ $6$

第$185$种：$5$ $6$ $3$ $4$

第$186$种：$5$ $6$ $3$ $5$

第$187$种：$5$ $6$ $3$ $6$

第$188$种：$5$ $6$ $4$ $5$

第$189$种：$5$ $6$ $4$ $6$

第$190$种：$5$ $6$ $5$ $6$