全部知识点
假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 m=O(n)的稀疏图而言，下面的四个选项，哪一项的渐进时间复杂度最小？（）
假设有n 根柱子，需要按照以下规则依次放置编号为 1,2,3..的圆柱：每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4个根子时，最多可以放置（）个圆环。
以下对数据结构表述不恰当的一项是？（）
以下连通无向图中，（）一定可以用不超过两种颜色进行染色。
最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列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”的最长公共子序列长度为（）
一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出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,玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少?（）
假设我们有以下的C++代码：
int a=5,b=3,c=4; bool res = a & b ||c ^ b && a | c;
请问，res的值是什么?（）
提示：在C++中，逻辑运算的优先级从高到低依次为：逻辑非(!)、逻辑与(&&)、逻辑或(I)。位运算的优先级从高到低依次为：位非(~)、位与(&)、位异或(^)、位或(I)。同时，双目位运算的优先级高于双目逻辑运算；逻辑非和位非优先级相同，且高于所有双目运算符。
假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?（）
以下哪个命令，能将一个名为”main.cpp“的 C++源文件，编译并生成一个名为”main“的可执行文件?（）
在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数量最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?（）
如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）
若
，定义
；其中
对于给定自然数n0，存在序列n0,n1,n2,...,nm,其中对于
都有ni=f(ni-1)且nm=nm-1，称nm为n0关于f的不动点，问在10016至1A016中，关于f的不动点为9的自然数个数为（ ）。
现在用如下代码来计算xn,其时间复杂度为（）。
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);
}2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入非零时，输出一定不为零。（）
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
将f函数的输入参数的类型改为 unsigned int，程序的输出不变。（）
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“65535”时，输出为“63”。（）
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“1”时，输出为“64”。（）
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“512”时，输出为()。
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“64”时，执行完第5行后x的值为(）。
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
将第15行删去，输出不变。（）
