2024年信息学奥赛CSP-S1提高组初赛真题试卷

选择题

第 1 题单选题

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

pwd

echo

第 2 题单选题

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

O(n)

O(log n)

O(n log n)

O(1)

第 3 题单选题

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

int foo( return 0; )

Int bar( int x=1; return x)

Void baz(){int a[1000]; baz();}

Void qux(){return;}

第 4 题单选题

在一场比赛中，有 10 名选手参加，前三名将获得金银铜牌，若不允许并列，且每名选手只能获得一枚铜牌，则不同的颁奖方式共有多少种？（）

120

720

504

1000

第 5 题单选题

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

栈

队列

线性表

二叉搜索树

第 6 题单选题

一直 f(1) = 1,且对于 n>=2 有 f(n) = f(n − 1) + f( n/2 ) ,则 f(4)的值为：（）

第 7 题单选题

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

所有顶点的度数均为偶数

该图联通

该图存在一个欧拉回路

该图的边数是奇数

第 8 题单选题

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

数组必须是有序的

数组必须是无序的

数组长度必须是 2 的幂

数组中的元素必须是整数

第 9 题单选题

考虑一个自然数 n 以及一个模数 m，你需要计算 n 的逆元（即 n 在模 m 意义下的乘法逆元）。下列哪种算法最为合适？（）

使用暴力方法依次尝试

使用扩展欧几里得解法

使用快速幂解法

使用线性筛法

第 10 题单选题

在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和和冲突解决策略。已知某哈希表中有 n 个键值对，表的装载因子为α（0<α<=1）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为（）

O(1)

O(log n)

O (1/(1-α))

O(n)

第 11 题单选题

假设有一颗 h 层的完全二叉树，该树最多包含多少个节点（）

2^h− 1

2^（h+1）− 1

2^h

2^h+1

第 12 题单选题

设有一个 10 个顶点的完全图，每两个顶点之间都有一条边，有多少个长度为 4 的环？（）

120

210

630

5040

第 13 题单选题

对于一个整数 n，定义 f(n)为 n 的各个位数之和，问使 f(f(x))=10 的最小自然数 x 是多少？（）

199

299

3999

第 14 题单选题

设有一个长度为 n 的 01 字符串，其中有 k 个 1，每次操作可以交换相邻两个字符。在最坏的情况下将这 k 个 1 移到字符串最右边所需要的交换次数是多少？（）

K*(k-1)/2

(n-k)*k

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

第 15 题单选题

如图是一张包含 7 个顶点的有向图。如果要删除一些边，使得从节点 1 到节点 7 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（）

阅读程序

第 16-20 题组合题

2024 CSP-S1阅读程序题（1）（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×，除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

第16题判断

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

正确

错误

第17题判断

当输入“5 5 1”时，输出为“1 1 5 5 5”（）

正确

错误

第18题判断

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

正确

错误

第19题单选

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

按位与

按位或

按位异或

以上都不是

第20题单选

当输入为“10 100 100”时，输出的第 100 个数是（）

第 21-26 题组合题

2024 CSP-S1阅读程序题（2）

第21题判断

假设输入的 s 是包含 n 个字符的 01 串，函数 solve()所实现的算法时间复杂度是 O(n*2^m)。（）

正确

错误

第22题判断

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

正确

错误

第23题判断

在 n<=10 时，solve()的返回值始终小于4¹⁰（）

正确

错误

第24题单选

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

1024

第25题单选

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

211

665

2059

第26题单选

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

1477

1995

2059

2187

第 27-32 题组合题

2024 CSP-S1阅读程序题（3）

第27题判断

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

正确

错误

第28题判断

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

正确

错误

第29题判断

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

正确

错误

第30题单选

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

二叉树的 BFS 序

二叉树的先序遍历

二叉树的中序遍历

二叉树的后序遍历

第31题单选

输入“10”，输出的第一行是？（）

424

110101000

第32题单选

输入“16”，输出的第二行是？（）

完善程序

第 33-37 题组合题

合并序列：有两个长度为 N 的单调不降序列 A 和 B，序列的每个元素都是小于 10^9的非负整数。在 A 和 B 中各取一个数相加可以得到 N^2 个和，求其中第 k 小的和。上述参数满足 N<=10^5 和 1<=K<=N^2

第33题单选

1）处应填（）

an-a

an-a-1

ai+1

第34题单选

(2)处应填（）

a[mid]>ai

a[mid]>=ai

a[mid]<ai <="" p="">

a[mid]<=ai

第35题单选

(3)处应填（）

a+l

a+l+1

a+l-1

an-l

第36题单选

(4)处应填（）

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

a[n]+b[n]

2*maxn

maxn

第37题单选

(5)处应填（）

get_rank(mid)<k <="" p="">

get_rank(mid)<=k

get_rank(mid)>k

get_rank(mid)>=k

第 38-42 题组合题

次短路：已知有一个 n 个点 m 条边的有向图 G，并且给定图中的两个点 s 和 t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行“-1”。如果存在，输出两行，第一行表示此段路经的长度，第二行表示此段路的一个方案

第38题单选

(1)处应填（）

udp(pre[b],n+b,dis[b],q)

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

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

upd(a,b,d,q)

第39题单选

(2)处应填（）

make_pair(-d,b)

make_pair(d,b)

make_pair(b,d)

make_pair(-b,d)

第40题单选

(3)处应填（）

0xff

0x1f

0x3f

0x7f

第41题单选

(4)处应填（）

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

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

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

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

第42题单选

(5)处应填（）

pre2[a%n]

pre[a%n]

pre2[a]

pre[a%n]+1

答题卡

选择题

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

阅读程序

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

完善程序

33 34 35 36 37 38 39 40 41 42