2024年_CSP-S1初赛试卷

第1题中级 2.0分单选

在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（）

A. pwd

B. cd

C. ls

D. echo

第2题中级 2.0分单选

假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（）

A. O(n)

B. O(logn)

C. O(nlogn)

D. O(1)

第3题中级 2.0分单选

在C++中，以下哪个函数调用会造成栈溢出？（）

A. int foo() { return 0; }

B. int bar() { int x=1; return x; }

C. void baz() { int a[1000]; baz(); }

D. void qux() { return; }

第4题中级 2.0分单选

10名选手比赛，前三名获金银铜牌，不允许并列，不同的颁奖方式有多少种？（）

A. 120

B. 720

C. 504

D. 1000

第5题中级 2.0分单选

下面哪个数据结构最适合实现先进先出（FIFO）的功能？（）

A. 栈

B. 队列

C. 线性表

D. 二叉搜索树

第6题中级 2.0分单选

已知f(1)=1，且对于n>=2有f(n)=f(n-1)+f(n/2)，则f(4)的值为（）。

A. 4

B. 5

C. 6

D. 7

第7题中级 2.0分单选

假设有一个包含n个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（）

A. 所有顶点的度数均为偶数

B. 该图连通

C. 该图存在一个欧拉回路

D. 该图的边数是奇数

第8题中级 2.0分单选

对数组进行二分查找的过程中，以下哪个条件必须满足？（）

A. 数组必须是有序的

B. 数组必须是无序的

C. 数组长度必须是2的幂

D. 数组中的元素必须是整数

第9题中级 2.0分单选

计算n在模m意义下的乘法逆元，下列哪种算法最为适合？（）

A. 使用暴力法依次尝试

B. 使用扩展欧几里得算法

C. 使用快速幂法

D. 使用线性筛法

第10题中级 2.0分单选

哈希表有n个键值对，装载因子为a(0<a<=1)，开放地址法解决冲突，最坏情况下查找一个元素的时间复杂度为（）。

A. O(1)

B. O(logn)

C. O(1/(1-a))

D. O(n)

第11题中级 2.0分单选

一棵h层的完全二叉树，最多包含多少个结点？（）

A. 2^h-1

B. 2^(h+1)-1

C. 2^h

D. 2^(h+1)

第12题中级 2.0分单选

10个顶点的完全图，有多少个长度为4的环？（）

A. 120

B. 210

C. 630

D. 5040

第13题中级 2.0分单选

使f(f(x))=10的最小自然数x是多少？（）

A. 29

B. 199

C. 299

D. 399

第14题中级 2.0分单选

长度为n的01字符串，有k个1，每次交换相邻两个字符，最坏情况下将k个1移到最右边的交换次数是？（）

A. k

B. k*(k-1)/2

C. (n-k)*k

D. (2n-k-1)*k/2

第15题中级 2.0分单选

7个顶点的有向图，从节点1到节点7没有路径，最少删边，有多少种可行的删边集合？（）

A. 1

B. 2

C. 3

D. 4

第16题中级 1.5分判断

当1000>=d>=b时，输出的序列是有序的。（）

T. 正确

F. 错误

第17题中级 1.5分判断

当输入5 5 1时，输出为1 1 5 5 5。（）

T. 正确

F. 错误

第18题中级 1.5分判断

假设数组c长度无限制，该程序算法时间复杂度是O(b)的。（）

T. 正确

F. 错误

第19题中级 3.0分单选

函数int logic(int x, int y)的功能是（）。

A. 按位与

B. 按位或

C. 按位异或

D. 以上都不是

第20题中级 3.0分单选

（4分）当输入为10 100 100时，输出的第100个数是（）。

A. 91

B. 94

C. 95

D. 98

第21题中级 1.5分判断

假设数组dp长度无限制，函数solve()的算法时间复杂度是O(n*2^m)。（）

T. 正确

F. 错误

第22题中级 1.5分判断

输入11 2 10000000001时，程序输出两个数32和23。（）

T. 正确

F. 错误

第23题中级 1.5分判断

（2分）在n<=10时，solve()的返回值始终小于4^10。（）

T. 正确

F. 错误

第24题中级 3.0分单选

当n=10且m=10时，有多少种输入使得两行的结果完全一致？（）

A. 1024

B. 11

C. 10

D. 0

第25题中级 3.0分单选

当n<=6时，solve()的最大可能返回值为（）。

A. 65

B. 211

C. 665

D. 2059

第26题中级 3.0分单选

若n=8，m=8，solve和solve2的返回值的最大可能的差值为（）。

A. 1477

B. 1995

C. 2059

D. 2187

第27题中级 1.5分判断

假设程序运行前能自动将maxn改为n+1，算法时间复杂度是O(nlogn)。（）

T. 正确

F. 错误

第28题中级 1.5分判断

时间开销的瓶颈是init()函数。（）

T. 正确

F. 错误

第29题中级 1.5分判断

若修改常数B1或K1的值，该程序可能会输出不同的结果。（）

T. 正确

F. 错误

第30题中级 3.0分单选

在solve()函数中，h[]的合并顺序可以看作是（）。

A. 二叉树的BFS序

B. 二叉树的先序遍历

C. 二叉树的中序遍历

D. 二叉树的后序遍历

第31题中级 3.0分单选

输入10，输出的第一行是（）。

A. 83

B. 424

C. 54

D. 110101000

第32题中级 3.0分单选

（4分）输入16，输出的第二行是（）。

A. 7

B. 9

C. 10

D. 12

第33题中级 3.0分单选

序列合并问题，①处应填（）

A. an-a

B. an-a-1

C. ai

D. ai+1

第34题中级 3.0分单选

②处应填（）

A. a[mid]>ai

B. a[mid]>=ai

C. a[mid]

D. a[mid]<=ai

第35题中级 3.0分单选

③处应填（）

A. a+l

B. a+l+1

C. a+l-1

D. an-l

第36题中级 3.0分单选

④处应填（）

A. a[n-1]+b[n-1]

B. a[n]+b[n]

C. 2*maxn

D. maxn

第37题中级 3.0分单选

⑤处应填（）

A. get_rank(mid)

B. get_rank(mid)<=k

C. get_rank(mid)>k

D. get_rank(mid)>=k

第38题中级 3.0分单选

次短路问题，①处应填（）

A. upd(pre[b], n+b, dis[b], q)

B. upd(a, n+b, d, q)

C. upd(pre[b], b, dis[b], q)

D. upd(a, b, d, q)

第39题中级 3.0分单选

②处应填（）

A. make_pair(-d, b)

B. make_pair(d, b)

C. make_pair(b, d)

D. make_pair(-b, d)

第40题中级 3.0分单选

③处应填（）

A. 0xff

B. 0x1f

C. 0x3f

D. 0x7f

第41题中级 3.0分单选

④处应填（）

A. upd(a, n+b, dis[a]+c, q)

B. upd(n+a, n+b, dis2[a]+c, q)

C. upd(n+a, b, dis2[a]+c, q)

D. upd(a, b, dis[a]+c, q)

第42题中级 3.0分单选

⑤处应填（）

A. pre2[a%n]

B. pre[a%n]

C. pre2[a]

D. pre[a%n]+1

试卷题目预览

在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（ ）

假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）

在C++中，以下哪个函数调用会造成栈溢出？（ ）

10名选手比赛，前三名获金银铜牌，不允许并列，不同的颁奖方式有多少种？（ ）

下面哪个数据结构最适合实现先进先出（FIFO）的功能？（ ）

已知f(1)=1，且对于n>=2有f(n)=f(n-1)+f(n/2)，则f(4)的值为（ ）。

假设有一个包含n个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（ ）

对数组进行二分查找的过程中，以下哪个条件必须满足？（ ）

计算n在模m意义下的乘法逆元，下列哪种算法最为适合？（ ）

哈希表有n个键值对，装载因子为a(0<a<=1)，开放地址法解决冲突，最坏情况下查找一个元素的时间复杂度为（ ）。

一棵h层的完全二叉树，最多包含多少个结点？（ ）

10个顶点的完全图，有多少个长度为4的环？（ ）

使f(f(x))=10的最小自然数x是多少？（ ）

长度为n的01字符串，有k个1，每次交换相邻两个字符，最坏情况下将k个1移到最右边的交换次数是？（ ）

7个顶点的有向图，从节点1到节点7没有路径，最少删边，有多少种可行的删边集合？（ ）

当1000>=d>=b时，输出的序列是有序的。（ ）

当输入5 5 1时，输出为1 1 5 5 5。（ ）

假设数组c长度无限制，该程序算法时间复杂度是O(b)的。（ ）

函数int logic(int x, int y)的功能是（ ）。

（4分）当输入为10 100 100时，输出的第100个数是（ ）。

假设数组dp长度无限制，函数solve()的算法时间复杂度是O(n*2^m)。（ ）

输入11 2 10000000001时，程序输出两个数32和23。（ ）

（2分）在n<=10时，solve()的返回值始终小于4^10。（ ）

当n=10且m=10时，有多少种输入使得两行的结果完全一致？（ ）

当n<=6时，solve()的最大可能返回值为（ ）。

若n=8，m=8，solve和solve2的返回值的最大可能的差值为（ ）。

假设程序运行前能自动将maxn改为n+1，算法时间复杂度是O(nlogn)。（ ）

时间开销的瓶颈是init()函数。（ ）

若修改常数B1或K1的值，该程序可能会输出不同的结果。（ ）

在solve()函数中，h[]的合并顺序可以看作是（ ）。

输入10，输出的第一行是（ ）。

（4分）输入16，输出的第二行是（ ）。

序列合并问题，①处应填（ ）

②处应填（ ）

③处应填（ ）

④处应填（ ）

⑤处应填（ ）

次短路问题，①处应填（ ）

②处应填（ ）

③处应填（ ）

④处应填（ ）

⑤处应填（ ）

📝 题目纠错

💬 吐槽/建议

在Linux系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（）

假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（）

在C++中，以下哪个函数调用会造成栈溢出？（）

10名选手比赛，前三名获金银铜牌，不允许并列，不同的颁奖方式有多少种？（）

下面哪个数据结构最适合实现先进先出（FIFO）的功能？（）

已知f(1)=1，且对于n>=2有f(n)=f(n-1)+f(n/2)，则f(4)的值为（）。

假设有一个包含n个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（）

对数组进行二分查找的过程中，以下哪个条件必须满足？（）

计算n在模m意义下的乘法逆元，下列哪种算法最为适合？（）

哈希表有n个键值对，装载因子为a(0<a<=1)，开放地址法解决冲突，最坏情况下查找一个元素的时间复杂度为（）。

一棵h层的完全二叉树，最多包含多少个结点？（）

10个顶点的完全图，有多少个长度为4的环？（）

使f(f(x))=10的最小自然数x是多少？（）

长度为n的01字符串，有k个1，每次交换相邻两个字符，最坏情况下将k个1移到最右边的交换次数是？（）

7个顶点的有向图，从节点1到节点7没有路径，最少删边，有多少种可行的删边集合？（）

当1000>=d>=b时，输出的序列是有序的。（）

当输入5 5 1时，输出为1 1 5 5 5。（）

假设数组c长度无限制，该程序算法时间复杂度是O(b)的。（）

函数int logic(int x, int y)的功能是（）。

（4分）当输入为10 100 100时，输出的第100个数是（）。

假设数组dp长度无限制，函数solve()的算法时间复杂度是O(n*2^m)。（）

输入11 2 10000000001时，程序输出两个数32和23。（）

（2分）在n<=10时，solve()的返回值始终小于4^10。（）

当n=10且m=10时，有多少种输入使得两行的结果完全一致？（）

当n<=6时，solve()的最大可能返回值为（）。

若n=8，m=8，solve和solve2的返回值的最大可能的差值为（）。

假设程序运行前能自动将maxn改为n+1，算法时间复杂度是O(nlogn)。（）

时间开销的瓶颈是init()函数。（）

若修改常数B1或K1的值，该程序可能会输出不同的结果。（）

在solve()函数中，h[]的合并顺序可以看作是（）。

输入10，输出的第一行是（）。

（4分）输入16，输出的第二行是（）。

序列合并问题，①处应填（）

②处应填（）

③处应填（）

④处应填（）

⑤处应填（）

次短路问题，①处应填（）

②处应填（）

③处应填（）

④处应填（）

⑤处应填（）