目录
一、选择题：每题 2 分，共 15 题， 30 分. 在每小题给出的四个选项中，只有一项是符合题目要求的.
二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 3，错误填 7；除特殊说明外，判断 题每题 1.5 分，选择题每题 4 分，共 40 分)
三、完善程序(单选题，每小题 3 分，共 30 分)
2020 CCF 非专业级别软件能力认证第一轮
(CSP-S) 提高级 C++ 语言试题
1. 下列关于 NOIP 的说法， 错误的是： A
(A).NOIP 中文名称为全国青少年信息学奥林匹克联赛，将于今年恢复举行。
(B).参加 NOIP 是参加 NOI 的必要条件，不参加 NOIP 将不具有参加 NOI 的资格。
(C).NOIP 竞赛全国前五十名将获得进入国家集训队的资格。
(D).在 NOIP 复赛中， NOI 各省组织单位必须严格遵循 CCF 《关于 NOIP 数据提交格式的说明》的规范在 竞赛结束后规定时间内向 CCF 提交本赛区所有参赛选手的程序。
2. 二进制数 001001 与 100101 进行按位异或的结果为： A
(A).101000 (B).100100 (C).101101 (D).101100
3. 在 8 位二进制补码中， 10101011 表示的数是十进制下的 A 。
(A).43 (B). −43 (C). −85 (D).−84
4. 平衡树是计算机科学中的一类数据结构， 为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于 目标结点到树根的距离(即深度)，因此当结点的深度普遍较大时， 查询的均摊复杂度会上升。为了实现 更高效的查询，产生了平衡树。下列数据结构中，不属于平衡树的为： A
(A).线段树 (B).Splay 树 (C).替罪羊树 (D).红黑树
5. 组合数 (k(n)) 为从 n 件有标号物品中选出 k 件物品的方案数， 例如 (2(3)) = 3。已知 n, k ∈ N，下列说法错
误的为： A
(A). (k(n)) = (n k(−)1)+()。
(B). (2k(n))(0 ≤ k ≤ 2n) 在 k = n 时取得最大值。
(C).卡特兰数 Cn = (n(2n))/n
(D).包含 n 个 0 和 k 个 1，且没有两个 1 相邻的字符串的数量为 (nk(+)1).
6. 下列有关 CPU 的说法，正确的有 A
(A).CPU 的用途是将计算机系统所需要的显示信息进行转换驱动显示器。
(B).CPU 的性能和速度取决于时钟频率(一般以赫兹或千兆赫兹计算， 即 hz 与 Ghz) 和每周期可处理的指 令(IPC)，两者合并起来就是每秒可处理的指令(IPS)。
(C).AMD 是世界上最大的半导体公司，也是首家推出 x86 架构处理器的公司。
(D). 目前的 CPU 一般都带有 3D 画面运算和图形加速功能，所以也叫做“图形加速器”或“3D 加速器”。
7. 下列算法中， 没有用到贪心思想的算法为 A
(A).计算无向图最小生成树的 Kruskal 算法。
(B).计算无向图点双连通分量的 Tarjan 算法。
(C).计算无向图单源最短路路径的 Dijkstra 算法。
(D). 以上算法均使用了贪心的思想。
8. 在图 G = (V, E) 上使用 Bellman –Ford 算法计算单源最短路径，最坏时间复杂度为 A (A).Θ(|V ||E|) (B). Θ(|V | log |V |) (C). Θ(|E| log |E|) (D).Θ(|E|)
9. 若要使用 g++ 编译器， 开启 -Ofast 优化， 且使用 C++ 11 标准， 将源文件 prog.cpp 编译为可执行程 序 exec ，且保留调试信息，则需要使用的编译命令为 A
(A).g++ prog.cpp -Ofast exec -std=c++11 -debug
(B).g++ prog.cpp -Ofast exec -std=c++11 -g
(C).g++ prog.cpp -o exec -Ofast -std=c++11 -debug
(D).g++ prog.cpp -o exec -Ofast -std=c++11 -g
10. 已知袋子 α 中装有 4 张 5 元纸币和 3 张 1 元纸币， 袋子 β 内装有 2 张 10 元纸币与 3 张 1 元纸币， 袋 子 γ 中装有 3 张 20 元纸币与 3 张 50 元纸币。现在从每个袋子中随机选出 2 张纸币丢弃， 记第 i 个袋 子此时剩下的纸币面值之和为 vi ，则 vα < vβ < vγ 的概率为 A
(A). (B). (C). (D).
11. Hackenbush 是一款老少皆宜的双人博弈游戏。该游戏双方分别被称为红方与蓝方。游戏的局面基于一些 顶点和边， 其中边分为红色、蓝色与绿色。一些顶点长在大地上(用虚线表示)，而另一些顶点将通过边 直接与间接地与大地相连。每一局将从事先约定好的一方开始， 每一方轮流选择属于自己颜色的边， 然 后将该边删除。特别地， 对于绿色的边， 红蓝双方都可以进行删除操作。如果删除后， 某些顶点或边不 再与大地联通， 则这些顶点或边将自动被删除。如果轮到某一方时， 属于他的颜色的所有的边都被删除 了，那么他就输了整场游戏。
12. 记将 n 个有标号球， 放到若干个无标号集合， 每个集合可空的方案数为 fn 。{k(n)} 为第二类斯特林数， 其 表示将 n 个有标号球放到 k 个非空的无标号集合内的方案数。则下列说法：
(a) fn = ∑k(n)=0 {k(n)}
(b) fn = ∑ (n k(−)1)fk
(c) fn = [ ] eex −1
正确的为： A
(A).(a), (b) (B). (a), (c) (C).(c) (D).(a), (b), (c)
13. 已知参数 k，对于递归式 T (n) = k ^nT (^n) + n 的说法，正确的是 A
(A).当 k = 1 时， T (n) = Θ(n log n) (B). 当 k = 1 时， T (n) = Θ(n log2 n)
(C).当 k = 4 时， T (n) = Θ(n log n) (D).当 k = 4 时， T (n) = Θ(n log2 n)
14. 对于图 G = (V, E) 中的边 e ∈ E，我们记 G − e 表示将边 e 删除后得到的新图 G\ ，G/e 表示将 e 删除， 并将 e 的两个端点合并为一个点后得到的新图(如图所示， G/(u, v) 即为 u, v 合并为 w 后得到的图)
需要注意的是， 合并操作会保留所有的重边， 即在上图操作后， w 向外连边数为 8 而不是 7。特别地， 若 u, v 之间有多条重边，则 G/(u.v) 只会删去其中一条，其余的重边将构成新图中 w 指向自己的自环。 图 G = (V, E) 的 Tutte 多项式 是一个关于变量 x, y 的多项式，满足：
• 若 E = ?，则 T (G; x, y) = 1.
• 若 e 是 G 的一个桥边，则 T (G; x, y) = xT (G − e, x, y).
• 若 e 是 G 的一个自环，则 T = (G; x, y) = yT (G − e; x, y).
• 若 e 既不是桥边，也不是自环，则 T (G; x, y) = T (G − e; x, y) + T (G/e; x, y).
容易证明， 一张图 G 的 Tutte 多项式是唯一的。设 K4 (V, E) 为四阶完全图， e ∈ E，则 K4 − e 的 Tutte
多项式可能是： A
| (A).x3 + 2x2 + x + 2xy + y + y2 | (B).x3 + x2 + x + 2xy + y + y2 |
| (C).x3 + 2x2 + 2x + 2xy + y + y2 | (D).x3 + x2 + 2x + 2xy + y + y2 |
15. 满足 k! = ∏1 (2n − 2i ) 的正整数对 (k, n) 的数量有 A 个
(A).1 (B).2 (C).3 (D).4
(一) (12 分)阅读下面一段程序，完成 16 ∼ 21 六道小题。
给定长为 n 的序列 a ，ai 的元素均为 [0, 109 ] 内的整数。计算
对 109 + 7 取模后的值。其中 [P] 当命题 P 为真时值为 1，否则值为 0。
判断题：
16. (1 分) vec.push_back(x) 的含义为向容器 vec 的尾部插入元素 x 。 A
17. (1 分) 对于 0 ≤ i ≤ 231 − 1，语句 i&1 的含义与 i mod 2 等价。 A
18. 该程序需要注意运算时可能超出 int 类型所能容纳的最大数据的风险。 A
19. 函数 inc(x, y) 的含义为返回 (x + y) mod (109 + 7) 的值 (0 ≤ x, y < 109 + 7) 。 A 选择题：
20. (3 分) 该算法的时间复杂度为： A 。
(A).Θ(n) (B). Θ(n2 ) (C). Θ(n log2 n) (D).Θ(n log n)
21. 下列说法错误的为： A 。
(A).该算法的空间复杂度为 Θ(n)。
(B).在循环语句前执行 vec.push_back(0) 是因为 std::vector 容器下标从 0 开始计数。
(C).若将 inc 函数接收的参数类型改为 long long ，该函数仍将返回预期的结果。
(D).若要对 x, y ∈ [0, 109 + 7) 进行运算 (x − y) mod (109 + 7)，可以调用函数 inc(x, mod - y)。
(二) (13 分)阅读下面一段程序，完成 22 ∼ 27 六道小题。
提示：该程序的输入为一张 n 个点 m 条边的连通无向图。输入格式为：
• 输入的第一行包含两个整数 n, m(1 ≤ n ≤ m ≤ 100)。
• 接下来一行，包含三个整数 u, v, w(1 ≤ u, v ≤ n, 1 ≤ w ≤ 100)。
判断题：
22. (1 分) 该程序实现了用于求无向图 G = (V, E) 的最小生成树的算法。 A
23. (1 分) 程序中使用了邻接矩阵来存储图 G = (V, E) 。 A
24. 为了确保该算法的结果符合预期，输入需要保证所有的 w 互不相同。 A
25. 对于任意合法的输入，该程序一定会在有限步内返回结果。 A
选择题：
26. 变量 components 在运行过程中可达到的最小值为 A 。
(A).1 (B).0 (C).「⌋ (D).m − (n − 1)
27. 该程序的时间复杂度为 A 。
(A).Θ(nm) (B). Θ(n2 ) (C). Θ(n log n) (D).Θ(m log n)
提示：该程序的输入为一张 n 个点的连通图。
判断题：
28. (1 分) 由程序的建图方式，可以猜测输入的图 G 为一棵树。 A
29. 函数 dfs(int, int) 用于计算每个节点的深度，并存储至数组 dep[] 。 A
30. 函数 solve() 通过广度优先搜索，在树 T 上构造了一条路径。 A
31. (2 分) 程序将输出一个大小为 n 的排列。 A
选择题：
32. 该程序读入以下数据后，输出结果为： A 。
1 8
2 1 2
3 2 3
4 3 4
5 4 5
6 4 6
7 4 7
8 7 8
(A).1 3 8 7 5 6 4 2 (B).1 3 7 8 6 5 4 2 (C).1 3 8 7 5 6 2 4 (D).1 3 7 8 6 5 2 4
33. (5 分) 该程序对于给定的图 G，构造出另一个图 G\，并在 G\ 上构造某条特殊的路径。记 dG (u, v) 为图 G 中 u, v 两点的距离，则有关 G\ (V\ , E\ ) 的构造方法与找出的路径的说法，正确的为： A 。
(A).V\ = V, E\ = {(u, v) | u, v ∈ V, dG (u, v) ≤ 2}，找出的路径为哈密顿路径。
(B).V\ = V, E\ = {(u, v) | u, v ∈ V, dG (u, v) ≤ 2}，找出的路径为欧拉路径。
(C).V\ = V, E\ = {(u, v) | u, v ∈ V, dG (u, v) ≤ 3}，找出的路径为哈密顿路径。
(D).V\ = V, E\ = {(u, v) | u, v ∈ V, dG (u, v) ≤ 3}，找出的路径为欧拉路径。
(一) (15 分)阅读下面一段程序，完成 34 ∼ 38 五道小题。
对于图 G = (V, E)，我们定义它的线图 L(G) 为一张 |E| 个点的无向图，满足：
• 原图 G 中的边 e 对应 L(G) 中的一个点 u。
• L(G) 中点 u, v 之间有连边，当且仅当 G 中 u, v 对应的边有公共的顶点。 下图展示了如何通过 G 构造出 L(G)。
现在，给定一棵树 T ，你需要计算出它的 k 阶线图 Lk (T) 的点数。其中 k 阶线图的定义如下：
Lk (G) =〈 G
输入格式： 输入的第一行包含两个整数 n, k。接下来 n − 1 行，每行两个整数 u, v ，描述树中的一条边。
输出格式： 输出一行一个整数，表示答案。
数据范围： 1 ≤ k ≤ 5, 1 ≤ n ≤ 50。
(二) (15 分)阅读下面一段程序，完成 39 ∼ 43 五道小题。
给定 n 个区间 [l1 , r1 ], [l2 , r2 ], · · · , [ln , rn ]。你需要求出有多少种不同的方案， 给每个区间涂上黑白两种颜 色之一，使得任意同色区间两两交集为空集。
答案可能很大，因此要对 998, 244, 353 取模。
输入格式： 输入的第一行包含一个整数 n。接下来 n 行，每行两个整数 li , ri。
输出格式： 输出一行一个整数，表示答案。
数据范围： 1 ≤ n ≤ 106 , 1 ≤ li ≤ ri ≤ 109。
