CSP-J初赛必考的硬核知识点，这次一次吃透

为什么计算机用0和1？负数怎么运算？数据在内存里怎么排队？
本文用一篇长文，讲透进制转换、计算机组成、补码原理和四种基础数据结构，二叉树，组合数学。

适合CSP-J/S初赛备考

第一章 进制转换：计算机的“母语”是怎么来的？

为什么是二进制？

我们人类习惯十进制，是因为有十根手指。但计算机内部是由无数个“开关”组成的，每个开关只有“开（通电）”和“关（断电）”两种状态。用这两种状态来表示数字，二进制（逢二进一） 就诞生了，它是最稳定、最抗干扰的方式。

至于八进制和十六进制，纯粹是为了方便程序员阅读。因为一长串的0和1太容易看花眼，用十六进制可以每4位二进制缩写成1位，比如 0b110101 写成 0x35，清爽多了。

CSP核心考点与避坑指南

1. 通用转换大法

转换类型	方法名称	操作要点
其他进制 → 十进制	按权展开相加	每位数字乘以该位的权值（基数的位数次方），再求和
十进制 → 其他进制（整数）	除基取余，倒序排列	不断除以目标基数，记录余数，最后倒序读取
十进制 → 其他进制（小数）	乘基取整，顺序排列	不断乘以目标基数，记录整数部分，顺序读取
二、八、十六进制互转	8421码分组法	1位八进制=3位二进制，1位十六进制=4位二进制

举例：二进制 110.1 转十进制：1×2² + 1×2¹ + 0×2⁰ + 1×2⁻¹ = 4 + 2 + 0 + 0.5 = 6.5。

2. 易错点警示

⚠️ 坑点1：小数转换

初赛常考 0.625 转二进制，很多人只练整数，遇到小数就慌。

正确做法：乘2取整。

• 0.625 × 2 = 1.25 → 取 1，剩 0.25
• 0.25 × 2 = 0.5 → 取 0，剩 0.5
• 0.5 × 2 = 1.0 → 取 1，剩 0

结果是 0.101。

⚠️ 坑点2：前缀陷阱

在C++代码中：

• 0x 开头 → 十六进制（如 0x10 等于十进制的16）
• 直接用数字 0 开头 → 八进制（如 010 在C++老标准中等同于十进制的 8，而不是10！）

📌 本章小结：二进制是计算机的底层语言，进制转换的本质是“按权展开”和“短除法/乘基取整”。记住这两个方法，就能应对CSP初赛中90%的进制题目。

第二章 计算机组成：冯·诺依曼的“身体构造”

有了语言，计算机还需要一个“身体”来执行运算。现代计算机的鼻祖——冯·诺依曼结构，我们可以继续用厨房来理解它。

计算机部件	说明
运算器	负责算术运算和逻辑运算
控制器	负责解读指令并指挥各部件工作
内存	断电后数据丢失（临时存储）
外存	断电后数据保留（永久存储）
输入设备	键盘、鼠标等
输出设备	显示器、打印机等

CSP核心考点与避坑指南

1. 存储单位换算

这是选填题的常客。牢记递进关系：

Bit（位） → Byte（字节） → KB → MB → GB → TB

📌 核心等式：1 Byte = 8 bit

⚠️ 注意：在CSP考试中，除非特别说明，全部遵循1024进制！即 1KB = 1024 Byte，1MB = 1024 KB。

🌐 网络陷阱：你家宽带是 100 Mbps，这里的 b 是小写，代表 bit；下载软件显示 10 MB/s，这里的 B 是大写，代表 Byte。所以理论最高下载速度是 100 / 8 = 12.5 MB/s，别闹出“宽带缩水”的笑话。

2. 内存与外存本质区别

📌 核心结论：程序必须调入内存才能被CPU执行。

硬盘上的程序只是一个文件，双击运行时，操作系统会把它加载到内存中，CPU再从内存读取指令执行。这是判断概念题的高频考点。

📌 本章小结：冯·诺依曼结构的核心是“存储程序”思想——程序和数据都存放在内存中，CPU按顺序取指令执行。记住“内存是操作台，外存是冰箱”这个比喻，硬件组成题就难不倒你。

第三章 原码、反码、补码：计算机的“负数记账法”

这是初学者最头疼的部分。我们一步步拆解它为什么存在。

核心矛盾：计算机没有减法器

计算机的CPU内部只有一个加法器。那 1 - 1 怎么算？只能算 1 + (-1)。

如果直接用原码（最高位是符号位，0正1负）来表示负数：

• 1 的原码：00000001
• -1 的原码：10000001
• 两者相加得：10000010，也就是十进制的 -2，这显然是错的！

解决方案：补码的“模运算”思想

为了解决这个难题，工程师们发明了补码。补码的核心思想是 “模运算”，就像时钟一样：

在12小时制的时钟上，从3点倒拨2小时，和正拨10小时效果一样（3 - 2 = 3 + 10 (mod 12)）。

在8位二进制中，模是 2^8 = 256，所以 -1 可以用 -1 + 256 = 255（二进制 11111111）来表示，这就是 -1 的补码。

三种码的关系与计算规则（以8位为例）

类型	正数（如 +1）	负数（如 -1）
原码	00000001	10000001（符号位为1，其余位不变）
反码	00000001（同原码）	11111110（符号位不变，其余位取反）
补码		11111111（反码 + 1）

运算举例：计算 1 - 1，即 1 + (-1)。

• 1的补码：00000001
• -1的补码：11111111
• 相加得：1 00000000（最高位溢出，舍弃）
• 结果是 00000000，正好是十进制的 0！

CSP核心考点与避坑指南

📌 核心口诀：补码再求补（符号位不变，取反加一）等于原码。

牢记这个口诀，可以快速解决95%的补码转原码选择题。

⚠️ 坑点1：补码转原码

例如补码 11111100：

1. 取反（符号位不变）：10000011
2. 加1：10000100
3. 这就是原码，值为 -4。

⚠️ 坑点2：补码表示范围

8位有符号补码范围是 -128 ~ +127。

其中 -128 的补码是 10000000，它没有对应的原码和反码！

这是选择题常挖的坑，看到“-128有原码”的说法，直接判定为错。

📌 本章小结：补码的本质是用“模运算”将减法转化为加法，让CPU只需要设计加法器。记住“正数三码合一，负数反码加1”，以及“-128是个特例”，补码题目就能轻松拿分。

第四章 数组、链表、栈与队列：数据的“摆放与存取学”

计算机处理大量数据时，如何组织它们就成了核心问题。这四种基础数据结构，就是解决“怎么放”和“怎么取”的四种经典方案。

一张表看懂四种结构

数据结构	内存布局	核心特性	访问速度	插入/删除速度	CSP最爱考点
数组	连续的内存空间	通过下标随机存取	O(1) 极快	O(n) 较慢（需移动元素）	二维数组行优先/列优先的地址计算
链表	离散的内存空间（节点+指针）	必须从头遍历顺序存取	O(n) 较慢	O(1)（仅改指针）极快	头插法/尾插法；判断链表是否有环（快慢指针）
栈	可用数组或链表实现	后进先出（LIFO）	O(1)（仅栈顶）		括号匹配、中缀表达式转后缀、函数递归调用原理
队列	可用数组（循环队列）或链表实现	先进先出（FIFO）	O(1)（仅队头/队尾）		广度优先搜索（BFS） 的底层结构；循环队列的判空/判满条件

三个最重要的避坑指南

1. 数组寻址公式（必考！）

假设二维数组 a[i][j]，基址为 base，每个元素占 size 字节：

存储方式	地址计算公式	说明
行优先（C/C++默认）	base + (i × 列数 + j) × size	先存满一行，再存下一行
列优先（如Fortran）	base + (j × 行数 + i) × size	先存满一列，再存下一列

💻 实战演练（CSP风格）：

定义一个二维数组 int a[10][10]，在内存中按行优先存储，数组首地址为 1000，每个 int 占4字节。请问 a[3][5] 的地址是多少？

解：a[10][10] 有10行10列，行号列号均从0开始。a[3][5] 前面有 完整3行（第0、1、2行）和当前行的 5个元素（第0-4列）。

地址 = 1000 + (3 × 10 + 5) × 4 = 1000 + 35 × 4 = 1140。

关键点：如果题目改为 a[1..10][1..10]（从1开始编号），则公式应调整为 base + ((i-1) × 列数 + (j-1)) × size。

2. 栈与递归

函数不断调用自身，会导致栈空间被耗尽，从而报错 “Stack Overflow”。这不是算法逻辑错误，而是内存空间不足。写递归函数时，一定要确保有明确的终止条件。

3. 循环队列的判空判满

为了区分“队空”和“队满”，通常刻意浪费一个存储单元：

状态	判断条件	说明
队空	front == rear	队头指针和队尾指针重合
队满	(rear + 1) % maxSize == front	队尾指针的下一个位置是队头

%（取模运算）是实现循环的关键，务必理解它的含义。

📌 本章小结：数组适合随机访问，链表适合频繁插入删除；栈是“后进先出”，队列是“先进先出”。记住它们的核心特性和适用场景，数据结构选择题就不会丢分。

第五章 二叉树：分层组织的数据结构

二叉树是CSP初赛数据结构的重点内容，需要掌握基本概念、遍历方式和重要性质。

二叉树的核心概念

术语	含义
根节点	树的顶层节点，没有父节点
叶子节点	没有子节点的节点（度为0）
深度	从根节点到该节点的边数（根深度为0）
层数	从1开始编号，根在第1层
完全二叉树	除最后一层外都填满，且最后一层节点从左到右连续
满二叉树	每个节点要么是叶子，要么有2个孩子

三种遍历方式（必考！）

遍历方式	访问顺序	记忆口诀	第一个访问的节点
前序遍历	根 → 左 → 右	“根左右”	根节点
中序遍历	左 → 根 → 右	“左根右”	左子树最左下节点
后序遍历	左 → 右 → 根	“左右根”

关键考点：已知“前序+中序”或“后序+中序”，可以唯一确定一棵二叉树。

规律：前序第一个是根，后序最后一个是根，中序根左边是左子树、右边是右子树。

二叉树的性质（选择题常考）

性质	公式
叶子节点数 = 度为2的节点数 + 1	n₀ = n₂ + 1
第i层最多节点数	2^(i-1)
高度为h的二叉树最多节点数	2^h - 1（根深度为0）
完全二叉树节点i的左孩子	2i（编号从1开始）
完全二叉树节点i的右孩子	2i + 1
完全二叉树节点i的父节点	⌊i/2⌋

📌 本章小结：二叉树的遍历是CSP初赛必考内容，记住“前序找根、中序分左右、后序最后是根”的口诀，遍历题目就能轻松应对。

第六章 排列组合与数学基础（初赛必考）

CSP-J初赛每年都会考察排列组合与数论基础，它们不依赖于特定编程知识。

1. 排列与组合

概念	公式	含义	关键词
排列（A）	A(n,m) = n!/(n-m)!	从n个中取m个排成一列，顺序有关	排队、站位、安排顺序
组合（C）	C(n,m) = n!/(m!(n-m)!)	从n个中取m个组成一组，顺序无关	选人、选物、抽签

快速区分：排列 = 组合 × m!，即 A(n,m) = C(n,m) × m!。

常见解题模型：

• 捆绑法：解决“相邻”问题，把相邻元素捆成一个整体
• 插空法：解决“不相邻”问题，先排其他元素再插入空隙
• 隔板法：解决“相同元素分组”问题，在空隙中插入隔板
• 错位排列：n个元素全不在原位的排列数，记作Dₙ

错位排列递推公式：D(n) = (n-1) × (D(n-1) + D(n-2))

• D₁=0，D₂=1，D₃=2，D₄=9，D₅=44

2. 初等数论基础

知识点	要点	初赛常见考察方式
质数/合数	质数只有1和本身两个因数	判断质数、分解质因数
最大公约数（GCD）	辗转相除法	求两个数的最大公约数
最小公倍数（LCM）	LCM(a,b) = a×b / GCD(a,b)	与GCD结合出题
同余/模运算	(a+b) mod m 的分配律	大数取模运算

📌 本章小结：排列组合的核心是区分“顺序是否有关”，数论的核心是“辗转相除法”和“质数判定”。掌握这些模型，数学类选择题就能稳定拿分。

结语：把书读薄，把分拿到

至此，我们学习了进制、计算机组成，补码，反码，数据结构，这一切构成了计算机运行的基础。

CSP并不可怕，它考察的就是这些基础概念的深度理解和灵活运用。

与其死记硬背，不如顺着我们今天这条 “语言→身体→算术→整理” 的逻辑线，理解计算机设计的初衷。当你明白了“为什么”，那些“是什么”的考点自然就记住了。

附录：CSP初赛核心速查表

进制转换速查

转换	方法	口诀
二→十	按权展开相加	“每一位乘上它的权”
十→二（整数）	除2取余，倒序排列	“除到0，余数倒着读”
十→二（小数）	乘2取整，顺序排列	“乘到1，整数顺着读”
二↔十六	4位一组，8421码	“4位变1位，1位变4位”

补码速查

类型	原码	反码	补码
正数（如+5）	00000101
负数（如-5）	10000101	11111010	11111011

关键值：-128 的补码是 10000000，无原码/反码。

数据结构速查

数据结构	一句话记忆
数组	连续内存，随机访问，增删慢
链表	离散内存，顺序访问，增删快
栈	后进先出（LIFO）——像一叠盘子
队列	先进先出（FIFO）——像排队打饭

数组寻址公式速查

存储方式	公式（从0开始）
行优先	base + (i × 列数 + j) × size
列优先	base + (j × 行数 + i) × size

排列组合公式速查

名称	公式	记忆要点
排列数	A(n,m) = n!/(n-m)!	顺序有关
组合数	C(n,m) = n!/(m!(n-m)!)	顺序无关
错位排列	D₁=0, D₂=1, D₃=2, D₄=9, D₅=44	递推：D(n)=(n-1)(D(n-1)+D(n-2))

二叉树性质速查

性质	公式
叶子节点数	n₀ = n₂ + 1
第i层最多节点数	2^(i-1)
高度h的二叉树最多节点数	2^h - 1
节点i的左孩子（完全二叉树）	2i
节点i的右孩子（完全二叉树）	2i + 1
节点i的父节点（完全二叉树）	⌊i/2⌋