冲刺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合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。

n^2

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.

2^{10}

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. [

frac x 2

] mod 11，其中[

frac x 2

]表示

frac x 2

下取整

本题共 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* -

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 题

二进制数

00101010_2

和

00010110_2

的和为（）。

00111100_2

01000000_2

00111100_2

01000010_2

本题共 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)，哈希函数为

h(x)=x^2

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 题

有如下递归代码

代码语言：javascript复制

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 题

斐波那契数列的定义为：

F_1=1，

F_2=1，

F_n=F_{n−1} F_{n−2}(n≥3)

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

代码语言：javascript复制

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

A. O(n)
B. O(

n^2

)

C. O(

2^n

)

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 命令的输出如下：

代码语言：javascript复制

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 个数进行排序，以下最坏时间复杂度低于

O(n^2)

的排序方法是（）

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

第 5 题

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

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

第 6 题

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

代码语言：javascript复制

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，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。

代码语言：javascript复制

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.

O(nsqrt n)

O(n^2)

第 14 题

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

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

第 15 题

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

代码语言：javascript复制

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

存储二叉树排序算法系统

0 人点赞