2023年信息学CSP-S组初赛真题及参考答案

2023-09-20 13:52|编辑: 常老师|阅读: 1184

摘要

2023信息学CSP-J/S初赛已经结束，本文整理了2023年信息学CSP-S组初赛真题及参考答案，供考生参考。

2023信息学CSP-J/S认证，分别举行第一轮认证、第二轮认证。CSP-J/S认证分入门级和提高级两个组别，难度不同。CSP-J/S第一轮为集中笔试；第二轮为现场集中上机认证。2023年9月16日上午11:30，CSP-J 2023第一轮认证结束，以下为本次比赛真题及参考答案

2023年信息学CSP-S组初赛真题及参考答案

一、单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）

1 在Linux系统终端中，以下那个命令用于创建一个新的目录（）

A newdir

B mkdir

C create

D mkfold

答案 B

2 由0,1,2,3,4中选取4个数字，能组成（）个不同四位数注:最小的四位数是1000最大的四位数是9999

A 96

B 18

C 120

D 84

答案 A

3 假设n 是图的顶点的个数,m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法,对于m=O（n）的稀疏图而言下面的四个选项，哪一项的渐近时间复杂度最小

A O（m*sqrt（logn）*loglogn）

B O（n^2+m）

C O（n^2/logm+mlogn）

D O（m+nlogn）

答案 A

4 假设有n 根柱子，需要按照以下规则依次放置编号为1、2、3、...的圆环:每根柱子的底部固定，顶部可以放入圆环，每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时，最多可以放置（）个圆环

A 7

B 9

C 11

D 5

答案 C

5 以下对数据结构的表述不恰当的一项是

A 队列是一种先进先出（FIFO）的线性结构

B 哈夫曼树的构造过程主要是为了实现图的深度优先搜索

C 散列表是一种通过散列函数将关键字映射到存储位置的数据结构

D 二又树是一种每个结点最多有两个子结点的树结构

答案 B

6 以下连通无向图中，（）一定可以用不超过两种颜色进行染色

A 完全三叉树

B 平面图

C 边双连通图

D欧拉图

答案 A

7 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x1,x2,x3,...xm}和Y={y1,y2,y3...yn},最长公共子序列（LCS）问题的目标是找到一个最长的新序列Z= {z1,z2,z3...zk},使得序列既是序列X 的子序列，又是序列Y的子序列，且序列Z的长度k 在满足上述条件的序列里是最大的。（注:序列A 是序列B 的子序列，当且仅当在保持序列B 元素顺序的情况下，从序列B中删除若千个元素，可以使得剩余的元素构成序列A。测序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为（）

A 4

B 5

C 6

D 7

答案 C

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

答案 B

9 假设我们有以下的C++代码:

inta=5,b=3,c=4;

bool res= a&b||c^b && a|c

提示:在 C++中，逻辑运算的优先级从高到低依次为: 逻辑非（!）逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为: 位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算:逻辑非和位非优先级相同，且高于所有双目运算符

A true

B false

C 1

D 0

答案 A

10 假设快速排序算法的输入是一个长度为n的已排序数组，且该快速排序算法在分治过程总是选择第1个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

A 快速排序对于此类输入的表现最好因为数组已经排序

B 快速排序对于此类输入的时间复杂度是O（nlogn）。

C 快速排序对于此类输入的时间复杂度是O（n^2）

D 快速排序无法对此类数组进行排序因为数组已经排序

答案 C

11 以下哪个命令，能将一个名为“main.cpp”的 C++源文件，编译并生成一个名为"main“的可执行文件? （）

A g++ -o main main.cpp

B g++ -o main.cpp main

Cg++main -o main.cpp

D g++ main.cpp -o main.cpp

**答案 A **

12 在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心（）

A 4个结点的树

B 6个结点的树

C 7个结点的树

D 8个结点的树

答案 C

13 如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边?

A 1

B 2

C 3

D 4

答案 C

A 10

B 11

C 12

D 13

答案 B

15 现在用如下代码来计算x^n，其时间复杂度为（）

double quick_power（double x,unsigned int 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）

答案 A

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

01 #incTude<iostream>

02 using namespace std;

03

04 unsigned short f（unsigned short x） {

05 x ^=x << 6;

06 x ^=x >> 8;

07 return x;

08 }

09

10 int main（） {

11 unsigned short x;

12 cin >> x;

13 unsigned short y = f（x）;

14 cout << y << end1;

15 return 0;

16 }

假设输入的x是不超过65535的自然数，完成下面的判断题和单选题

判断题

16 当输入非零时，输出一定不为零（）

答案 T

17 将f函数的输入参数的类型改为unsigned int，程序的输出不变（）

答案 F

18 当输入为“65535”时，输出为“63”（）

答案 T

19 当输入为“1”时，输山为“64”。

答案 F

单选题

20 当输入为“512”时，输出为（）

A “33280” B “33410” C “33106” D “33346"

答案 B

21 当输入为“64”时，执行完第5行后x的值为（）

A "8256” B “4130” C “4128” D “4160“

答案 D

判断题

22 将第15 行删去，输出不变（）

答案 F

23 当输入为“10”时，输出的第一行大于第二行。（）

答案 F

24 当输入为“1000”时，输出的第一行与第二行相等（）

答案 T

单选题

25 solve1（n）的时间复杂度为（）

答案 D

26 solve2（n）的时间复杂度为（）

A O（n^2） B O（n） C O（nlogn） D O（nsqrt（n））

答案 B

27 输入为”5”时，输出的第二行为（）

A 20 B 21 C 22 D 23

答案 B

判断题

28 将第24行的“m”改为“m-1”，输出有可能不变，而剩下情况为少1。（）

答案 T

29 将第22行的“g +（h-g）/2改为“（h+g）>>1”，输出不变。（）

答案 T

30 当输入为“5 7 2 -4 5 1 -3”，输出为”5”。（）

答案 T

单选题

31 设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（）

答案 C

32 将第10行中的”>”替换为”>=”，那么原输出与现输出的大小关系为（）

A 一定小于 B 一定小于等于且不一定小于 C 一定大于等于且不一定大于 D 以上三种情况都不对

答案 B

33 当输入为“5 8 2 -5 3 8 -1 2”时，输出为（）

A"13"B"14"C"8"D"15"

答案 B

三、完善程序（单选题，每小题3分，共计 3 分）

1第k小路径

给定一张n个点 m 条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第k小的路径。保证存在至少 k条路径，上述参数满足1<=n,m<=10^5 和1<=k<=10^18表示 .在程序中，我们求出从每个点出发的路径数量。超过10^18的数都用 10^18表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。

试补全程序。

34 ①处应该填写（）

Ak>=f[u]Bk<=f[u]Ck>f[u]Dk < p=""> <>

答案 B

35 ②处应该填写（）

Adeg[v]==1Bdeg[v]==0Cdeg[v]>1Ddeg[v]>0

答案 A

36 ③处应该填写（）

Astd::min（f[u]+f[v],LIM）

Bstd::min（f[u]+f[v]+1,LIM）

Cstd::min（f[u]*f[v],LIM）

Dstd::min（f[u]*（f[v]+1）,LIM）

答案 A

37 ④处应该填写（）

Au!=1B!E[u].empty（）Ck>0Dk>1

答案 D

38 ⑤处应该填写（）

Ak+=f[u]Bk-=f[u]C--kD++k

答案 C

2 最大值之和

给定整数序列 a0...an-1，求该序列所有非空连续子序列的最大值之和。上述参数满足1<=n<=10^5 和 1<=ai<=10^8

一个序列的非空连续子序列可以用两个下标l和r（其中0 <=l<=r<=n）表示，对应的序列为al,al+1,...ar。两个非空连续子序列不同，当且仅当下标不同

例如，当原序列为[1,2,1,2] 时，要计算子序列[1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2] 的最大值之和，答案为 18。注意[1,1]和[2,2] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算.解决该问题有许多算法，以下程序使用分治算法时间复杂度 O（nlogn）。

试补全程序