PDF文档公众号回复关键字:20240917

2023 CSP-S 选择题

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

11 以下哪个命令，能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？( )
A g++ -o main main.cpp
B g++ -o main.cpp main
C g++ main -o main.cpp
D g++ main.cpp -o main.cpp

12 在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？( )
A 4 个结点的树
B 6 个结点的树
C 7 个结点的树
D 8 个结点的树

13 如图是一张包含 6 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 6 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？( )

A 1
B 2
C 3
D 4

14
A 10
B 11
C 12
D 13

15 现在用如下代码来计算 x^n，其时间复杂度为( )

double quick_power(double x, unsigned n) {if (n == 0) return 1;if (n == 1) return x;return quick_power(x, n / 2)* quick_power(x, n / 2)* ((n & 1) ? x : 1);
}

A O(n)
B O(1)
C O(logn)
D O(nlogn)

2 相关知识点

1) 编译命令

g++ 是 GNU C++ 编译器，它是 GNU 编译器套件（GCC）的一部分。g++ 用于编译 C++ 程序，将源代码转换为可执行文件。它可以处理 C++ 标准库和其他 GNU 库，以及用户自定义的头文件和库

基本用法

要使用 g++ 编译一个 C++ 程序，你需要在命令行中输入以下命令：

g++ -o output_file source_file.cpp

其中，output_file 是生成的可执行文件名，source_file.cpp 是 C++ 源代码文件

g++ 是 GNU C++ 编译器，它是 GNU 编译器套件（GCC）的一部分。g++ 用于编译 C++ 程序，将源代码转换为可执行文件。它可以处理 C++ 标准库和其他 GNU 库，以及用户自定义的头文件和库。

基本用法

要使用 g++ 编译一个 C++ 程序，你需要在命令行中输入以下命令：

g++ -o output_file source_file.cpp

其中，output_file 是生成的可执行文件名，source_file.cpp 是 C++ 源代码文件。

编译选项

g++ 提供了许多编译选项，以便你可以控制编译过程。以下是一些常用选项：

-c：仅编译源代码，生成目标文件（.o 文件），不进行链接。
-I：指定头文件的搜索路径。
-L：指定库文件的搜索路径。
-l：链接指定的库文件。
-std：指定 C++ 标准版本，如 c++11、c++14、c++17 等。
-Wall：显示所有警告信息。
-Werror：将警告视为错误，即在出现警告时停止编译

2) 树的重心

树的重心是图论中的一个重要概念，指的是树中的一个顶点，当从这个顶点出发，将树分成若干个子树时，每个子树中的节点数都尽可能平衡。换句话说，树的重心是使得删除该点后得到的所有连通分量中，节点数最多的分量所含节点数最小的那个点

例如如下树

如果根节点为1，去除1节点后，节点最多的分量包括2个节点，具体如下下图，此时节点数最小

去除其他点，节点最多的连通分量会超过2，例如下图情况为3

一个树可能有个多个重心，奇数个节点的树只有1个重心，例如上面举例情况

3) 拓扑排序

拓扑排序是一个有向无环图（DAG）的所有顶点的线性序列

每个顶点只能出现一次，如果A到B节点有路径，且A节点在B节点的前面，那么B节点不能在A节点的前面

下图是一个有向无环图

拓扑排序方法

1从 DAG 图中选择入度为0的顶点（即没有节点指向该节点）并输出，并删除此节点
上图中A符合
输出A 并删除A后，变成下图

2从 DAG 图中选择入度为0的顶点（即没有节点指向该节点）并输出，并删除此节点
上图中B符合
输出B 并删除B后，变成下图

3从 DAG 图中选择入度为0的顶点（即没有节点指向该节点）并输出，并删除此节点
上图中C符合
输出C 并删除C后，变成下图

4从 DAG 图中选择入度为0的顶点（即没有节点指向该节点）并输出，并删除此节点
上图中D符合
输出D 并删除D后，只剩下节点E，此时输出节点E所以上图拓扑排序为ABCDE

4) 进制转换

R进制转十进制

按权展开，但要注意各个位的权，最低位（最右边）的权是0次方，权值为1

(11010110)2=1×2^7+1×2^6+0×2^5+1×2^4+0×2^3+1×2^2+1×2^1+0×2^0=(214)10

十进制整数转R进制

十进制小数转R进制

3 思路分析

11 以下哪个命令，能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？( A )
A g++ -o main main.cpp
B g++ -o main.cpp main
C g++ main -o main.cpp
D g++ main.cpp -o main.cpp

根据g++编译语法
g++ 编译选项 目标文件 源文件
所以选A

12 在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？( C )
A 4 个结点的树
B 6 个结点的树
C 7 个结点的树
D 8 个结点的树

奇数个节点的树只有一个重心
所以选C

13 如图是一张包含 6 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 6 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？( C )

A 1
B 2
C 3
D 4

分析

根据拓扑排序的规则
1先删掉入度为0的点，此时2为入度为0的点
删除2后，没用入度为0的点，但允许删1条边，只有删除1条边满足也可以
2 此时有1 3 4这3个节点的入度为0，都可以删除
3 删除4->1这条边，此时入度为0的点为1，逐步删除1，3，4，5，6
4接2 ，删除1->3,此时入度为0的点为3，逐步删除3，4，1，5，6
5接2，删除，3->4,此时入度为0的点为4，逐步删除4，1，3，5，6
所以有3条边可以被删除，选C

14
( B )

A 10
B 11
C 12
D 13

分析

由题目可知
i=0时，n=16^0*x0
i=1时，n=16^0*x0+16^1*x1
i=2时，n=16^0*x0+16^1*x1+16^2*x2
和16进制转10进制计算规则相同
例如
(100)16=16^0*0+16^1*1+16^2*1=256f(0)=x0
f(1)=x0+x1
f(2)=x0+x1+x2
可以看出，f(n)是计算16进制中各位的数字和需要找一个数列,需要满足，例如如下图满足不动点为9
n2=f(1)=f(264)=9
n3=f(2)=f(9)=9
此种情况还有，108,117,126,135,144,153,162,171,180共9个

还有一种情况，需要2次后为9，分别有2种情况，19E和18F
共2种，和前面9种一共11种
所有选B

需要2次后为9，第1次为除了18，还有27，36，45，54，63，72，81
如果为27此时，数列前1个最小的16进制为9FF，而题目的范围(100)16~(1A0)超出范围
因此大于27的36，45也会超出范围

15 现在用如下代码来计算 x^n，其时间复杂度为( A )

double quick_power(double x, unsigned n) {if (n == 0) return 1;if (n == 1) return x;return quick_power(x, n / 2)* quick_power(x, n / 2)* ((n & 1) ? x : 1);
}

A O(n)
B O(1)
C O(logn)
D O(nlogn)

分析

递归排序时间复杂度有2部分组成
1递归的调用次数
2每次递归调用执行的时间复杂度
此题每次递归调用的时间复杂度为简单运算，可以看作1
递归调用次数，每次2分，并且分成2部分，所以总调用次数为n
所以时间复杂度为O(n),选A