CSP-J 初赛核心知识点复习清单
一、计算机基础常识
1. 计算机发展史与人物
* 第一台电子计算机：ENIAC (1946年)，使用电子管。
* 冯·诺依曼 (Von Neumann)：提出“存储程序”思想，确立计算机五大部件（运算器、控制器、存储器、输入设备、输出设备）。
* 艾伦·图灵 (Alan Turing)：计算机科学之父，提出图灵机模型，图灵奖是计算机界最高荣誉。
* 摩尔定律：集成电路上可容纳的晶体管数目，约每隔 18-24 个月便会增加一倍。
2. 数据存储单位换算 (必背)
* 基本关系：
* 1 Byte (B)=8 bits (b)1 \text{ Byte (B)} = 8 \text{ bits (b)}1 Byte (B)=8 bits (b)
* 1 KB=1024 B1 \text{ KB} = 1024 \text{ B}1 KB=1024 B
* 1 MB=1024 KB1 \text{ MB} = 1024 \text{ KB}1 MB=1024 KB
* 1 GB=1024 MB1 \text{ GB} = 1024 \text{ MB}1 GB=1024 MB
* 1 TB=1024 GB1 \text{ TB} = 1024 \text{ GB}1 TB=1024 GB
* 注意：考试中统一按 1024 进制计算。
3. 进制转换与编码
* 常见进制：
* 二进制 (Binary)：0, 1
* 八进制 (Octal)：0-7
* 十进制 (Decimal)：0-9
* 十六进制 (Hex)：0-9, A(10)-F(15)
* 转换技巧：
* 二 ↔\leftrightarrow↔ 八：每 3 位二进制对应 1 位八进制。
* 二 ↔\leftrightarrow↔ 十六：每 4 位二进制对应 1 位十六进制。
* 十 →\rightarrow→ 其他：除基取余，逆序排列。
* 其他 →\rightarrow→ 十：按权展开求和。
* ASCII 码 (必记数值)：
* '0' = 48
* 'A' = 65
* 'a' = 97
* 空格 = 32
* 规律：小写字母 ASCII 值 - 大写字母 ASCII 值 = 32
4. 计算机网络
* IP 地址：
* IPv4：32位，点分十进制。
* IPv6：128位，冒号十六进制。
* TCP/IP 协议族：
* 应用层：HTTP (80), HTTPS (443), FTP (21), DNS (53)。
* 传输层：TCP (可靠连接), UDP (不可靠/快速)。
* 网络层：IP 协议。
* 域名系统 (DNS)：将域名解析为 IP 地址。
* .cn (中国), (.com商业), .edu (教育), .gov (政府)。
5. 软件系统
* 系统软件：操作系统 (Windows, Linux, macOS, Android, iOS)、数据库管理系统、编译程序。
* 应用软件：Office, 浏览器, 游戏等面向具体任务的软件。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、数学与逻辑基础
1. 排列组合
* 加法原理：“分类”计数，完成一件事有 nnn 类办法，总方法数相加。
* 乘法原理：“分步”计数，完成一件事需 nnn 个步骤，总方法数相乘。
* 排列公式：Anm=n!(n−m)!A_n^m = \frac{n!}{(n-m)!}Anm =(n−m)!n!
* 组合公式：***=n!m!(n−m)!C_n^m = \frac{n!}{m!(n-m)!}*** =m!(n−m)!n!
* 常用技巧：捆绑法（相邻问题）、插空法（不相邻问题）。
2. 数论基础
* 质数 (素数)：大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除。最小质数是 2。
* 最大公约数 (GCD)：常用辗转相除法。
* 最小公倍数 (LCM)：lcm(a,b)=a×bgcd(a,b)\text{lcm}(a,b) = \frac{a \times b}{\text{gcd}(a,b)}lcm(a,b)=gcd(a,b)a×b
* 模运算：amod ba \mod bamodb 表示 aaa 除以 bbb 的余数，结果范围 0≤r<b0 \le r < b0≤r<b。
3. 逻辑运算
* 与 (AND / &&)：全真才真。
* 或 (OR / ||)：全假才假。
* 非 (NOT / !)：取反。
* 异或 (XOR / ^)：相同为 0 (假)，不同为 1 (真)。
* 优先级：! > && > ||。注意短路运算特性。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、数据结构基础
1. 线性结构
* 数组：连续存储，随机访问快，下标从 0 开始。访问复杂度 O(1)O(1)O(1)。
* 链表：离散存储，插入删除快，查找慢。查找复杂度 O(n)O(n)O(n)。
* 栈 (Stack)：
* 特点：后进先出 (LIFO)
* 操作：只能在栈顶进行插入 (Push) / 删除 (Pop)。
* 复杂度：O(1)O(1)O(1)
* 队列 (Queue)：
* 特点：先进先出 (FIFO)
* 操作：队尾入队 (Enqueue)，队头出队 (Dequeue)。
* 复杂度：O(1)O(1)O(1)
> 重点考题：给定入栈序列，判断合法的出栈序列（通过模拟入栈出栈过程验证）。
2. 树 (二叉树为重点)
* 基本性质：
* nnn 个节点的二叉树有 n−1n-1n−1 条边。
* 第 kkk 层最多有 2k−12^{k-1}2k−1 个节点。
* 深度为 hhh 的二叉树最多有 2h−12^h - 12h−1 个节点。
* 重要公式：叶子节点数 n0n_0n0 与度为 2 的节点数 n2n_2n2 关系：n0=n2+1n_0 = n_2 + 1n0 =n2 +1。
* 遍历方式：
* 前序：根 →\rightarrow→ 左 →\rightarrow→ 右
* 中序：左 →\rightarrow→ 根 →\rightarrow→ 右
* 后序：左 →\rightarrow→ 右 →\rightarrow→ 根
* 层序：从上到下，从左到右
* 哈夫曼树 (Huffman Tree)：带权路径长度 (WPL) 最小的二叉树，用于数据压缩。
3. 图论基础
* 基本概念：顶点、边、度 (入度/出度)。
* 性质：所有顶点的度数之和 = 2×2 \times2× 边数。
* 存储结构：邻接矩阵、邻接表。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、算法基础与 C++ 语法
1. 排序算法对比
算法 均时平间复杂度 稳定性 备注 <>冒泡排序<> O(n)O(n)O(n) 稳定 简单，交换相邻元素 <>选择排序<> O(n)O(n)O(n) 不稳定 每次选最小/大值 <>插入排序<> O(n)O(n)O(n) 稳定 适合小规模或基本有序数据 <>快速排序<> O(nlogn)O(n \log n)O(nlogn) 不稳定 最坏 O(n)O(n)O(n)，实际最快 <>归并排序<> O(nlogn)O(n \log n)O(nlogn) 稳定 需要额外空间
2. 常见算法思想
* 枚举 (暴力)：遍历所有可能情况。
* 模拟：按照题目描述一步步执行。
* 递归：函数调用自身，必须有终止条件。
* 二分查找：在有序数组中查找，时间复杂度 O(logn)O(\log n)O(logn)。
* 贪心：每一步都做出当前看来最好的选择（局部最优），不一定得到全局最优。
* 动态规划 (DP)：将大问题分解为子问题，记录中间状态（如背包问题）。
* 搜索：DFS (深度优先，栈/递归实现), BFS (广度优先，队列实现)。
3. C++ 基础语法陷阱
* 整数除法：5 / 2 结果是 2 (整数截断)，5.0 / 2 结果是 2.5。
* 自增自减：i++ (先用后加) vs ++i (先加后用)。
* 逻辑短路：if (a != 0 && b/a > 1) 是安全的；若顺序颠倒可能除零错误。a
* 数组下标：C++ 数组下标从 0 开始，注意越界问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、备考建议与应试技巧
1. 时间分配建议 (120分钟)：
* 单项选择题 (15题, 30分)：建议 20-25 分钟。速战速决，遇到难题先标记。
* 阅读程序 (3大题, 40分)：建议 40-45 分钟。这是拉分关键，需静心模拟变量变化。
* 完善程序 (2大题, 30分)：建议 25-30 分钟。利用上下文逻辑推断填空。
* 检查：留 10-15 分钟 涂卡及复查。
2. 核心能力培养：
* 静态调试能力：在不运行代码的情况下，在草稿纸上跟踪变量值的变化。
* 排除法：选择题中，通过代入特殊值 (如 n=1,n=2n=1, n=2n=1,n=2) 快速排除错误选项。
* 知识地图：将分散的知识点（如 ASCII、进制、存储单位）形成体系，避免碎片化记忆。
3. 避坑指南：
* 注意题目问的是“不正确的是”还是“正确的是”。
* 注意数据范围，警惕整数溢出 (int vs long long)。
* 注意运算符优先级，特别是逻辑运算符与算术运算符混合时。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
