CSP-S初赛错题本

一些废话

CSP-S1 2024即将到来
临时抱佛脚整理了T1-T15这些基础题

CSP-S 2020

T8

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24个顶点的二分图至多有（ ）条边。
A.144
B.100
C.48
D.122

T10

一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数n在以下哪个区间？已知n<60( ）
A.30<n<40
B.40<n<50
C.50<n<60
D.20<n<30
其实是可以枚举的。。。

CSP-S 2023

T6

以下连通无向图中，（）一定可以用不超过两种颜色进行染色：
A. 完全三叉树
B. 平面图
C. 边双连通图
D.欧拉图
“染色”即二分图，完全三叉树的染色方法为：把所有偶数层的节点染成一个颜色，奇数层的节点染成另一个颜色。

T7

A.4
B.5
C.6
D.7
最长公共子序列是ABCABA和ABAABA

T8

A.7元
B.35/6元
C.16/3元
D.19/3元
总共只有36种情况，枚举即可：
0元的有：(1,1) (2,2) …… (6,6) 共六种。
2元的有：(1,2) (1,3) …… (1,6) 共五种。
4元、6元、8元、10元、12元的情况与2元相同，各5种。
所有可能情况下的收益之和为(2+4+6+8+10+12)*5 = 210元
收益平均值为210/36即35/6

T13

A.1
B.2
C.3
D.4
找环打破即可

T14

还没看懂，找时间研究一下

T15

现在用如下代码来计算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)
当时看到快速幂直接选了C
后来发现不大对