CSP-J/S考前知识点复习【计算机+基础知识+数论+数据结构+算法】考点总结_csp第一轮复习资料

CSP-J/S第一轮测试的考察题型是：

1. 选择题，共15题，每题2分，共30分；
2. 阅读程序题，共计40分。一般（特殊标记除外）三道程序题目，判断题每题1.5分，选择题每题3分；
3. 完善程序题，共计30分，选择题目，每题3分；一般两道题目。

主要考点包括但不限于：

• 计算机知识
  • 计算机历史/名人
  • 操作系统、硬件和软件
  • 网络协议
  • 其他
• 数论
  • 排列组合
  • 进制转换
  • 原码、反码、补码
  • 其他
• 数据结构
  • 栈 （常考）
  • 队列
  • 树 （常考）
  • 图
• 算法
  • 计算时间（空间）复杂度 （常考）
  • 排序算法
  • 二分查找
  • 递归、递推
  • 高精度运算
  • DP
  • 其他

文章目录

• 计算机基础
• • 计算机历史
  • • 计算机名人
  • 基础知识
  • • 计算机系统的构架与工作原理
    • • 硬件系统
      • 软件系统
    • 计算机存储单位
    • 字符编码
• 数学相关
• • 计数问题
  • • 加法原理与乘法原理
    • 排列组合
    • • A n m A_n^m Anm​与 C n m C_n^m Cnm​
      • 捆绑法
      • 隔板法 / 抽空法
  • 进制转换
  • • 其他进制数与十进制数的转换
    • • 二、八、十六进制数转十进制数
      • 十进制数转二、八、十六进制数
  • 原码、反码、补码
  • • 原码
    • 反码
    • 补码
  • 数论
  • • 数论四大定理
    • • 威尔逊定理
      • 费马小定理
      • 欧拉定理
      • 中国剩余定理（CRT）
• 数据结构
• • 线性数据结构
  • • 栈
    • 队列
  • 树与图
  • • 树
    • • 二叉树
      • 哈夫曼编码
    • 图
    • • 图的相关术语
      • 图的遍历
      • • 深度优先遍历
        • 广度优先遍历
  • 链表
  • • 单链表
    • 双链表
  • 表达式
  • • 中缀表达式
    • 前缀表达式
    • 后缀表达式
• 算法
• • 时间复杂度
  • 空间复杂度
  • 排序算法
  • • 插入排序
    • 冒泡排序
    • 选择排序
    • 归并排序
    • 快速排序
    • 计数排序
    • 希尔排序
  • 贪心算法
  • 二分算法
  • • 二分查找
    • 二分答案
  • 动态规划
  • • 主要思想
    • DP

计算机基础

计算机历史

代别 年代 元件 应用场景 第一代 1940s-1950s 电子管 科学计算、军事研究 第二代 1950s-1960s 晶体管 数据处理、事物处理 第三代 1960s-1970s 集成电路 工业控制的各个领域 第四代 近代 大规模、超大规模集成电路 各个领域 第五代 1980s-至今 智能计算机系统 办公、人工智能

计算机名人

冯 · 诺依曼，美国数学家、科学家、现代计算机之父。提出冯诺依曼理论。

冯 · 诺依曼理论：

1. 计算机硬件设备由五部分组成：输入设备、输出设备、存储器、运算器、控制器。

2. 存储程序思想：将程序指令和数据存储在同一存储器中，并通过指令来控制计算机的操作。

---

图灵，英国数学家、生物学家、科学家、计算机科学/人工智能之父，首次提出了计算机科学理论。计算机界的最高奖项\"图灵奖\"以他命名，被称为\"计算机界的诺贝尔奖\"。

---

基础知识

计算机系统的构架与工作原理

一个完整的计算机系统由硬件系统和软件系统构成（如下图），没有软件系统的硬件称为”裸机“，”裸机“是无法直接使用的。

硬件系统

1.中央处理器（CPU）

#mermaid-svg-1i8hAtmXzmnwgprM {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-1i8hAtmXzmnwgprM .error-icon{fill:#552222;}#mermaid-svg-1i8hAtmXzmnwgprM .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-1i8hAtmXzmnwgprM .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-1i8hAtmXzmnwgprM .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-1i8hAtmXzmnwgprM .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-1i8hAtmXzmnwgprM .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-1i8hAtmXzmnwgprM .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-1i8hAtmXzmnwgprM .marker{fill:#333333;stroke:#333333;}#mermaid-svg-1i8hAtmXzmnwgprM .marker.cross{stroke:#333333;}#mermaid-svg-1i8hAtmXzmnwgprM svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-1i8hAtmXzmnwgprM .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-1i8hAtmXzmnwgprM .cluster-label text{fill:#333;}#mermaid-svg-1i8hAtmXzmnwgprM .cluster-label span{color:#333;}#mermaid-svg-1i8hAtmXzmnwgprM .label text,#mermaid-svg-1i8hAtmXzmnwgprM span{fill:#333;color:#333;}#mermaid-svg-1i8hAtmXzmnwgprM .node rect,#mermaid-svg-1i8hAtmXzmnwgprM .node circle,#mermaid-svg-1i8hAtmXzmnwgprM .node ellipse,#mermaid-svg-1i8hAtmXzmnwgprM .node polygon,#mermaid-svg-1i8hAtmXzmnwgprM .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1i8hAtmXzmnwgprM .node .label{text-align:center;}#mermaid-svg-1i8hAtmXzmnwgprM .node.clickable{cursor:pointer;}#mermaid-svg-1i8hAtmXzmnwgprM .arrowheadPath{fill:#333333;}#mermaid-svg-1i8hAtmXzmnwgprM .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-1i8hAtmXzmnwgprM .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-1i8hAtmXzmnwgprM .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-1i8hAtmXzmnwgprM .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-1i8hAtmXzmnwgprM .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-1i8hAtmXzmnwgprM .cluster text{fill:#333;}#mermaid-svg-1i8hAtmXzmnwgprM .cluster span{color:#333;}#mermaid-svg-1i8hAtmXzmnwgprM div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-1i8hAtmXzmnwgprM :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 中央处理器 操作命令 操作命令 指令 数据 运算结果 寄存器 控制器 运算器 内存储器

CPU的性能指标
计算机运算速度指计算机每秒执行的指令数，它是一项综合的性能指标。其中CPU的主要性能指标包括主频和字长。

2.存储器
存储器主要用来存储程序及相关数据信息。

内存储器

• RAM：随机存储器。断电后，RAM中的数据随之丢失。
• ROM：只读存储器。断电后，ROM中的数据保持不变。
• Cache：高速缓冲存储器。

外存储器
分为软盘、硬盘、闪存和光盘

软件系统

• 软件系统
  • 系统软件
    • 操作系统
    • 其他系统软件
      • 语言处理系统
      • 数据库管理系统
  • 应用软件
    • 用户编制软件
    • 各种工具软件
      操作系统 的主要功能包括：

1. 处理机管理
2. 存储管理
3. 文件管理
4. 设备管理
5. 进程管理
   常见的操作系统包括Windows系列、UNIX系列、Linux系列、macOS系列等。
   程序设计语言及其处理程序

#mermaid-svg-DDcA8yb6gCVQxOKZ {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .error-icon{fill:#552222;}#mermaid-svg-DDcA8yb6gCVQxOKZ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-DDcA8yb6gCVQxOKZ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .marker.cross{stroke:#333333;}#mermaid-svg-DDcA8yb6gCVQxOKZ svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-DDcA8yb6gCVQxOKZ .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .cluster-label text{fill:#333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .cluster-label span{color:#333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .label text,#mermaid-svg-DDcA8yb6gCVQxOKZ span{fill:#333;color:#333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .node rect,#mermaid-svg-DDcA8yb6gCVQxOKZ .node circle,#mermaid-svg-DDcA8yb6gCVQxOKZ .node ellipse,#mermaid-svg-DDcA8yb6gCVQxOKZ .node polygon,#mermaid-svg-DDcA8yb6gCVQxOKZ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-DDcA8yb6gCVQxOKZ .node .label{text-align:center;}#mermaid-svg-DDcA8yb6gCVQxOKZ .node.clickable{cursor:pointer;}#mermaid-svg-DDcA8yb6gCVQxOKZ .arrowheadPath{fill:#333333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-DDcA8yb6gCVQxOKZ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-DDcA8yb6gCVQxOKZ .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-DDcA8yb6gCVQxOKZ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-DDcA8yb6gCVQxOKZ .cluster text{fill:#333;}#mermaid-svg-DDcA8yb6gCVQxOKZ .cluster span{color:#333;}#mermaid-svg-DDcA8yb6gCVQxOKZ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-DDcA8yb6gCVQxOKZ :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 汇编程序 连接程序 编译程序 链接程序 解释代码 以及 汇编语言的执行过程 汇编语言源程序 目标程序 可执行程序 高级语言的执行过程 高级语言源程序 目标程序 可执行程序 解释型高级语言 执行代码 生成结果

计算机存储单位

1TB= 2 10 GB= 2 20 MB= 2 30 KB= 2 40 B 1 TB=2^{10} GB=2 ^{20} MB=2 ^{30} KB=2 ^{40} B 1TB=210GB=220MB=230KB=240B
也就是说，

$1KB=1024B$

$1MB=1024KB$

$1GB=1024MB$

$1TB=1024GB$

$$1B(Byte)=8b(bit)$$
也就是说，$1Mb=1024b=128B$，以此类推。

字符编码

字符是人和计算机交互过程中不可缺少的重要信息。要使计算机能处理、存储字符信息，首先也必须用计算机能识别的二进制代码来存储。

ASCII 码最初由美国国家标准协会（ANSI）于 1963 年制定，后来得到了广泛采用。ASCII 码使用 7 二进制数来表示字符，共计 128 个不同的字符，包括了各种英文字母、数字、标点符号以及一些特殊控制字符。

数学相关

计数问题

计数问题是CSP第一轮认证的“高频”知识点，一般出现在单线选择题。

加法原理与乘法原理

加法原理
例题：小A同学去吃午饭，先去A店吃3个汉堡，再去B店吃4个汉堡，问他共吃了多少个汉堡（答案： $3+4=7$ 个汉堡）
乘法原理
例题：小A同学去吃午饭，去A店在3种不同汉堡里选一种吃，去B店在4种不同汉堡里选一种吃，（答案： $3\times 4=12$ 个汉堡）

排列组合

A n m A_n^m Anm​与 C n m C_n^m Cnm​

n 个不同的元素的全排列有 $n!$ 种方式。
n 个不用的元素中要选择 m 个元素进行全排列有 A n m = n !( n − m ) ! {A_n^m} = \\frac{n!}{(n-m)!} Anm​=(n−m)!n!​ ，也就是从$n$乘到$n-m+1$。
n 个不同的元素种要选择 m 个元素组合不考虑排序有 C n m C_n^m Cnm​种，即等于 A n mm ! \\frac{A_n^m}{m!} m!Anm​​。

捆绑法

在做排列的题目时，解决某些元素相邻(要求在一起)问题常用捆绑法：把相邻元素看作一个整体，再与其他元素一起排列，同时注意捆绑元素的内部排列。

隔板法 / 抽空法

插空法，数学术语，是用来解决某些元素不相邻的排列组合题，即不邻问题。在解决对于某几个元素要求不相邻的问题时，先将其它元素排好，再将指定的不相邻的元素插入已排好元素的间隙或两端位置，从而将问题解决的策略。用这种方法解题思路清晰、简便易懂。

进制转换

整型有4种进制形式：
十进制：由0-9数字组成，逢十进一。是生活中最常见的进制。
二进制：由0和1两个数字组成，逢二进一。
八进制：由0-7数字组成，为了与其他进制的数字进行区分，通常开头以0作为标记表示八进制。
十六进制：由0-9和A-F组成。A代表十进制的11，B代表十进制的12，以此类推。

不同进制的数据有3种书写方式。

1. 10011010 ( 2 ), 232 ( 8 ), 154 ( 10 ), 9 A ( 16 ) 10011010_{(2)}, 232_{(8)}, 154_{(10)}, 9 A_{(16)} 10011010(2)​,232(8)​,154(10)​,9A(16)​ ；
2. ( 10011010 ) 2 , ( 232 ) 8 , ( 154 ) 10 , ( 9 A ) 16 (10011010)_{2}, (232)_{8}, (154)_{10}, (9 A)_{16} (10011010)2​,(232)8​,(154)10​,(9A)16​ ；
3. $10011010B,232O,154D,9AH$ (其中的B、O、D、H分别表示二进制、八进制、十进制和十六进制) 。

其他进制数与十进制数的转换

二、八、十六进制数转十进制数

二、八、十六进制数转十进制数采用 “按权展开” 的方式。
例：
将 (1011.101 ) 2 (1011.101)_{2} (1011.101)2​ 转为十进制数。
转换整数部分：
(1011 ) 2 =1× 2 3 +0× 2 2 +1× 2 1 +1× 2 0 (1011)_{2} = 1\\times 2^3 + 0\\times 2^2 + 1\\times 2^1 + 1\\times 2^0 (1011)2​=1×23+0×22+1×21+1×20
转换小数部分：
(0.101 ) 2 =1× 2 − 1 +0× 2 − 2 +1× 2 − 3 (0.101)_{2} = 1\\times 2^{-1} + 0\\times 2^{-2} + 1\\times 2^{-3} (0.101)2​=1×2−1+0×2−2+1×2−3
所以：
(1011.101 ) 2 =1× 2 3 +0× 2 2 +1× 2 1 +1× 2 0 +1× 2 − 1 +0× 2 − 2 +1× 2 − 3 =8+0+2+1+ 1 2 +0+ 1 8 =(11.625 ) 10 (1011.101)_{2} = 1\\times 2^3 + 0\\times 2^2 + 1\\times 2^1 + 1\\times 2^0 + 1\\times 2^{-1} + 0\\times 2^{-2} + 1\\times 2^{-3} = 8 + 0 + 2 + 1 + \\frac{1}{2} + 0 + \\frac{1}{8} = (11.625)_{10} (1011.101)2​=1×23+0×22+1×21+1×20+1×2−1+0×2−2+1×2−3=8+0+2+1+21​+0+81​=(11.625)10​

十进制数转二、八、十六进制数

十进制数转$n$进制数的方法是：
整数部分：除以$n$取余数，直到商为0，余数反向排列。
小数部分：乘以$n$取整数，整数从左到右排列。
例： 100.345 10 =1100100.010112 100.345_{10} = 1100100.01011{2} 100.34510​=1100100.010112

原码、反码、补码

机器数是将符号”数字化“的数。一般在计算机中用二进制表示。

原码

原码的表示方法非常直观。与真值、十进制数的转换非常方便。

• 对于有符号数而言，规定最高位是符号位，0 表示正数，1 表示负数，非符号位是该数字绝对值的二进制。

例如，用1字节来存储一个整数时，十进制的$+36$与$-36$的原码表示为：
[ + 36 ] 原 = 0010   0100 [+36]_{原}=0010\\, 0100 [+36]原​=00100100
[ − 36 ] 原 = 1010   0100 [-36]_{原}=1010\\, 0100 [−36]原​=10100100

反码

原码的负数加减法运算复杂，且原码中的0表示不唯一。为了克服原码的缺点，采用反码表示。

• 规定正数的反码与原码一致，负数的反码是对原码按位取反，只是最高位（符号位）不变。

例如，用1字节来存储一个整数时，十进制的$+36$与$-36$的反码表示为：
[ + 36 ] 反 = 0010   0100 [+36]_{反}=0010\\, 0100 [+36]反​=00100100
[ − 36 ] 反 = 1101   1011 [-36]_{反}=1101\\, 1011 [−36]反​=11011011

补码

反码中的0任然表示不唯一。则采用补码。

• 规定正数的补码与原码一致，负数的补码对反码 $+1$ 。

例如，用1字节来存储一个整数时，十进制的$+36$与$-36$的补码表示为：
[ + 36 ] 补 = 0010   0100 [+36]_{补}=0010\\, 0100 [+36]补​=00100100
[ − 36 ] 补 = 1101   1100 [-36]_{补}=1101\\, 1100 [−36]补​=11011100

数论

数论四大定理

威尔逊定理

$(p-1)!\equiv -1(modp)$和$p$为素数等阶

费马小定理

若$p$为素数，且$gcd(a,p)=1$，则 a p − 1 ≡1(mod   p) a^{p-1}\\equiv 1(mod\\,p) ap−1≡1(modp)

欧拉定理

若$gcd(a,n)=1$，，则 a φ ( n ) ≡1(mod   n) a^{\\varphi (n)}\\equiv 1(mod\\,n) aφ(n)≡1(modn)

中国剩余定理（CRT）

求解同余方程，
{ x ≡ a 1 ( m o d   m 1 ) x ≡ a 2 ( m o d   m 2 ) . . . x ≡ a n ( m o d   m n ) \\left\\{\\begin{matrix}x\\equiv a_1(mod\\,m_1) \\\\x\\equiv a_2(mod\\,m_2) \\\\... \\\\x\\equiv a_n(mod\\,m_n) \\end{matrix}\\right. ⎩ ⎨ ⎧​x≡a1​(modm1​)x≡a2​(modm2​)...x≡an​(modmn​)​
其中 m 1 , m 2 ,..., m n m_1,m_2,...,m_n m1​,m2​,...,mn​均为两两互素的整数。

数据结构

线性数据结构

栈

栈：只能在某一端插入或删除的特殊线性表，即FILO。

典型考题：合法出栈顺序

方法：依次枚举
例题：入栈顺序A B C D，以下出栈顺序不合法的是（$D$）

• A. A B C D(A入栈→A出栈→B入栈→B出栈→C入栈→C出栈→D入栈→D出栈)
• B. D C B A(ABCD入栈→DCBA出栈)
• C. B A C D(AB入栈→BA出栈→C入栈→C出栈→D入栈→D出栈)
• D. A D B C(A入栈→A出栈→BCD入栈→D出栈，此时栈内C在B上面，B无法出栈)

实现栈的主要方法 有数组模拟栈和STL两种。
数组模拟栈：

1. 准备数组 sta 和标记变量 t=0 。
2. 入栈：将 sta[++t] 赋值为新入栈元素。
3. 出栈： t--; 。
4. 栈顶元素：sta[t]。
5. 判断栈为空： t==0 。
   STL栈：
   一、导入库。
   例如：

#include 

二、定义变量。
常见定义方法：stack变量名称;
例如：

stack<int> sta; // 定义一个元素为整数的栈sta

三、栈的常用成员函数。
下表中的stack为栈的变量名称。

函数 作用 stack.empty() 判断栈是否为空。如果栈为空，返回 true，否则返回 false。 stack.size() 返回栈中实际的元素个数。 stack.push(e) 将元素e压入栈顶。 stack.top() 访问栈顶元素。 stack.pop() 使栈顶元素出栈。

队列

一种从一端删除(队头)另一端插入(队尾)的特殊线性表，即FIFO。

实现队列的主要方法 有数组模拟队列和STL两种。
数组模拟

1. 准备数组q，队头标记变量h=1，队尾标记变量t=0；
2. 入队：q[++t]=要入队的元素；
3. 出队：h++;
4. 队首元素：q[h]；
5. 判断为空：t<h。
   STL
   导入：#include
   定义：queue变量名称;
   例如：

#include queue<int>que;

队列常用的成员函数：

函数 作用 que.empty() 判断队列是否为空。如果为空，返回 true，否则返回 false。 que.size() 返回队列中实际的元素个数。 que.push(e) 将元素e压入队尾。 que.front() 访问队首元素。 que.pop() 使栈队首素出队。

树与图

树

树型结构是一类重要的非线性数据结构。直观看来，树是以分支关系定义的层次结构。把它叫做“树”是因为它常看起来像一棵倒挂的树，也就是说它常是根朝上，而叶朝下的。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。
树的性质：对于一颗有$n$个节点的树，有$n-1$条边（总节点数-根节点=边数）

二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。对于一颗深度为$k$二叉树，其节点数最多为 2 k −1 2^{k}-1 2k−1,第$i$层节点数最多为 2   i − 1 2 \\ ^{i - 1} 2 i−1。

二叉树树便利：遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个节点转换成为一个线性序列来表示。二叉树遍历分先序遍历、中序遍历、后序遍历。

1. 先序遍历：根据“根 - 左 - 右”的原则，先处理根，再处理左子树，再处理右子树，子树按同样的方法处理。
2. 中序遍历：根据“左 - 根 - 右”的原则，先处理左子树，再处理根，再处理右子树，子树按同样的方法处理。
3. 后序遍历：根据“左 - 右 - 根”的原则，先处理左子树，再处理右子树，最后输出根，子树按同样的方法处理。

我们只需要知道中序遍历和任意其他一种遍历，即可得知另一种遍历，这也是考试中常考的知识点。如：
前序遍历为1234，中序遍历为2134，后续遍历为（答案：2431）。

哈夫曼编码

首先，将符号按照出现概率由大到小排队，如图1所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。
寻找一个符号的哈夫曼编码，只需从哈夫曼树的根节点开始，往左写0, 往右则写1.

图

图也是一类重要的非线性数据结构。

有向图、无向图
如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。

图的相关术语

度：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。
入度 和 出度：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
环：当从一个节点出发，不走回头路，能回到这个节点，则称它为一个环。
自环：若一条边的两个顶点为同一顶点，则此边称作自环。
路径：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,…ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。

图的遍历

常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。

深度优先遍历

深度优先遍历的遍历过程可以描述为：从图中某个节点出发，访问该节点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余节点，直至图中所有与起始节点有路径相通的节点都被访问完为止。

例如：有个图：

 a--b--c / | \\ d -- e f

这时，假设我们从a节点开始遍历，那么遍历的大致过程为（以下为递归过程，每个缩进表示为上一层产生的递归）：

• 遍历a，层数为1，并将a存入标记数组，表示已经遍历过该节点。
  • 遍历b，层数为2，并将b存入标记数组。
    • 遍历e，层数为3，并将e存入标记数组。
      • 回到b，发现b已经被标记，没有可以遍历的地方，结束。
    • 遍历c，层数为3，并将c存入标记数组。
      • 遍历f，层数为4，并将f存入标记数组。
        • 回到c，发现c已经被标记，没有可以遍历的地方，结束。
    • 回到b，发现b已经被标记，没有可以遍历的地方，结束。
  • 遍历d，层数为2，并将d存入标记数组。
    • 回到a，发现a已经被标记，返回。
    • 来到e，发现e已经被标记，没有可以遍历的地方，结束。

广度优先遍历

广度优先遍历对图的广度优先遍历方法描述为：从图中某个节点v出发，在访问该节点v之后，依次访问v的所有未被访问过的邻接节点，然后再访问每个邻接节点的邻接节点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有节点都被访问为止。

int visited[0..n-1]={0,0,...0};void BFS(AdjList adj,int v){//v是遍历起始点在邻接表中的下标，邻接表中下标从0开始InitQueue(Q); //Q是队列visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);while (!QueueEmpty(Q)) {DeQueue(Q,v);for (w=adj[v].firstedge;w;w=w->ext)if (!visited[w->adjvex]) {visited[w->adjvex]=1;visite(adj[w->adjvex].elem);EnQueue(Q,w->adjvex); }}}

链表

单链表

在a的后面插入元素p:

p->next = a->next;a->next = p;

删除元素p:

a->next = p->next;delete p;

双链表

[[元素]]⇄[[元素]]⇄[[元素]]…
插入p：

q->next = p;q->prev = p->prev;p->prev->next = q;p->prev = q;

删除p：

p->prev->next = p->next;p->next->prev = p->prev;//下面这行可写可不写，如果内存规定较紧，建议写上delete p;

表达式

中缀表达式

同普通表达式。

前缀表达式

前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
将表达式里最低级的运算符作为根，一个进行运算的数按同样的方式作为左孩子，右子树同上；将得到的这棵树进行前序遍历，得到的结果即为此表达式的前缀表达式。

后缀表达式

后缀表达式（将运算符写在操作数之后），也叫逆波兰式（RPN，或逆波兰记法）。
将一个普通的中缀表达式转换为逆波兰表达式的一般算法是：首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为存放结果（逆波兰式）的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：

1. 若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈。
2. 若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符（包括左括号）优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符（包括左括号）低于（不包括等于）该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。
3. 若取出的字符是“（”，则直接送入S1栈顶。
4. 若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
5. 重复上面的1~4步，直至处理完所有的输入字符。
6. 若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。完成以上步骤，S2栈便为逆波兰式输出结果。

不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！

算法

算法是指解题方案的准确而完整的描述。
算法包括以下特征：

• 有穷性：算法必须能在执行有限个步骤之后终止
• 确切性：算法的每一步骤必须有确切的定义
• 可行性：也称之为有效性
• 输入项：一个算法有输入，以刻画运算对象的初始情况
• 输出项：没有输出的算法是毫无意义的

我们可以通过 时间复杂度 和 空间复杂度 来衡量算法的优劣。

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。
一个算法的时间复杂度为 $x$ 的算法的时间复杂度可用 $O(x)$ 来表示。
一般的，当一个算法的时间复杂度更小时，我们认为这个算法更快，在一定程度上更佳。
顺序结构的算法的时间复杂度为 $O(1)$ 。
对于循环结构的算法的时间复杂度，例如：

for (int i = 1; i <= n; i++)

以上这部分程序的时间复杂度为 $O(n)$ 。

for (int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)

以上这段程序的时间复杂度为 $O(n\times m)$ 。

当一个算法有多处可计算时间复杂度时，选择时间复杂度（通常为时间复杂度的次数）最高的一处的时间复杂度作为整个算法的时间复杂度。
例如：

while (m--) // 此处的时间复杂度为O(m)for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) // 此处的时间复杂度为O(n²)

以上这段程序的时间复杂度为 O( n 2 ) O(n^2) O(n2) 。

空间复杂度

空间复杂度在CSP-J中考察频率及难度并不高。
算法的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

排序算法

我们可以通过稳定性、时间复杂度、空间复杂度等信息来比较各个排序算法。

排序算法的 稳定性 指相等元素在排序后的相对位置是否保持不变。
即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

下表通过展示7种常见（常考）的排序算法的稳定性、时间复杂度和思想来比较这些排序算法。

名字 稳定性 平均时间复杂度 最坏时间复杂度 类别 插入排序 稳定 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) 基于大小比较的排序 冒泡排序 稳定 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) 基于大小比较的排序 选择排序 不稳定 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) 基于大小比较的排序 归并排序 稳定 $O(n\log n)$ $O(n\log n)$ 基于分治策略的排序 快速排序 不稳定 $O(n\log n)$ O ( n 2 ) O(n^2) O(n2) 基于分治策略的排序 计数排序 稳定 $O(n)$ $O(n)$ 线性排序 希尔排序 不稳定 O ( n 3 / 2 ) O(n^{3/2}) O(n3/2) O ( n 3 / 2 ) O(n^{3/2}) O(n3/2) -

插入排序

设有 $len$ 条记录存放在数组 $A$ 中，重新安排记录在数组中的存放顺序，使得按关键码有序。插入排序的过程简单地说就是逐一地将待排序数组元素插入一个已经有序的序列中。
下图是将一个无序数组插入排序的过程

伪代码 ：将A数组排序(len为A的长度)

for (signed j = 2; j < len; j++) { key=A[j]; //将A[j]插入已排序序列A[1..j-1] i=j-1; while (i>0 and A[i]>key) { A[i+1]= A[i]; i=i-1; A[i+1]=key;}}

冒泡排序

冒泡排序是最简单和最通用的排序方法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序。

伪代码 ：将数组arr排序（len是arr的长度)

for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; }

选择排序

它的工作原理是第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

伪代码 ：将S数组选择排序

归并排序

归并排序是一种借助“归并”来排序的方法，所谓归并，是指两个或两个以上的有序数列合并成一个有序序列的过程。二路归并排序是最简单的一种规定排序方法。
二路归并排序的基本操作是先将无序表分为两个无序表，直到无序表的长度为1。再将两个有序表合并为一个有序表。

伪代码 ：合并两个有序线性表

arr_a = {1,4,5,6}arr_b = {4,4,8,10}// 伪代码如下： result = []; idx_a, idx_b; while (idx_a<arr_a.size() && idx_b<arr_b.size()) if (arr_a[idx_a]<=arr_b[idx_b]) result[arr_a[idx_a]]; idx_a+=1; else if (arr_a[idx_a]>arr_b[idx_b]) result[arr_b[idx_b]]; idx_b+=1; if (idx_a==arr_a.size()) result.extend(arr_b[idx_b] to arr_b[arr_b-1]);//当然，写代码的时候没有extend和to这个东西

快速排序

快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素 p ，利用 p 将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列变得有序。

实现（通用代码） ：

计数排序

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
对于一个长度为 $n$ 的线性表：

准备记录数组a；重复n次： 输入当前元素x; 将a[x]增加1；重复n次，循环变量为i： 重复a[i]次： 输出i；

希尔排序

希尔排序是对前面几种基于大小比较的排序的较大改进的排序算法。
希尔排序步骤如下：

1. 选择一个补偿序列， t 1 t_1 t1​ ， t 2 t_2 t2​ ，…， t k t_k tk​ ，其中 t i > t i + 1 t_i>t_i+1 ti​>ti​+1 ， t k = 1 t_k=1 tk​=1。
2. 按步长序列个数k，对序列进行k次排序。
3. 每次排序根据对应的步长 t i t_i ti​，将待排序列分割为若干长度为$m$的子序列，分别对各子表进行直接插入排序，仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

贪心算法

贪心思想的核心思想是在每一步决策中都选取局部最优解，期望通过一系列的局部最优选择达到全局最优解。 并非所有问题都能通过贪心算法找到真正的全局最优解 ，因为某些情况下这种策略可能会导致次优的结果。在下面我们将详细解释。

贪心并没有一个具体的模板。
贪心适用于在每一步选择中，局部最优解可以导向全局最优解的问题。

先来看一非常经典的例子：

接水问题 ：有$n$人排队接水，第$i$个人需要的节水时间为 a i a_i ai​，如何让所有人的平均等待时长最短？
根据贪心思想，一般地，会让节水时间更短的人排到更前面。这样一来，所有人的节水时间都是最短的。

区间类贪心 ：即区间覆盖问题。寻找能够完全遮盖某个实数轴区间的最少数目线段集。

时间安排问题 ：即活动选择问题，给定一组相互冲突的任务列表及其起始结束时间，目标是挑选最多互斥任务执行。

贪心思想的优点：

• 贪心算法通常非常直观和易于理解，解决问题的思路简单直接。
• 贪心算法的时间复杂度通常较低，适合解决某些大规模问题。常见的时间复杂度为 O(n log n) 或 O(n)。
• 贪心算法在诸如图论（如最小生成树、最短路径）、任务调度、资源分配等多个领域有广泛的应用。

贪心思想的缺点：

• 贪心算法并不总能找到问题的最优解。它依赖于每一步的局部最优选择，可能会错过全局最优解。例如，背包问题（经典的DP）的贪心算法不能保证找到最优解。
• 贪心算法只有在某些特定类型的问题（满足贪心选择性质和最优子结构性质）中才能有效工作。对于不满足这些性质的问题，贪心算法无法保证最优解。
• 贪心算法一旦做出选择，就不会回溯或改变决定。因此，一旦做出错误的选择，就无法修正。

二分算法

二分算法一般分为二分查找和二分答案。注意：二分查找和二分答案并不是同一种算法！！！
我们先来看一个图以了解该算法的主要思想：

我们需要二分的答案就是这个临界点x。
二分算法一般用于在单调不减或单调不增的线性表中寻找大于某数的最小值或小于某数的最大值，也可以用于实数的枚举（例如开根号）。
单调不减或单调不增是指一个线性表是有序的。
一般做法是：将一个线性表用中间值一分为二，发现中间值大了，就数值小的一块再一分为二。类似地，如果中间值小了，就把大的那一块一分为二。以此类推。
在下面的介绍中，将用“数组”代替“线性表”。

二分查找

我们首先来看模板：
模板1：

while (l < r) { int mid = l + r >> 1;//(l+r)/2 if (/*判断条件*/) r = mid; // 判断是否满足性质 else l = mid + 1; }

模板2：

while (l < r) { int mid = l + r >> 1;//(l+r)/2 if (/*判断条件*/) r = mid; // 判断是否满足性质 else l = mid + 1; }

第一个模板是尽量往左找目标，第二个模板是尽量往右找目标。
只要是往左找答案，就用第一个模板，mid不用加一，r=mid，l加一；
只要是往右找答案，就用第二个模板，mid要加一，l=mid，r要减一;
二分套这两个模板，肯定没错！（只要判断条件写对）

模板3：实数二分

while(r-l>1e-5) //需要一个精度保证{double mid = (l+r)/2;if(/*判断条件*/) l=mid; //或r=mid;else r=mid; //或l=mid;}

二分答案

二分算法的区别：
二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

---

什么是二分答案？

答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

当题目中有“求…最大值的最小 、 求…最小值的最大”，我们一般用二分答案。

模板：

• 尽量往左找答案：

  //求最小的最大值int bsearch(int l, int r){while (l < r){ int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1;}return l;}

• 尽量往右找答案

  //求最大的最小值int bsearch(int l, int r){ while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l;}

动态规划

动态规划，也称DP，是一种广泛应用于数学、计算机科学和经济学等地方的方法论。其核心思想是通过将复杂问题分解为相对简单的子问题，并存储子问题的解以避免冗余计算，从而显著提高计算效率。

主要思想

动态规划常常适用于具有重叠子问题和最优子结构性质的问题。其基本思想是将待求解的问题分解为若干个相关联的子问题，先求解子问题，然后利用这些子问题的解来构造原问题的解。
对于重复出现的子问题，只在第一次遇到的时候对他进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。

通俗来讲，动态规划算法是解决一类具有重叠子问题和最优子结构性质的问题的有效方法。其基本原理是将大问题分解为小问题，通过保存中间结果来避免重复计算，从而提高算法的效率。动态规划方法所耗时往往远少于朴素解法。

动态规划的基本过程包括定义子问题，解决子问题，合并子问题的解来求解原问题。动态规划通常采用自底向上的方式进行，通过迭代计算子问题并存储子问题的解，逐步求解更大规模的问题，直到求解出原问题。

DP

下面是动态规划的非常经典的问题：

• 最长公共子序列
• 背包问题
• 矩阵链路乘法
• 硬币找零问题

优点：

• 对于具有重叠子问题和最优子结构性质的问题，动态规划可以显著提高求解效率，避免不必要的重复计算。通过存储和复用子问题的解，动态规划算法能够避免重复计算相同的子问题，从而大大减少计算量。
• 动态规划算法的代码通常比较简洁，易于理解和实现。一旦确定了问题的状态转移方程和边界条件，动态规划算法的代码实现往往非常直观和简洁。

缺点：

• 对于没有重叠子问题和最优子结构性质的问题，动态规划算法可能并不适用，此时需要考虑其他算法。动态规划算法的有效性建立在问题的重叠子问题和最优子结构性质上，如果问题不具备这些性质，那么动态规划算法就无法发挥其优势。
• 动态规划算法的空间复杂度通常较高，需要存储所有子问题的解，以便后续使用。这可能导致算法在处理大规模问题时需要消耗大量的内存空间。在某些情况下，可能需要考虑使用滚动数组或其他优化技巧来降低空间复杂度。滚动数组是一种常用的优化方法，它只保留当前需要使用的子问题解，从而避免了存储所有子问题的解。