公告
CSP-J 第一轮笔试·知识总结
📘 CSP-J 第一轮笔试 超详细知识点总结
覆盖 NOI 2025 大纲 · 全考点详解 · 含真题高频点
💡 CSP-J（入门级）第一轮 为 笔试，满分 100 分，时长 2 小时。
题型包括 单项选择题（15 题，30 分）、阅读程序题（约 40 分） 和 完善程序题（约 30 分）。
本总结基于 NOI 2025 修订版大纲，覆盖所有考纲知识点，适合系统复习和考前冲刺。
题型包括 单项选择题（15 题，30 分）、阅读程序题（约 40 分） 和 完善程序题（约 30 分）。
本总结基于 NOI 2025 修订版大纲，覆盖所有考纲知识点，适合系统复习和考前冲刺。
一 考试概况
1.1 考试形式
| 项目 | 说明 |
|---|---|
| 形式 | 笔试，全部为客观题 |
| 时长 | 2 小时 |
| 满分 | 100 分 |
| 语言 | 仅 C++（NOI 系列赛事从 2022 年起只支持 C++） |
| 通过率 | 约 20%~30%（各省不同） |
1.2 题型与分值
| 题型 | 题量 | 分值 | 考查内容 |
|---|---|---|---|
| 单项选择题 | 15 题 | 30 分（每题 2 分） | 计算机基础、C++ 语法、数据结构、算法复杂度、数学基础等 |
| 阅读程序题 | 3 大题 | 约 40 分 | 读懂程序逻辑，判断输出或结果 |
| 完善程序题 | 2 大题 | 约 30 分 | 填空完成算法（排序、二分、递推、贪心、DFS/BFS 等） |
晋级规则： 第一轮成绩优异者可晋级第二轮（上机考试）。
笔试通过是参加复赛的唯一门槛，务必认真对待！
笔试通过是参加复赛的唯一门槛，务必认真对待！
二 计算机基础知识
本模块在单项选择题中占比约 15%~20%，是必拿分部分。
2.1 计算机的发展历史
- 第一台通用电子计算机： ENIAC，1946 年诞生于美国。
- 计算机之父、体系结构奠基人： 冯·诺依曼（Von Neumann），提出了 存储程序原理 和 二进制 思想。
- 著名计算机科学家： 图灵（Alan Turing）——提出图灵机模型、图灵测试；克劳德·香农——信息论奠基人。
- 计算机发展的四个阶段：
- 第一代（1940s-1950s）：电子管——体积巨大、耗电多
- 第二代（1950s-1960s）：晶体管——体积减小、更可靠
- 第三代（1960s-1970s）：集成电路——更小、更快
- 第四代（1970s 至今）：大规模/超大规模集成电路——微处理器诞生，PC 出现
- 图灵奖： 计算机领域的最高奖项，相当于“计算机界的诺贝尔奖”。
2.2 计算机的五大组成部分（冯·诺依曼体系）
| 部件 | 英文 | 功能 | 生活类比 |
|---|---|---|---|
| 运算器 | ALU | 执行算术运算和逻辑运算 | 大脑的计算中枢 |
| 控制器 | CU | 从内存取指令、分析指令、控制执行 | 大脑的指挥中心 |
| 存储器 | Memory | 存储数据和程序（内存 + 外存） | 笔记本 / 记忆 |
| 输入设备 | Input | 将外部信息送入计算机 | 眼睛、耳朵 |
| 输出设备 | Output | 将计算机结果输出给用户 | 嘴巴、手 |
核心考点： CPU = 运算器 + 控制器 + 寄存器。寄存器是 CPU 内部速度最快的临时存储单元。
2.3 存储体系（内存 vs 外存）
| 存储类型 | 速度 | 容量 | 断电后 | 典型设备 |
|---|---|---|---|---|
| 寄存器 | 极快 | 极小 | 丢失 | CPU 内部 |
| 高速缓存（Cache） | 很快 | 小 | 丢失 | CPU 附近 |
| 内存（RAM） | 快 | 中等 | 丢失 | DDR 内存条 |
| 外存 | 慢 | 大 | 保留 | 硬盘、SSD、U 盘 |
必背结论： 内存是“工作台”，外存是“仓库”。程序运行时，必须将数据从外存调入内存 才能被 CPU 处理。
2.4 常见 I/O 设备
- 输入设备： 键盘、鼠标、扫描仪、麦克风、摄像头。
- 输出设备： 显示器、打印机、音箱、投影仪。
- 兼输入输出： 触摸屏、网卡。
2.5 数据单位与进制
- 位（bit）： 0 或 1，最小存储单位。
- 字节（Byte）： 1 Byte = 8 bit，基本存储单位。
- 字（Word）： CPU 一次处理的数据大小，取决于 CPU 字长（16/32/64 位）。
换算关系（必背！）：
1 KB = 1024 Byte | 1 MB = 1024 KB | 1 GB = 1024 MB | 1 TB = 1024 GB
- 一个英文字母（'A'）→ 1 Byte
- 一个汉字（GBK 编码）→ 2 Byte
- 一个汉字（UTF-8 编码）→ 3 Byte（大部分常用汉字）
2.6 进制转换（每年必考！）
- 二进制 → 十进制： 按权展开。如
1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 11₁₀。 - 十进制 → 二进制： “除 2 取余，倒序排列”。
- 八进制/十六进制： 三位二进制 = 一位八进制；四位二进制 = 一位十六进制。
- 原码、反码与补码： 计算机中整数的三种表示方式。正数的原码 = 反码 = 补码；负数的补码 = 反码 + 1。
2.7 信息编码
- ASCII 码： 7 位编码（实际存储占 1 字节），共 128 个字符。常用：'0'=48，'A'=65，'a'=97。
- Unicode： 统一字符编码，包含全球所有字符。
三 操作系统与 Linux 命令
3.1 操作系统基础
- Windows： 个人电脑最流行，图形界面。
- Linux： 开源、稳定，多用于服务器和竞赛环境（如 NOI Linux）。
- macOS： Apple 系统，基于 Unix。
- Android / iOS： 移动端操作系统。
- 并发与并行： 并发是“同时处理多个任务”（宏观），并行是“同一时刻真正同时执行”（微观）。
3.2 Linux 高频命令（初赛必考！）
| 命令 | 含义 | 示例 |
|---|---|---|
ls | 列出当前目录内容 | ls -l 显示详细信息 |
cd | 切换目录 | cd /home |
pwd | 显示当前绝对路径 | pwd |
mkdir | 创建目录 | mkdir test |
rm | 删除文件或目录 | rm -r dir（递归删除） |
cp | 复制文件或目录 | cp a.txt b.txt |
mv | 移动或重命名 | mv old.txt new.txt |
cat | 查看文件内容 | cat file.txt |
grep | 搜索文本 | grep "hello" file.txt |
chmod | 修改文件权限 | chmod 755 script.sh |
sudo | 以管理员身份执行 | sudo apt install g++ |
touch | 创建空白文件 | touch file.txt |
记忆口诀：
ls 看文件，cd 进目录，pwd 我在哪，rm 要小心（删了就找不回来了）。
四 网络基础
4.1 网络分类
- LAN（局域网）： 一栋楼、一个校园。
- MAN（城域网）： 一座城市。
- WAN（广域网）： 国家、全球，即 互联网（Internet）。
4.2 IP 地址与域名
- IPv4： 32 位，写成 4 个十进制数（如
192.168.1.1），每段 0~255。 - IPv6： 128 位，解决 IPv4 地址枯竭问题。
- 域名： 人类可读的名称，如
www.baidu.com。 - DNS（域名系统）： 将域名解析为 IP 地址的“电话簿”。
特殊地址：
127.0.0.1 表示本机（localhost），用于自身测试。
4.3 常用网络协议
| 协议 | 全称 | 作用 |
|---|---|---|
| TCP | 传输控制协议 | 可靠传输，面向连接 |
| UDP | 用户数据报协议 | 不可靠但速度快（直播、视频通话） |
| IP | 网际协议 | 负责数据包路由寻址 |
| HTTP | 超文本传输协议 | 网页传输（明文） |
| HTTPS | 安全超文本传输协议 | 加密版 HTTP |
| FTP | 文件传输协议 | 上传/下载文件 |
- 路由器 vs 交换机： 路由器用于跨网段通信，交换机用于同一网段内通信。
五 C++ 程序设计语言
本模块在笔试中占比最高，2024 年超过 40%。
5.1 基本语法与数据类型
- 标识符： 字母、数字、下划线组成，不能以数字开头，不能是关键字。
- 常量与变量： 常量值不可变，变量值可变。
- 头文件与命名空间：
#include <bits/stdc++.h>包含所有常用头文件；using namespace std;使用标准命名空间。
5.2 基本数据类型
| 类型 | 关键字 | 大小（常见） | 取值范围 |
|---|---|---|---|
| 整数型 | int | 4 字节 | 约 -2.1×10⁹ ~ 2.1×10⁹ |
| 长整数型 | long long | 8 字节 | 约 -9×10¹⁸ ~ 9×10¹⁸ |
| 实数型 | float | 4 字节 | 约 6-7 位有效数字 |
| 双精度实数型 | double | 8 字节 | 约 15-16 位有效数字 |
| 字符型 | char | 1 字节 | -128 ~ 127 |
| 布尔型 | bool | 1 字节 | true / false |
高频陷阱：
例如
int 最大约 2.1×10⁹，超出范围要用 long long。例如
1LL << 60 必须加 LL 后缀，否则溢出。
5.3 基本运算
- 算术运算： 加
+、减-、乘*、除/、整除/（整数除法）、求余%。 - 关系运算：
>、>=、<、<=、==、!=。 - 逻辑运算：
&&（与）、||（或）、!（非）。 - 自增自减：
++、--（前置和后置的区别）。 - 三目运算：
条件 ? 表达式1 : 表达式2。 - 位运算：
&（按位与）、|（按位或）、~（按位非）、^（按位异或）、<<（左移）、>>（右移）。
⚠️ 位运算优先级陷阱： 位运算优先级 低于 算术运算。
例如
例如
1 + 2 << 1 的结果是 (1+2) << 1 = 6，而非 1 + (2<<1) = 5。
5.4 控制结构
- 顺序结构： 按代码顺序执行。
- 分支结构：
if、if-else、switch。 - 循环结构：
for、while、do-while。
do-while至少执行一次。 - 逻辑运算短路特性：
a && b中若a为假，则不执行b。
5.5 数学库常用函数（需包含 <cmath>）
- 绝对值：
abs() - 四舍五入：
round() - 下取整：
floor() - 上取整：
ceil() - 平方根：
sqrt() - 幂运算：
pow()
5.6 数组
- 一维数组：
int a[100];，下标从 0 开始。 - 二维数组：
int a[10][10];。 - 数组越界： 访问
a[100]当数组大小为 100 时是非法的（合法下标 0~99）。
5.7 字符串处理
- 字符数组：
char s[100];，以'\0'结尾。 - string 类：
string s;，常用函数：length()、size()、substr()、find()。
5.8 函数与递归
- 函数定义与调用：
返回值类型 函数名(参数列表) { 函数体 }。 - 形参与实参： 形参是定义时的参数，实参是调用时传入的值。
- 传值参数与传引用参数： 传值复制一份，传引用（
&）直接操作原变量。 - 变量作用域： 局部变量只在函数内有效，全局变量所有函数共享。
- 递归函数： 函数调用自身，必须有终止条件。
5.9 结构体
- 定义：
struct Student { string name; int age; }; - 访问成员： 用点号
.，如stu.name。
5.10 指针与引用
- 指针：
int *p = &a;，存储变量的地址。 - 字符指针：
char *s;，指向字符串。 - 指向结构体的指针： 用
->访问成员。 - 引用：
int &r = a;，变量的别名。
5.11 文件基本读写
- 文件重定向：
freopen("in.txt", "r", stdin);、freopen("out.txt", "w", stdout);。 - 文本文件操作：
ifstream、ofstream。
5.12 STL 常用容器与算法（近年高频）
| 容器/算法 | 特点 | 常考知识点 |
|---|---|---|
vector | 动态数组 | push_back() 后 size() 变化 |
stack | 后进先出（LIFO） | 出栈序列合法性 |
queue | 先进先出（FIFO） | BFS 必备 |
sort | 排序 | 完善程序题核心 |
min/max | 最值 | 常用函数模板 |
swap | 交换 | 常用函数模板 |
栈和队列的核心区别（必考！）：
栈是 后进先出（LIFO）——像叠盘子；队列是 先进先出（FIFO）——像排队打饭。
栈是 后进先出（LIFO）——像叠盘子；队列是 先进先出（FIFO）——像排队打饭。
六 数据结构
6.1 线性表
- 数组： 连续存储，随机访问 O(1)，插入/删除 O(n)。
- 链表： 链式存储，插入/删除 O(1)（给定位置），随机访问 O(n)。
6.2 栈与队列
- 栈（Stack）： LIFO，典型应用：函数调用、撤销操作、括号匹配。
- 队列（Queue）： FIFO，典型应用：BFS、打印机队列。
6.3 树
- 树的定义： 由 n 个节点组成的有限集合，有且仅有一个根节点。
- 二叉树： 每个节点最多两个子节点（左、右）。
- 完全二叉树： 除最后一层外都满，最后一层从左到右连续。可用数组存储（下标 1 为根，左孩子
2i，右孩子2i+1）。 - 满二叉树： 每一层节点数都达到最大值。
- 二叉搜索树（BST）： 左子树 < 根 < 右子树，中序遍历为升序。
- 哈夫曼树： 带权路径长度最小的二叉树，用于数据压缩。
- 树的遍历： 前序（根-左-右）、中序（左-根-右）、后序（左-右-根）。
6.4 图
- 图的定义： G = (V, E)，V 为顶点集合，E 为边集合。
- 有向图 vs 无向图： 边是否有方向。
- 邻接矩阵： O(N²) 空间，判断相邻 O(1)。
- 邻接表： O(N+M) 空间，遍历邻居快。
- 连通图： 任意两个顶点之间都有路径。
七 算法
7.1 算法复杂度（大 O 表示法）
| 复杂度 | 名称 | 10⁵ 规模估算 |
|---|---|---|
| O(1) | 常数级 | 极快 |
| O(log n) | 对数级 | 约 17 步 |
| O(n) | 线性级 | 10⁵ 步 |
| O(n log n) | 线性对数级 | 约 1.7×10⁶ 步（可接受） |
| O(n²) | 平方级 | 10¹⁰ 步（超时） |
结论： 数据规模 ≥ 10⁵ 时，O(n²) 算法几乎必然超时（TLE）。必须用 O(n log n) 或更优算法。
7.2 排序算法（必考）
| 算法 | 平均时间复杂度 | 稳定性 |
|---|---|---|
| 冒泡排序 | O(n²) | ✅ 稳定 |
| 选择排序 | O(n²) | ❌ 不稳定 |
| 插入排序 | O(n²) | ✅ 稳定 |
| 归并排序 | O(n log n) | ✅ 稳定 |
| 快速排序 | O(n log n) | ❌ 不稳定 |
| 堆排序 | O(n log n) | ❌ 不稳定 |
7.3 查找算法
- 顺序查找： O(n)，无序数组可用。
- 二分查找： O(log n)，要求数组 有序。
7.4 搜索算法
- DFS（深度优先搜索）： 用栈/递归，O(N+M)。
- BFS（广度优先搜索）： 用队列，O(N+M)，无权图 最短路径。
7.5 动态规划（DP）
- 基本思路： 状态、转移方程、边界条件。
- 一维 DP： 如斐波那契、爬楼梯。
- 背包 DP： 0/1 背包、完全背包。
- 区间 DP： 如石子合并。
八 数学与其他
8.1 数论基础
- 素数（质数）： 大于 1，只有 1 和自身两个约数。判断：试除到 √n。
- 最大公约数（GCD）： 欧几里得算法（辗转相除法）。
- 最小公倍数（LCM）：
a × b / GCD(a, b)。
8.2 排列组合
- 排列： A(n, m) = n! / (n−m)!（有序）。
- 组合： C(n, m) = n! / [m!(n−m)!]（无序）。
九 NOI 赛事规则
9.1 竞赛体系
层级： CSP-J/S 第一轮（笔试）→ CSP-J/S 第二轮（上机）→ NOIP → 省队选拔 → NOI → 国家队 → IOI
9.2 CSP-J/S
- CSP-J： 入门级（Junior），面向初中生及小学生。
- CSP-S： 提高级（Senior），面向高中生。
- 赛程： 第一轮（笔试，每年 9 月）→ 第二轮（上机，每年 10 月）。
- 语言： 仅 C++（NOI 系列从 2022 年起只支持 C++）。
9.3 NOIP
- 全称：全国青少年信息学奥林匹克联赛。
- 仅设 提高组（普及组由 CSP-J 替代）。
- 评奖：以省为单位划线，分一、二、三等奖。
9.4 NOI
- 全国青少年信息学奥林匹克竞赛（全国决赛）。
- 金牌前 50 名 入选国家集训队，获得 保送资格。
9.5 竞赛常用术语
| 术语 | 含义 |
|---|---|
| AC | Accepted（通过） |
| WA | Wrong Answer（答案错误） |
| TLE | Time Limit Exceeded（超时） |
| MLE | Memory Limit Exceeded（超内存） |
| RE | Runtime Error（运行时错误） |
| CE | Compilation Error（编译错误） |
| PE | Presentation Error（格式错误） |
📌 复习建议
- 单项选择题（30 分）： 重点复习计算机基础、进制转换、原码/反码/补码、存储单位、运算符优先级、数据结构概念、算法复杂度。
- 阅读程序题（约 40 分）： 多练手算模拟，熟悉循环嵌套、递归、字符串/数组操作。
- 完善程序题（约 30 分）： 掌握排序、二分、递推、贪心、DFS/BFS 的代码填空套路。
- 高频考点 TOP 10： 进制转换、原码/反码/补码、运算符优先级、循环执行次数、数组与下标、递归分析、时间复杂度、字符串处理、排序算法、数据结构性质。
- 最后冲刺： 做 3~5 套完整真题，限时 2 小时，适应笔试节奏。
🚀 笔试通过率约 20%~40%（各省不同），务必要认真对待。
初赛决定你能不能进复赛——多背一分，多进一分！
初赛决定你能不能进复赛——多背一分，多进一分！
贵公网安备 52011502010065 号