集训笔记

2026-08-11 22:47:10

发布于：浙江

2阅读

0回复

0点赞

📚 CSP-J 初赛核心知识点复习清单

‌常见进制‌：
- 二进制 (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

‌IP 地址‌：
- IPv4：32位，点分十进制。
- IPv6：128位，冒号十六进制。
‌TCP/IP 协议族‌：
- 应用层：HTTP (80), HTTPS (443), FTP (21), DNS (53)。
- 传输层：TCP (可靠连接), UDP (不可靠/快速)。
- 网络层：IP 协议。
‌域名系统 (DNS)‌：将域名解析为 IP 地址。
- .cn (中国), .com (商业), .edu (教育), .gov (政府)。

‌数组‌：连续存储，随机访问快，下标从 0 开始。访问复杂度 $O(1)$ 。
‌链表‌：离散存储，插入删除快，查找慢。查找复杂度 $O(n)$ 。
‌栈 (Stack)‌：
- 特点：‌后进先出 (LIFO)‌
- 操作：只能在栈顶进行插入 (Push) / 删除 (Pop)。
- 复杂度： $O(1)$
‌队列 (Queue)‌：
- 特点：‌先进先出 (FIFO)‌
- 操作：队尾入队 (Enqueue)，队头出队 (Dequeue)。
- 复杂度： $O(1)$

‌重点考题‌：给定入栈序列，判断合法的出栈序列（通过模拟入栈出栈过程验证）。

‌基本性质‌：
- $n$ 个节点的二叉树有 $n-1$ 条边。
- 第 $k$ 层最多有 $2^{k-1}$ 个节点。
- 深度为 $h$ 的二叉树最多有 $2^h - 1$ 个节点。
- ‌重要公式‌：叶子节点数 $n_0$ 与度为 2 的节点数 $n_2$ 关系： $n_0 = n_2 + 1$ 。
‌遍历方式‌：
- ‌前序‌：根 $\rightarrow$ 左 $\rightarrow$ 右
- ‌中序‌：左 $\rightarrow$ 根 $\rightarrow$ 右
- ‌后序‌：左 $\rightarrow$ 右 $\rightarrow$ 根
- ‌层序‌：从上到下，从左到右
‌哈夫曼树 (Huffman Tree)‌：带权路径长度 (WPL) 最小的二叉树，用于数据压缩。

算法	平均时间复杂度	稳定性	备注
<>冒泡排序<>	$O(n)$	稳定	简单，交换相邻元素
<>选择排序<>	$O(n)$	不稳定	每次选最小/大值
<>插入排序<>	$O(n)$	稳定	适合小规模或基本有序数据
<>快速排序<>	$O(n \log n)$	不稳定	最坏 $O(n)$ ，实际最快
<>归并排序<>	$O(n \log n)$	稳定	需要额外空间

‌时间分配建议 (120分钟)‌：
- ‌单项选择题‌ (15题, 30分)：建议 ‌20-25 分钟‌。速战速决，遇到难题先标记。
- ‌阅读程序‌ (3大题, 40分)：建议 ‌40-45 分钟‌。这是拉分关键，需静心模拟变量变化。
- ‌完善程序‌ (2大题, 30分)：建议 ‌25-30 分钟‌。利用上下文逻辑推断填空。
- ‌检查‌：留 ‌10-15 分钟‌ 涂卡及复查。
‌核心能力培养‌：
- ‌静态调试能力‌：在不运行代码的情况下，在草稿纸上跟踪变量值的变化。
- ‌排除法‌：选择题中，通过代入特殊值 (如 $n=1, n=2$ ) 快速排除错误选项。
- ‌知识地图‌：将分散的知识点（如 ASCII、进制、存储单位）形成体系，避免碎片化记忆。
‌避坑指南‌：
- 注意题目问的是“‌不‌正确的是”还是“‌正确‌的是”。
- 注意数据范围，警惕整数溢出 (int vs long long)。
- 注意运算符优先级，特别是逻辑运算符与算术运算符混合时。