PDF文档公众号回复关键字:20240915
2023 CSP-S 选择题
1单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）
6 以下连通无向图中，( )一定可以用不超过两种颜色进行染色
A 完全三叉树
B 平面图
C 边双连通图
D 欧拉图
7 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 X=x1,x2,x3,⋯,xm 和 Y=y1,y2,y3,⋯,yn，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 Z=z1,z2,z3,⋯,zk, 使得序列 Z既是序列 X 的子序列，又是序列 Y的子序列，且序列 Z的长度 k 在满足上述条件的序列里是最大的。 （注：序列 A是序列 B的子序列，当且仅当在保持序列 B元素顺序的情况下，从序列 B中删除若干个元素，可以使得剩余的元素构成序列 A。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为( )
A 4
B 5
C 6
D 7
8 一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 x点，得到 2x元；第二次掷出 y点，当 y=x时玩家会失去之前得到的 2x 元而当 y≠x 时玩家能保住第一次获得的 2x 元。上述 x,y∈1,2,3,4,5,6。 例如：玩家第 一次掷出 3 点得到 6 元后，但第二次再次掷出 3 点，会失去之前得到的 6 元，玩家最终收益为 0 元；如果玩家第一次掷出 3 点、第二次掷出 4 点，则最终收益是 6 元。假设骰子掷出任意一点的概率均为 1/6,玩家连续掷两次般子后，所有可能情形下收益的平均值是多少？( )
A 7元
B 35/6元
C 16/3元
D 19/3元
9 假设我们有以下的 C++ 代码：
int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c;
请问，res 的值是什么？（） 提示：在 C++ 中，逻辑运算的优先级从高到低依次为：逻辑非（!）、逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为：位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算；逻辑非与位非优先级相同，且高于所有双目运算符。
A true
B false
C 1
D 0
10 假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?( )
A 快速排序对于此类输入的表现最好，因为数组已经排序
B 快速排序对于此类输入的时间复杂度是 Θ(nlogn)
C 快速排序对于此类输入的时间复杂度是 Θ(n^2)
D 快速排序无法对此类数组进行排序，因为数组已经排序
2 相关知识点
1) 染色
染色给图的某类元素(点，边，面)中每个指定1种颜色，使得相邻元素有不同颜色
2) 完全三叉树
完全三叉树是一种每个节点最多有三个子节点的树结构。在这种树中，除了最底层，其他层的节点都充满，且最底层的节点从左到右依次排列
3) 平面图
一个图能画在平面上，没有边与边相交
如下2个图都是平面图
下图有边交叉，不是平面图
4) 边双连通图
如果任意两点之间，至少存在两条没有重复的边，则称改图为边双连通图
5) 欧拉图
欧拉图（Eulerian Graph）指的是可以找到一条经过每条边且仅经过一次的闭合路径的无向图或有向图。这样的路径称为欧拉回路（Eulerian Circuit）
欧拉图和欧拉回路，是从一点出发回到原点
半欧拉图
如果存在一条通过图中每条边且仅经过一次的路径，但不一定回到起点，这样的图称为半欧拉图，路径称为欧拉路径（Eulerian Path)
6) 最长公共子序列
一个序列即是X序列的子序列，也是Y序列的子序列，则该序列称为为X和Y的公共子序列。对于两个序列的公共子序列是不唯一的，因此，最长公共子序列顾名思义就是长度最长的公共子序列
7 快速排序
是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
//划分——每次划分唯一确定一个元素位置
int Partition(int A[], int low, int high)
{
int pivot = A[low]; //一般采用严蔚敏教材版本，以第一个位置为基准
while (low < high)
{
while (low < high && A[high] >= pivot)
{
--high;
}
A[low] = A[high]; //将比基准小的元素移动到左端
while (low < high && A[low] <= pivot)
{
++low;
}
A[high] = A[low]; //将比基准小的元素移动到右端
}
A[low] = pivot;
return low;
}
//快排——平均时间复杂度O(log2n)
void QuickSort(int A[], int low, int high)
{
int pivotpos;
if (low < high)
{
pivotpos = Partition(A,low,high);
//依次对划分后的子表递归排序
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
3 思路分析
6 以下连通无向图中，( A )一定可以用不超过两种颜色进行染色
A 完全三叉树
B 平面图
C 边双连通图
D 欧拉图
分析
A完全三叉树可以通过2种颜色染色，具体如下图
B平面图可能形成环，无法通过2种颜色染色
C边双连通图会形成环，无法通过2种颜色染色
D欧拉图会形成环，无法通过2种颜色染色
所以选A
7 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 X=x1,x2,x3,⋯,xm 和 Y=y1,y2,y3,⋯,yn，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 Z=z1,z2,z3,⋯,zk, 使得序列 Z既是序列 X 的子序列，又是序列 Y的子序列，且序列 Z的长度 k 在满足上述条件的序列里是最大的。 （注：序列 A是序列 B的子序列，当且仅当在保持序列 B元素顺序的情况下，从序列 B中删除若干个元素，可以使得剩余的元素构成序列 A。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为( C )
A 4
B 5
C 6
D 7
分析
根据最长公共子序列定义进行匹配，其长度为7
具体如下
8 一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 x点，得到 2x元；第二次掷出 y点，当 y=x时玩家会失去之前得到的 2x 元而当 y≠x 时玩家能保住第一次获得的 2x 元。上述 x,y∈1,2,3,4,5,6。 例如：玩家第 一次掷出 3 点得到 6 元后，但第二次再次掷出 3 点，会失去之前得到的 6 元，玩家最终收益为 0 元；如果玩家第一次掷出 3 点、第二次掷出 4 点，则最终收益是 6 元。假设骰子掷出任意一点的概率均为 1/6,玩家连续掷两次般子后，所有可能情形下收益的平均值是多少？( B )
A 7元
B 35/6元
C 16/3元
D 19/3元
分析
列出所有可能收益如下图
所有可能收益加起来
2*5+4*5+6*5+8*5+10*5+12*5=(2+4+6+8+10+12)*5=42*5=210
总共36种收益，所以平均收益
210/36=70/12=35/6
所以选B
9 假设我们有以下的 C++ 代码：
int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c;
请问，res 的值是什么( A ) 提示：在 C++ 中，逻辑运算的优先级从高到低依次为：逻辑非（!）、逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为：位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算；逻辑非与位非优先级相同，且高于所有双目运算符。
A true
B false
C 1
D 0
分析
根据运算符优先级可知，先计算位运算
a&b=5&3
101
&011
------
101 对应十进制5
c ^ b=4 ^ 3
100
^011
-------
111 对应十进制7
a | c =5 | 4
101
|100
-----
101 对应十进制5
5 || 7 && 5=5 || true = true
所以选A
10 假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?( C )
A 快速排序对于此类输入的表现最好，因为数组已经排序
B 快速排序对于此类输入的时间复杂度是 Θ(nlogn)
C 快速排序对于此类输入的时间复杂度是 Θ(n^2)
D 快速排序无法对此类数组进行排序，因为数组已经排序
分析
快速排序总是把第一个元素作为基准元素的情况，如果是已经排好序的情况，每次分成2部分中，只有一部分有数据，无法使用二分的的效率，此时等同冒泡排序的时间复杂度
A 对已经排好序的不友好，效率会更低 不正确
B 时间复杂度等同冒泡排序，Θ(n^2) 不正确
C 时间复杂度等同冒泡排序，Θ(n^2) 正确
D 可以排序，时间复杂度高一些
所以选C