冲刺CSP-J/S第一轮CSP-S2019~2022年4年真题汇总

大家好，我是老码农，这套真题汇总只包含最近4年（2019年~2022年）

• 历年真题前15道题，都是选择题

这些题目考察的都是基础知识，前15道题尽量不失分或少失分。

比较有难度的题目是15题往后的阅读程序相关的题目，

阅读程序相关的题目考察孩子C++基础和算法能力，要求会更高。

算法能力的提升不是1天2天会有质的飞跃，需要每天持之以恒的刷题，

但基础知识可以采取硬背或者适当多刷相关题目获取高分。

公众号内回复：CSP-S2023，即可获得PDF电子版及答案

CSP-S2019真题

第 1 题

若有定义：int a=7; float x=2.5, y=4.7,则表达式 x + a % 3 *（int）（x + y）% 2 的值是：（）

• A. 0.000000
• B. 2.750000
• C. 2.500000
• D. 3.500000

本题共 2 分

第 2 题

下列属于图像文件格式的有（）

• A. WMV
• B. MPEG
• C. JPEG
• D. AVI

本题共 2 分

第 3 题

二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑或运算的结果是（）。

• A. 11 1111 1101 1111
• B. 11 1111 1111 1101
• C. 10 1111 1111 1111
• D. 11 1111 1111 1111

本题共 2 分

第 4 题

编译器的功能是（）

• A. 将源程序重新组合
• B. 将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）
• C. 将低级语言翻译成高级语言
• D. 将一种编程语言翻译成自然语言

本题共 2 分

第 5 题

设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（）

• A. x= (x*100+0. 5)/100. 0;
• B. x=(int) (x*100+0. 5)/100. 0;
• C. x=(x/100+0. 5）*100. 0;
• D. x=x*100+0. 5/100. 0;

本题共 2 分

第 6 题

由数字1, 1, 2, 4, 8, 8所组成的不同的4位数的个数是（）。

• A. 104
• B. 102
• C. 98
• D. 100

本题共 2 分

第 7 题

排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

• A. 冒泡排序
• B. 直接插入排序
• C. 快速排序
• D. 归并排序

本题共 2 分

第 8 题

G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有 （）个顶点。

• A. 10
• B. 9
• C. 11
• D. 8

本题共 2 分

第 9 题

一些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是 9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901 。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）

• A. 40
• B. 25
• C. 30
• D. 20

本题共 2 分

第 10 题

—次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）。

• A. 23
• B. 21
• C. 20
• D. 22

本题共 2 分

第 11 题

设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。

• A.

• B. nlogn
• C. 2n
• D. 2n - 1

本题共 2 分

第 12 题

以下哪个结构可以用来存储图（）

• A. 栈
• B. 二叉树
• C. 队列
• D. 邻接矩阵

本题共 2 分

第 13 题

以下哪些算法不属于贪心算法？（）

• A. Dijkstra 算法
• B. Floyd 算法
• C. Prim算法
• D. Kruskal 算法

本题共 2 分

第 14 题

有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098, 中间一项是486,请问以下哪个数是可能的公比？（）

• A. 5
• B. 3
• C. 4
• D. 2

本题共 2 分

第 15 题

正实数构成的数字三角形排列形式如图所示。第一行的数为 a1,1；第二行的数从左到右依次为 a2,1，a2,2,第n行的数为an,1,an,2,……, an,n 从 a1,1开始， 每一行的数ai,j只有两条边可以分别通向下一行的两个数 ai+1,j和ai+1,j+1。用动态规划算法找出一条从 a1,1向下通到an,1，an,2,2,……, an,n中某个数的路径，使得该路径上的数之和最大。

img

令c[i] [j]是从a1,1到ai,j的路径上的数的最大和，并且C[i][0]=C[0] [j]=0,则 C[i][j] = ( )。

• A. max{C[i-1][j-1],C[i-1][j]}+ai,j
• B. C[i-1][j-1]+C[i-1][j]
• C. max{C[i-1][j-1],C[i-1][j]}+1
• D. max{C[i][j-1],C[i-1][j]}+ai,j

本题共 2 分

CSP-S2020真题

第 1 题

请选出以下最大的数（ ）。

• A. (550)10
• B. (777)8
• C.

• D. (22F)16

本题共 2 分

第 2 题

操作系统的功能是（ ）

• A. 负责外设与主机之间的信息交换
• B. 控制和管理计算机系统的各种硬件和软件资源的使用
• C. 负责诊断机器的故障
• D. 将源程序编译成目标程序

本题共 2 分

第 3 题

现有一段 8 分钟的视频文件，它的播放速度是每秒 24 帧图像，每帧图像是 一幅分辨率为 2048×1024像素的 32 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。

• A. 30G
• B. 90G
• C. 150G
• D. 450G

本题共 2 分

第 4 题

今有一空栈 S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。

• A. b
• B. a
• C. d
• D. c

本题共 2 分

第 5 题

将(2, 7, 10, 18)分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数h(x)=（ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。

• A. x2 mod 11
• B. 2x mod11
• C. x mod 11
• D. [

] mod 11，其中[

]表示

下取整

本题共 2 分

第 6 题

下列哪些问题不能用贪心法精确求解？（ ）

• A. 霍夫曼编码问题
• B. 0-1背包问题
• C. 最小生成树问题
• D. 单源最短路径问题

本题共 2 分

第 7 题

具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。

• A. O(n+e)
• B. O(n2)
• C. O(e2)
• D. O(n)

本题共 2 分

第 8 题

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

• A. 144
• B. 100
• C. 48
• D. 122

本题共 2 分

第 9 题

广度优先搜索时，一定需要用到的数据结构是( )

• A. 栈
• B. 二叉树
• C. 队列
• D. 哈希表

本题共 2 分

第 10 题

—个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 n 在以下哪个区间？已知 n<60。( ）

• A. 30<n<40
• B. 40<n<50
• C. 50<n<60
• D. 20<n<30

本题共 2 分

第 11 题

小明想通过走楼梯来锻炼身体，假设从第 1 层走到第 2 层消耗 10 卡热量， 接着从第 2 层走到第 3 层消耗 20 卡热量，再从第 3 层走到第 4 层消耗 30 卡热量，依此类推，从第 k 层走到第 k+1 层消耗 10k 卡热量 (k>l)？如果小明想从 1 层开始，通过连续向上爬楼梯消耗 1000 卡热量，至少要爬到第几层楼？ （ ）。

• A. 14
• B. 16
• C. 15
• D. 13

本题共 2 分

第 12 题

表达式 a*(b+c)-d 的后缀表达形式为（ ）。

• A. abc*+d- *
• B. -+*abcd
• C. abcd*+-

1. D. abc+*d-

本题共 2 分

第 13 题

从一个 4 × 4 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。

• A. 60
• B. 72
• C. 86
• D. 64

本题共 2 分

第 14 题

对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

• A. O((m + n2) log n)
• B. O(mn + n3)
• C. O((m + n) logn)
• D. O(n2)

本题共 2 分

第 15 题

1948年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

• A. 欧拉(Leonhard Euler)
• B. 冯·诺伊曼(John von Neumann)
• C. 克劳德·香农(Claude Shannon)
• D. 图灵(Alan Turing)

本题共 2 分

CSP-S2021真题

第 1 题

在 Linux 系统终端中，用于列出当前目录下所含的文件和子目录的命令为（ ）。

• A. ls
• B. cd
• C. cp
• D. all

本题共 2 分

第 2 题

二进制数

和

的和为（）。

• A.

• B.

• C.

• D.

本题共 2 分

第 3 题

在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。

• A. 系统分配的栈空间溢出
• B. 系统分配的队列空间溢出
• C. 系统分配的链表空间溢出
• D. 系统分配的堆空间溢出

本题共 2 分

第 4 题

以下排序方法中，（ ）是不稳定的。

• A. 插入排序
• B. 冒泡排序
• C. 堆排序
• D. 归并排序

本题共 2 分

第 5 题

以比较为基本运算，对于 2n 个数，同时找到最大值和最小值，最坏情况下需要的最小的比 较次数为（ ）。

• A. 4n−2
• B. 3n+1
• C. 3n−2
• D. 2n+1

本题共 2 分

第 6 题

现有一个地址区间为 0∼10 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储 （到 10 冲突了就从 0 开始往后），现在要依次存储 (0,1,2，3,4,5,6,7)，哈希函数为

mod 11。请问 7 存储在哈希表哪个地址中（ ）。

• A. 5
• B. 6
• C. 7
• D. 8

第 7 题

G 是一个非连通简单无向图（没有自环和重边），共有 36 条边，则该图至少有（ ）个点。

• A. 8
• B. 9
• C. 10
• D. 11

本题共 2 分

第 8 题

令根结点的高度为 1，则一棵含有 2021 个结点的二叉树的高度至少为（ ）。

• A. 10
• B. 11
• C. 12
• D. 2021

本题共 2 分

第 9 题

前序遍历和中序遍历相同的二叉树为且仅为（ ）。

• A. 只有 1 个点的二叉树
• B. 根结点没有左子树的二叉树
• C. 非叶子结点只有左子树的二叉树
• D. 非叶子结点只有右子树的二叉树

本题共 2 分

第 10 题

定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF 最少需要 ( ) 次上述操作。

• A. 7
• B. 8
• C. 9
• D. 6

本题共 2 分

第 11 题

有如下递归代码

solve(t, n):
  if t=1 return 1
  else return 5*solve(t-1,n) mod n

则 solve(23,23) 的结果为（ ）。

• A. 1
• B. 7
• C. 12
• D. 22

本题共 2 分

第 12 题

斐波那契数列的定义为：

现在用如下程序来计算斐波那契数列的第 n 项，其时间复杂度为（ ）。

F(n):
  if n<=2 return 1
  else return F(n-1) + F(n-2)

• A. O(n)
• B. O(

)

• C. O(

)

• D. O(n log n)

本题共 2 分

第 13 题

有 8 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ ）种方案。

• A. 36
• B. 48
• C. 54
• D. 64

本题共 2 分

第 14 题

设一个三位数 n= abc， a,b,c 均为 1∼9 之间的整数，若以 a、 b、 c 作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 n 有（ ）个。

• A. 81
• B. 120
• C. 165
• D. 216

本题共 2 分

第 15 题

有如下的有向图，节点为 A,B,⋯,J, 其中每条边的长度都标在图中。则节点 A 到节点J 的最短路径长度为（ ）。

• A. 16
• B. 19
• C. 20
• D. 22

本题共 2 分

CSP-S2022真题

第 1 题

在 Linux 系统终端中，用于切换工作目录的命令为（ ）。

• A. ls
• B. cd
• C. cp
• D. all

本题共 2 分

第 2 题

你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：

real 0m30.721s 
user 0m24.579s 
sys 0m6.123s

以下最接近秒表计时的时长为（ ）。

• A. 30s
• B. 24s
• C. 18s
• D. 6s

第 3 题

若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（ ）。

• A. dcebfa
• B. cbdaef
• C. bcaefd
• D. afedcb

第 4 题

考虑对 n 个数进行排序，以下最坏时间复杂度低于

的排序方法是（ ）

• A. 插入排序
• B. 冒泡排序
• C. 归并排序
• D. 快速排序

第 5 题

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ）。

• A. 移除受影响的数据后，最终序列是有序序列
• B. 移除受影响的数据后，最终序列是前后两个有序的子序列
• C. 移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列
• D. 移除受影响的数据后，最终序列基本无序

第 6 题

计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（ ）

unsigned x = 0xDEADNEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);

• A. EF、EF
• B. EF、DE
• C. DE、EF
• D. DE、DE

第 7 题

一个深度为 5（根结点深度为 1）的完全 3 叉树，按前序遍历的顺序给结点从 1 开始编号，则第 100 号结点的父结点是第（ ）号

• A. 95
• B. 96
• C. 97
• D. 98

第 8 题

强连通图的性质不包括（ ）：

• A. 每个顶点的度数至少为 1
• B. 任意两个顶点之间都有边相连
• C. 任意两个顶点之间都有路径相连
• D. 每个顶点至少都连有一条边

第 9 题

每个顶点度数均为 2 的无向图称为“2-正规图”。由编号为从 1 到 n 的顶点构成的所有 2-正规图，其中包含欧拉回路的不同 2-正规图的数量为（ ）。

• A. n!
• B. (n-1)!
• C. n!/2
• D. (n-1)!/2

第 10 题

共有 8 人选修了程序设计课程，期末大作业要求由 2 人组成的团队完成。假设不区分每个团队内 2 人的角色和作用，请问共有多少种可能的组队方案。（ ）

• A. 28
• B. 32
• C. 56
• D. 64

第 11 题

小明希望选到形如“省 A ·LLDDD”的车牌号。车牌号在“ ·”之前的内容固定不变； 后面 的 5 位号码中， 前 2 位必须是大写英文字母， 后 3 位必须是阿拉伯数字(L代表 A 至 Z，D 表示 0 至 9，两个L和三个D之间可能相同也可能不同)。请问总共有多少个可供选择的车牌号。（）

• A. 20280
• B. 52000
• C. 676000
• D. 1757600

第 12 题

给定地址区间为 0~9 的哈希表，哈希函数为 h(x) = x % 10，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 9 冲突了则从地址 0 重新开始探查）。哈希表初始为空表，依次存储(71, 23, 73, 99, 44, 79, 89)后，请问 89 存储在哈希表哪个地址中。（ ）

• A. 9
• B. 0
• C. 1
• D. 2

第 13 题

对于给定的 n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

int i, j, k = 0;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j*=2) {
        k = k + n / 2;
    }
}

• A. O(n)
• B. O(nlogn)
• C.

• D.

第 14 题

以比较为基本运算，在 n 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。

• A. n/2
• B. n-1
• C. n
• D. n+1

第 15 题

ack 函数在输入参数“(2,2)”时的返回值为（）。

unsigned ack(unsigned m, unsigned n) {
    if (m == 0) return n + 1;
    if (n == 0) return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}

• A. 5
• B. 7
• C. 9
• D. 13