7
CSP-J 入门组押题
一、单项选择题(15道,CSP-J选择考点:计算机基础、C++语法、复杂度、基础算法)
1. 下列不属于计算机存储单位的是()
A. Byte B. KB C. Hz D. GB
2. 十进制数25转二进制是()
A. 11001 B.10101 C.10011 D.11100
3. C++中,bool类型取值不可能是()
A. true B. false C. 1 D. 2
4. 表达式 3 * (1 + 2) > 5 && 7 % 2 == 1 的结果是()
A. 0 B. 1 C. false D. 报错
5. 循环 for(int i=2;i<10;i+=3) 循环次数()
A.2 B.3 C.4 D.5
6. 数组int a[20];下标合法范围()
A.0~20 B.1~20 C.0~19 D.1~19
7. 冒泡排序最坏时间复杂度()
A.O(n)O(n)O(n) B.O(n2)O(n^2)O(n2) C.O(nlogn)O(n\log n)O(nlogn) D.O(logn)O(\log n)O(logn)
8. 下面哪个是栈(LIFO)()
A.排队买票 B.子弹弹匣 C.水管流水 D.队列
9. sort函数默认排序方式()
A.降序 B.升序 C.随机 D.不稳定
10. 01背包,物品每件()
A.只能选一次 B.无限选 C.最多k次 D.不能选
11. 字符串"cspj"长度是()
A.3 B.4 C.5 D.不确定
12. DFS用什么辅助存储()
A.队列 B.栈 C.优先队列 D.哈希表
13. BFS适合求什么(无权图)()
A.最长路 B.最短路 C.环 D.拓扑序
14. 下面可以存大数,防止溢出的类型()
A.int B.char C.long long D.bool
15. 二分查找数组要求()
A.有序 B.无序 C.必须int D.元素互不相同
二、阅读程序(看代码写输出,CSP-J必考)
阅读1
问输出:________
阅读2
问输出:________
三、完善程序(挖空,CSP-J题型)
题目:求1~n所有数的约数个数之和
①处:
A.j<n B.j<=i C.j<=n D.j>i
②处:
A.i%j0 B.j%i0 C.i+j0 D.i*j0
四、编程大题(2道,CSP-J难度,第一题简单模拟,第二题DP/搜索)
T1 数字统计(基础模拟,CSP-J第一题风格)
【题目描述】
给定n个整数,统计其中正数、负数、0分别有多少个。
【输入】
第一行一个整数n。
第二行n个int范围内整数。
【输出】
一行三个整数:正数数量,负数数量,0的数量。
样例输入:
6
2 -3 0 5 0 -1
样例输出:
2 2 2
T2 最大子段和(经典CSP-J高频DP)
【题目描述】
给定长度为n的整数序列,找出连续一段子数组,使子数组元素和最大,输出这个最大值。
可以选单独一个数。
【输入】
第一行n。
第二行n个整数。
【输出】最大子段和。
样例输入
5
-2 3 -1 2 -4
样例输出
4
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
答案
一、单选
1.C 2.A 3.D 4.B 5.B
6.C 7.B 8.B 9.B 10.A
11.B 12.B 13.B 14.C 15.A
二、阅读程序
阅读1:6
阅读2:5
三、完善程序
①B ②A
编程题参考代码
T1
T2
CSP-J考前小贴士
1. 开long long!求和、乘积很容易int爆掉。
2. 数组开大一点,不要刚好卡数据范围,防止越界。
3. 多组样例手动模拟,边界测试:全负数、n=1。
4. 遇到搜索题记得标记,防止重复走。
5. 看清楚输出格式:空格、换行,不要多打少打。
CSP-S 提高组考前押题卷
> 📌考前提醒:
>
> 1. 注意long long,大量求和、乘法、图论最短路、DP极易爆int;
> 2. STL、图论、DP、字符串、贪心是S组核心;
> 3. 手动跑小样例,特判边界(n=1、无方案、负权等);
> 4. 数组/vector注意大小,图记得初始化,避免重复边、越界。
一、单项选择题(15题)
1. 下面时间复杂度为 O(nlogn)O(n\log n)O(nlogn) 的是()
A.冒泡排序 B.插入排序 C.归并排序 D.枚举所有子集
2. 一棵有n个节点的二叉树,最少叶子节点数()
A.1 B.⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ C.n−1n-1n−1 D.logn\log nlogn
3. Floyd多源最短路算法时间复杂度()
A.O(n)O(n)O(n) B.O(n2)O(n^2)O(n2) C.O(n3)O(n^3)O(n3) D.O(mlogn)O(m\log n)O(mlogn)
4. 无负权边图求单源最短路,优先队列实现的算法是()
A.Floyd B.Dijkstra C.Kruskal D.BFS
5. 并查集不能直接完成的是()
A.查询两点连通性 B.合并集合 C.求两点最短路径 D.路径压缩
6. 拓扑排序适用的图是()
A.有向无环图DAG B.带负环图 C.无向图 D.完全图
7. 01背包状态定义dp[i][j]dp[i][j]dp[i][j]代表前i物品,容量j最大价值,空间优化后数组滚动方向()
A.j从小到大 B.j从大到小 C.随便顺序 D.只循环i
8. 字符串string s="CSP-S2026",s.size()返回类型是()
A.int B.size_t C.char D.long long
9. 优先队列priority_queue<int>默认是什么堆()
A.小根堆 B.大根堆 C.栈 D.队列
10. 平衡二叉搜索树的平均查找复杂度()
A.O(1)O(1)O(1) B.O(logn)O(\log n)O(logn) C.O(n)O(n)O(n) D.O(n2)O(n^2)O(n2)
11. 以下哪个属于稳定排序()
A.快速排序 B.堆排序 C.归并排序 D.选择排序
12. 最小生成树Kruskal核心依靠()
A.栈 B.队列 C.并查集 D.哈希
13. 强连通分量算法常用于()
A.DAG缩点 B.求最短路 C.背包DP D.二分图匹配
14. 二分图最大匹配常用算法()
A.Dijkstra B.Hungary匈牙利 C.Floyd D.BFS无权最短路
15. 一个集合有n个元素,子集总数()
A.n!n!n! B.2n2^n2n C.n2n^2n2 D.nnn
二、阅读程序写结果
阅读1
输出:________
阅读2(递归,记忆化风格)
输出:________
三、完善程序(填空)
题目:求最长公共子序列LCS(经典DP)
①:
A. dp[i-1][j-1]+1 B. dp[i-1][j]+1 C. dp[i][j-1] D. dp[i-1][j-1]
②:
A.dp[i-1][j], dp[i][j-1] B.dp[i-1][j-1],dp[i-1][j] C.dp[i-1][j-1],dp[i][j-1] D.dp[i][j-1],dp[i][j]
四、编程大题(CSP-S难度,T1中等模拟/贪心;T2图论/DP)
T1 区间选点(经典贪心,CSP-S第一题高频)
【题目描述】
给定n个闭区间[li,ri][l_i,r_i][li ,ri ],请选出尽量少的点,使得每个区间内至少包含一个选出的点。输出最少点数。
【输入】
第一行整数n。
接下来n行,每行两个整数 l, r。
【输出】最少点数量。
样例输入
3
1 3
2 5
4 6
样例输出
2
T2 树上DP(子树最大独立集,S组树DP经典)
【题目描述】
给定一棵无根树,每个节点有权值。选若干节点,不能同时选相邻节点,求选出节点权值总和最大值。
【输入】
第一行n。第二行n个整数代表每个点权值。
接下来n-1行,每行u v,表示u、v相连。
【输出】最大权值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
8
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考答案
一、单选
1.C 2.A 3.C 4.B 5.C
6.A 7.B 8.B 9.B 10.B
11.C 12.C 13.A 14.B 15.B
二、阅读程序
阅读1:9
阅读2:11
三、完善程序
①A ②A
参考代码
T1 区间选点
T2 树上最大独立集
CSP-S考场重点提醒
1. 图论:多测清空数组、邻接表初始化,Dijkstra要用堆优化,long long存距离;
2. DP:状态定义先写纸上,仔细看转移,滚动数组注意循环顺序;
3. 树题:dfs别忘记父节点,防止往回走死循环;
4. 数据范围!1e5级别不能写O(n²)暴力,会TLE;
5. 输出答案前,特判无解情况,看题目要求输出-1或者0。
有帮助,赞一个