[C++知识库]2020 CCF 非专业级别软件能力认证第一轮(CSP-S) 提高级 C++ 语言试题

目录

一、选择题：每题 2 分，共 15 题， 30 分. 在每小题给出的四个选项中，只有一项是符合题目要求的.

二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 3，错误填 7；除特殊说明外，判断 题每题 1.5 分，选择题每题 4 分，共 40 分)

三、完善程序(单选题，每小题 3 分，共 30 分)

2020 CCF?非专业级别软件能力认证第一轮

(CSP-S) 提高级 C++ 语言试题?

一、选择题：每题 2 分，共 15 题， 30 分. 在每小题给出的四个选项中，只有一项是符合题目要求的.

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 ????

15. ?满足 k! = ∏1 (2n??? 2i?) 的正整数对 (k, n) 的数量有 ?????A?????个

(A).1 ?????????????????????????????????????(B).2 ?????????????????????????????????????(C).3??????????????????????????????????????(D).4

?

二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 3，错误填 7；除特殊说明外，判断 题每题 1.5 分，选择题每题 4 分，共 40 分)

(一) ????(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}，找出的路径为欧拉路径。

三、完善程序(单选题，每小题 3 分，共 30 分)

(一) ????(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。

?

?

?