第一篇 计算机基础知识

一、计算机发展与核心人物

1. 第一台电子计算机
   1946 年，美国宾夕法尼亚大学，ENIAC。

2. 核心人物

   • 冯·诺依曼：计算机之父，提出存储程序思想、计算机五大硬件组成（运算器、控制器、存储器、输入设备、输出设备）。
   • 图灵：人工智能之父，提出图灵机模型、图灵测试。

3. 计算机发展五代
   电子管 → 晶体管 → 集成电路 → 大规模/超大规模集成电路 → 人工智能。

4. 核心奖项

   • 图灵奖：ACM 1966 年设立，计算机界诺贝尔奖，华人唯一获奖者：姚期智。
   • 摩尔定律：单块集成电路集成度约每 18 个月翻一番。

5. 计算机应用

   • 最早应用领域：数值计算。
   • 目前最广泛应用：数据/信息处理。
   • 常见缩写：CAD（计算机辅助设计）、CAM（计算机辅助制造）、CAI（计算机辅助教学）、CAT（计算机辅助测试）。

二、计算机系统结构

1. CPU 核心

   • 组成：运算器、控制器、寄存器。
   • 核心指标：主频（决定运算速度）、字长（决定计算精度与寻址空间）。

2. 存储器体系

   类型	核心特点	断电后数据	CPU 能否直接访问
   RAM（随机存储器）	运行内存，临时存储	丢失	能
   ROM（只读存储器）	固化程序，永久存储	不丢失
   Cache（高速缓存）	解决 CPU 与内存速度差	丢失
   外存（硬盘/U盘）	永久存储大容量数据	不丢失	不能

3. 存储单位换算

   • 1 Byte = 8 bit，bit 是最小存储单位，Byte 是基本存储单位。
   • 1 KB = 1024 B，1 MB = 1024 KB，1 GB = 1024 MB，1 TB = 1024 GB，1 PB = 1024 TB。

4. 总线分类

   • 地址总线 (AB)：单向，位数决定最大寻址空间，32 位地址总线最大寻址 4 GB（2³² B）。
   • 数据总线 (DB)：双向，传输数据。
   • 控制总线 (CB)：传输控制信号。

5. 设备分类

   • 输入设备：键盘、鼠标、扫描仪、麦克风、触摸屏。
   • 输出设备：显示器、打印机。

三、计算机软件系统

1. 软件分类
   系统软件 + 应用软件。

2. 操作系统 (OS)

   • 核心功能：处理机管理、存储管理、设备管理、信息管理。
   • 定位：硬件与软件/用户的接口，裸机上第一层软件。
   • 常见 OS：Windows、Linux、UNIX、Mac OS、Android；⚠️ WPS、Photoshop、Sybase 不是操作系统。

3. 高频考点

   • BIOS：基本输入输出系统，是固件，不属于操作系统。
   • 文件删除：放入回收站仅标记删除，清空回收站后仍可通过软件恢复。

四、计算机语言

1. 语言分类

   • 低级语言
     • 机器语言：二进制，CPU 直接执行，速度最快。
     • 汇编语言：助记符，与硬件强相关，底层开发仍在使用，未被淘汰。
   • 高级语言
     • 面向过程：C、Pascal、Fortran（首个高级语言）。
     • 面向对象：C++、Java、C#、Python；三大特性：封装、继承、多态；Smalltalk 是首个面向对象语言。

2. 翻译方式

   • 编译型：C/C++、Pascal，先编译为机器码再执行，效率高、跨平台性差。
   • 解释型：Python、PHP、JavaScript，逐行解释执行，效率低。

3. CSP-J 推荐环境
   Dev-C++、free pascal、Lazarus。

五、数制转换

1. 进制核心

   • 二进制：0-1，基数 2。
   • 八进制：0-7，基数 8。
   • 十六进制：0-9/A-F，基数 16。

2. 核心转换方法

   • R 进制 → 十进制：按权展开求和。
   • 十进制 → R 进制：整数除 R 倒取余，小数乘 R 顺取整。
   • 二进制 ↔ 八进制：3 位一组；二进制 ↔ 十六进制：4 位一组。

3. 核心运算
   二进制加减、异或运算（相同为 0，不同为 1）。

六、信息编码

1. ASCII 码

   • 7 位编码，存储占 1 字节，最高位为 0，范围 0-127。
   • 关键值：'0'=48，'A'=65，'a'=97，大小写字母 ASCII 值相差 32。

2. Unicode
   万国码，为全球字符设定唯一编码，UTF-8 是互联网最常用的实现方式。

3. 存储计算

   • 汉字点阵：32×32 点阵汉字，单字占用字节数 = 32×32÷8 = 128 B。
   • 位图图像：存储字节数 = 分辨率 × 色深 ÷ 8。

4. 编码位数
   n 种状态，至少需要 ⌈log₂n⌉ 位二进制编码。

七、原码、反码、补码

1. 核心规则

   • 正数：原码 = 反码 = 补码。
   • 负数：反码 = 原码符号位不变，其余位取反；补码 = 反码 + 1。

2. 关键特性

   • 计算机中数值以补码形式存储。
   • 0 的补码唯一，原码/反码有 +0 和 -0 两种表示。
   • 8 位有符号数：补码范围 -128~+127，原码/反码范围 -127~+127。

3. 浮点数
   由阶码（决定数值范围）和尾数（决定数值精度）组成。

八、计算机网络

1. 网络模型与核心协议

   TCP/IP 四层	对应 OSI 七层	核心协议	协议用途
   应用层	应用层/表示层/会话层	HTTP	网页访问
   		FTP	文件传输
   		SMTP	发送邮件
   		POP3/IMAP	接收邮件
   		DNS	域名解析
   传输层		TCP	可靠、面向连接
   		UDP	不可靠、无连接
   网络层		IP/ICMP/ARP	寻址、路由
   网络接口层	数据链路层/物理层	Ethernet	以太网

2. IP 地址

   • IPv4：32 位，分 4 段，每段十进制范围 0-255；超过 255 的为非法 IP。
   • 地址分类：A 类(0-127)、B 类(128-191)、C 类(192-223)。
   • IPv6：128 位，解决 IPv4 地址枯竭问题。

3. 高频考点

   • 中国国家顶级域名：.cn。
   • 网络分类：LAN（局域网）、WAN（广域网）、MAN（城域网）；蓝牙、WiFi 属于无线局域网，以太网是有线局域网。
   • HTML：超文本标记语言，超链接标签格式 <a href="地址">内容</a>；网页标准由 W3C 制定。
   • 搜索引擎：双引号代表精确搜索。
   • 计算机病毒：人为编写的可自我复制的程序，核心特征：传染性、繁殖性、破坏性、潜伏性、隐蔽性。

第二篇 程序设计与数据结构

一、算法基础

1. 算法五大特征
   有穷性、确切性、可行性、输入（0 个或多个）、输出（1 个或多个）。

2. 时间复杂度

   • 大 O 表示法：忽略常数和低次项，仅保留最高次项。
   • 常见复杂度排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
   • 高频递归式：
     • T(n) = T(n-1) + n → O(n²)
     • T(n) = 2T(n/2) + n → O(n log n)
     • 斐波那契递归 → O(2ⁿ)

3. 空间复杂度
   算法执行所需占用的内存空间。

二、C++ 语言基础

1. 程序核心
   main 函数是程序唯一入口；注释不影响程序运行速度；分号是语句结束符。

2. 高频考点

   • 运算符优先级：算术 > 关系 > 逻辑；逻辑非 (not) > 与 (and) > 或 (or)。
   • 经典技巧：x &= x-1 可统计 x 二进制中 1 的个数。
   • 递归：必须有递归出口，子问题与原问题同构；函数/递归调用通过栈处理参数和返回地址，递归层数过多会导致栈溢出。

三、排序算法

仅保留 CSP-J 超高频考点，核心关注时间复杂度、稳定性。

四、线性数据结构

1. 数组（顺序表）
   支持随机访问，插入/删除效率低。

2. 链表
   不支持随机访问，插入/删除效率高；节点由数据域 + 指针域组成。

3. 栈 (Stack)

   • 核心特性：后进先出 (LIFO)。
   • 核心操作：入栈 (push)、出栈 (pop)。
   • 高频考点：进栈出栈序列合法性判断；应用场景：表达式求值、括号匹配、递归/函数调用。

4. 队列 (Queue)

   • 核心特性：先进先出 (FIFO)。
   • 高频考点：应用场景：广度优先搜索 (BFS)。

五、树（分值占比高）

1. 树的基础性质

   • 节点总数 = 所有节点总度数 + 1（根节点）。
   • 节点的度：节点的子节点个数；树的度：所有节点度的最大值。
   • 叶子节点：度为 0 的节点。

2. 二叉树（核心）

   • 核心性质：
     1. 第 i 层最多有 2^(i-1) 个节点。
     2. 深度为 k 的二叉树，最多有 2^k - 1 个节点。
     3. 任意二叉树，叶子节点数 n₀ = 度为 2 的节点数 n₂ + 1。
   • 满二叉树：深度 k，节点数 2^k - 1，每层节点全满。
   • 完全二叉树：除最后一层外其余层全满，最后一层节点靠左排列。
   • 二叉树遍历：前序（根左右）、中序（左根右）、后序（左右根）、层序；高频考点：已知两种遍历序列，求第三种。

3. 特殊二叉树

   • 哈夫曼树（最优二叉树）：带权路径长度最短，无度为 1 的节点；n 个叶子节点的哈夫曼树，总节点数 2n-1。
   • 二叉搜索树 (BST)：左子树所有节点 < 根 < 右子树所有节点，中序遍历为有序序列。

六、图

1. 基础性质

   • 无向图：总度数 = 2 × 边数；有向图：总入度 = 总出度 = 边数。
   • 无向完全图：n 个顶点，边数 n(n-1)/2；有向完全图：边数 n(n-1)。
   • 生成树：n 个顶点的连通图，生成树有且仅有 n-1 条边，无环且连通。

2. 图的存储
   邻接矩阵（二维数组）、邻接表。

3. 图的遍历

   • 深度优先遍历 (DFS，栈/递归)
   • 广度优先遍历 (BFS，队列)

4. 一笔画问题（欧拉路径）

   • 无向图可一笔画：连通，且奇度顶点数为 0 或 2。
   • 奇度顶点数为 0：欧拉回路（可回到起点）；为 2：欧拉路径。

第三篇 数学基础

一、简单数论

1. 带余除法
   被除数 = 除数 × 商 + 余数，0 ≤ 余数 < 除数。

2. 素数与合数
   素数（质数）是大于 1，仅能被 1 和自身整除的数；1 既不是素数也不是合数。

3. 最大公约数 (gcd) 与最小公倍数 (lcm)
   a × b = gcd(a, b) × lcm(a, b)。

4. 欧几里得算法（辗转相除法）
   gcd(a, b) = gcd(b, a mod b)。

5. 奇偶性运算

   • 奇 ± 奇 = 偶，偶 ± 偶 = 偶，奇 ± 偶 = 奇。
   • 奇 × 奇 = 奇，偶 × 任意数 = 偶。

二、排列组合

1. 两大原理

   • 加法原理（分类）：完成一件事有 n 类方案，总方法数为各类方案数之和。
   • 乘法原理（分步）：完成一件事分 n 个步骤，总方法数为各步骤方法数之积。

2. 核心公式

   • 排列（有序）：A(n, m) = n! / (n-m)!
   • 组合（无序）：C(n, m) = n! / (m! × (n-m)!)
     • C(n, m) = C(n, n-m)
     • C(n, 0) = 1

3. 高频方法
   捆绑法、插空法、隔板法、排除法。