A2-2.4.1
算法的基本概念，算法复杂度的概念和意义（时间复杂度与空间复杂度）。
算法的五大基本特征（必须全部背出，错一不可）
必记- 1. 有穷性（Finiteness）：算法必须在执行有限个步骤之后正常终止，不能陷入无限死循环
- 2. 确定性（Definiteness）：算法的每一步骤都必须有明确确定无二义性的定义，不能模糊含混
- 3. 可行性（Effectiveness）：算法中描述的操作都可以通过已经实现的基本运算执行有限次完成
- 4. 输入（Input）：算法具有零个或多个输入（可以没有任何外部输入）
- 5. 输出（Output）：算法必须具有一个或多个输出（没有任何输出的算法毫无实际意义！）
算法复杂度两大维度：时间复杂度 vs 空间复杂度
必记时间复杂度 T(n)
- 衡量度量本质
- 衡量算法执行所耗费的时间随问题规模 n 增长的渐进增长趋势
- 数学大 O 渐进符号表示法
- 以基本操作重复执行的频度度量，记作 O(f(n))
- 常见复杂度排序（从优到劣）
- O(1) 常数阶 < O(log n) 对数阶 < O(n) 线性阶 < O(n log n) 线性对数阶 < O(n^2) 平方阶 < O(2^n) 指数阶
空间复杂度 S(n)
- 衡量度量本质
- 衡量算法在运行过程中所需占用的额外临时辅助存储空间大小
- 数学大 O 渐进符号表示法
- 不包括输入数据本身所占空间，仅计算法运行额外分配的辅助空间
- 常见复杂度排序（从优到劣）
- 原地工作的排序算法空间复杂度通常为 O(1)
| 复杂度维度 | 衡量度量本质 | 数学大 O 渐进符号表示法 | 常见复杂度排序（从优到劣） |
|---|---|---|---|
| 时间复杂度 T(n) | 衡量算法执行所耗费的时间随问题规模 n 增长的渐进增长趋势 | 以基本操作重复执行的频度度量，记作 O(f(n)) | O(1) 常数阶 < O(log n) 对数阶 < O(n) 线性阶 < O(n log n) 线性对数阶 < O(n^2) 平方阶 < O(2^n) 指数阶 |
| 空间复杂度 S(n) | 衡量算法在运行过程中所需占用的额外临时辅助存储空间大小 | 不包括输入数据本身所占空间，仅计算法运行额外分配的辅助空间 | 原地工作的排序算法空间复杂度通常为 O(1) |
算法输入与输出易错陷阱
必记易错陷阱
专转本常考单选：“算法可以有 0 个输入，但必须至少有 1 个输出！” 如果某选项说“算法必须有至少一个输入”，则该说法必然是错误的。
随堂自测（3 题 · 共 397 道关联题）展开作答
在计算机科学中，算法的时间与空间____通常用O表示。
当问题规模 n 增大时，算法的执行时间 T(n) 的增长率和 f(n) 的增长率相同，即算法的执行时间 T(n)，可用时间度量 O(f(n)) 来衡量，该度量称为算法的 ____。
解决某一问题的算法也许有多种，但它们都必须满足确定性、有穷性、能行性、 输入和输出。其中输入的个数 n 应大于等于。（填一个数字）
A2-2.4.2
数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形表示，线性结构与非线性结构的概念。
数据结构的核心公式
必记计算机科学家沃思（Niklaus Wirth）提出经典名言：==程序 = 数据结构 + 算法==。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据的逻辑结构 vs 存储结构核心对比
必记| 结构维度 | 定义内涵与视角 | 细分类别与典型代表 |
|---|---|---|
| 逻辑结构 | 反映数据元素之间的逻辑关系，完全独立于计算机硬件存储实现 | 线性结构（一对一，如线性表/栈/队列/串）；非线性结构（树形结构一对多、图形网络多对多） |
| 存储结构（物理结构） | 数据元素及其关系在计算机内存中的具体实际存储表现形式 | 顺序存储结构（数组，连续地址物理相邻）、链式存储结构（指针节点，任意物理地址）、索引存储、散列存储（哈希表） |
线性结构判定准则
必记易错陷阱
线性结构的充要特征：存在唯一的第一个元素（表头）；存在唯一的最后一个元素（表尾）；除第一个元素外每个元素有且仅有一个直接前驱；除最后一个元素外每个元素有且仅有一个直接后继。
随堂自测（3 题 · 共 140 道关联题）展开作答
数据的_________结构是数据的逻辑结构在计算机存储器上实现。
数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()。
关于数据的逻辑结构与存储结构之间的关系，下述说法中错误的是____。
A2-2.4.3
线性表的定义，线性表的顺序存储结构及其插入与删除运算。
顺序表（顺序存储）的插入与删除算法分析
必记插入操作
- 操作动作过程
- 在第 i（1 ≤ i ≤ n+1）个位置插入新元素，必须将第 i 到第 n 个元素全部向后移动 1 个位置
- 元素移动平均次数公式
- 在等概率情况下，平均移动元素次数为 n / 2
- 时间复杂度
- 最好 O(1)（表尾插入），最坏 O(n)，平均 O(n)
删除操作
- 操作动作过程
- 删除第 i（1 ≤ i ≤ n）个元素，必须将第 i+1 到第 n 个元素全部向前移动 1 个位置
- 元素移动平均次数公式
- 在等概率情况下，平均移动元素次数为 (n - 1) / 2
- 时间复杂度
- 最好 O(1)（表尾删除），最坏 O(n)，平均 O(n)
| 操作类型 | 操作动作过程 | 元素移动平均次数公式 | 时间复杂度 |
|---|---|---|---|
| 插入操作 | 在第 i（1 ≤ i ≤ n+1）个位置插入新元素，必须将第 i 到第 n 个元素全部向后移动 1 个位置 | 在等概率情况下，平均移动元素次数为 n / 2 | 最好 O(1)（表尾插入），最坏 O(n)，平均 O(n) |
| 删除操作 | 删除第 i（1 ≤ i ≤ n）个元素，必须将第 i+1 到第 n 个元素全部向前移动 1 个位置 | 在等概率情况下，平均移动元素次数为 (n - 1) / 2 | 最好 O(1)（表尾删除），最坏 O(n)，平均 O(n) |
顺序表随机存取特性
必记易错陷阱
顺序表最大的优点是支持随机存取（按数组下标可以在 O(1) 时间内直接定位任意第 i 个元素）；主要缺点是插入和删除需要移动大量数据元素，且需要预先分配固定大小的连续内存块。
随堂自测（3 题 · 共 94 道关联题）展开作答
在长度为n顺序存储的线性表中删除一元素，最坏情况下需要移动表中的()个元素。
_是最常用且最简单的一种数据结构，即一种逻辑结构，表示数据元素之间一对一的关系。
____是最常用且最简单的一种数据结构，它是一种逻辑结构，表示数据元素之间一对一的关系。
A2-2.4.4
栈和队列的定义，栈和队列的顺序存储结构及其基本运算。
栈（Stack） vs 队列（Queue）核心操作对比（专转本高频大题）
必记栈
- 英文名称
- Stack
- 操作规则原则
- 后进先出（LIFO，Last In First Out）
- 允许操作的一端
- 所有的插入（入栈 Push）和删除（出栈 Pop）操作只能在“栈顶（Top）”进行
- 经典应用场景
- 函数递归调用、括号匹配、表达式求值、浏览器后退历史
队列
- 英文名称
- Queue
- 操作规则原则
- 先进先出（FIFO，First In First Out）
- 允许操作的一端
- 只允许在“队尾（Rear）”插入（入队），在“队头（Front）”删除（出队）
- 经典应用场景
- 打印机任务排队缓冲、操作系统 CPU 进程就绪队列、广度优先搜索（BFS）
| 操作受限线性表 | 英文名称 | 操作规则原则 | 允许操作的一端 | 经典应用场景 |
|---|---|---|---|---|
| 栈 | Stack | 后进先出（LIFO，Last In First Out） | 所有的插入（入栈 Push）和删除（出栈 Pop）操作只能在“栈顶（Top）”进行 | 函数递归调用、括号匹配、表达式求值、浏览器后退历史 |
| 队列 | Queue | 先进先出（FIFO，First In First Out） | 只允许在“队尾（Rear）”插入（入队），在“队头（Front）”删除（出队） | 打印机任务排队缓冲、操作系统 CPU 进程就绪队列、广度优先搜索（BFS） |
循环队列假溢出与队满判定
必记易错陷阱
为解决顺序队列的“假溢出”问题，通常采用循环队列（利用求模运算取余 % MaxSize）。
常见牺牲一个存储单元以区分队空队满：
• 队空条件：front rear；
• 队满条件：(rear + 1) % MaxSize front；
• 队列中当前元素个数：(rear - front + MaxSize) % MaxSize。
随堂自测（3 题 · 共 157 道关联题）展开作答
设栈 S 的初始状态为空，若元素 a、b、c、d、e、f 依次进栈，得到的出栈序列是 a、c、f、e、d、b，则栈 S 的容量至少是 ____。
设栈 S 和队列 Q 的初始状态均为空，元素 a,b,c,d,e,f,g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b,d,c,f,e,a,g，则栈 S 的容量至少是 ____。
设输入序列为 1、2、3，则经过栈的作用后可以得到 ____ 种不同的输出序列。
A2-2.4.5
线性单链表、双向链表与循环链表的结构及其基本运算。
链表结构核心特性对比（单链表 / 循环链表 / 双向链表）
必记单链表
- 节点结构指针域
- 包含数据域
data+ 单个后继指针域next - 首尾闭合判定
- 尾节点的
next指针固定为NULL - 优缺点与操作特性
- 插入和删除已知节点指针时时间复杂度为 O(1)（只需修改指针，无需移动数据）；不支持随机访问，查表需从头 O(n) 遍历
循环单链表
- 节点结构指针域
- 结构同单链表
- 首尾闭合判定
- 尾节点的
next指向头节点，形成环状闭合回路 - 优缺点与操作特性
- 从表中任意一个节点出发均能遍历访问到整张链表的所有元素
双向链表
- 节点结构指针域
- 包含数据域
data+ 前驱指针prior+ 后继指针next - 首尾闭合判定
- 双向互通
- 优缺点与操作特性
- 支持直接向前向后双向检索遍历，但每个节点需额外存储一个指针空间
| 链表结构类型 | 节点结构指针域 | 首尾闭合判定 | 优缺点与操作特性 |
|---|---|---|---|
| 单链表 | 包含数据域 data + 单个后继指针域 next | 尾节点的 next 指针固定为 NULL | 插入和删除已知节点指针时时间复杂度为 O(1)（只需修改指针，无需移动数据）；不支持随机访问，查表需从头 O(n) 遍历 |
| 循环单链表 | 结构同单链表 | 尾节点的 next 指向头节点，形成环状闭合回路 | 从表中任意一个节点出发均能遍历访问到整张链表的所有元素 |
| 双向链表 | 包含数据域 data + 前驱指针 prior + 后继指针 next | 双向互通 | 支持直接向前向后双向检索遍历，但每个节点需额外存储一个指针空间 |
单链表中头节点（Head Node）的作用
必记易错陷阱
在单链表第一个有效数据节点之前增设一个头节点的好处：使在链表第一个位置（表头）的插入和删除操作与在其他位置的操作统一，无需做特殊判断分支；空表与非空表处理逻辑一致
随堂自测（3 题 · 共 56 道关联题）展开作答
线性表若采用链式存储结构时，要求内存中可用存储单元的地址()。
线性表采用链式存储结构时，要求内存中可用存储单元的地址（）
线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。
A2-2.4.6
树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历。
二叉树四大核心数学性质（专转本每年必考计算题）
必记| 性质序号 | 性质内容公式 | 应用推导与经典结论 |
|---|---|---|
| 性质 1 | 在二叉树的第 i 层上，至多有 2^(i-1) 个节点（i ≥ 1） | 第 1 层至多 1 个，第 2 层至多 2 个，第 3 层至多 4 个 |
| 性质 2 | 深度为 k 的二叉树，至多有 2^k - 1 个节点（k ≥ 1） | 深度为 3 的二叉树至多 7 个节点，深度为 4 至多 15 个节点 |
| 性质 3（最核心公式） | ==在任意一棵二叉树中，若叶子节点数（度为0）为 n0，度为 2 的节点数为 n2，则必有：n0 = n2 + 1== | 【例】：若某二叉树中度为 2 的节点有 10 个，则其叶子节点数必为 11 个 |
| 性质 4 | 具有 n 个节点的完全二叉树的深度为 ⌊log2 n⌋ + 1 | 衡量完全二叉树的高度 |
二叉树三大遍历次序规则与算例
必记| 遍历方式 | 遍历访问顺序规则 | 根节点的访问位置 |
|---|---|---|
| 前序遍历（先序，Pre-order） | 根节点 -> 左子树 -> 右子树（根左右） | 最先访问根节点 |
| 中序遍历（In-order） | 左子树 -> 根节点 -> 右子树（左根右） | 中间访问根节点 |
| 后序遍历（Post-order） | 左子树 -> 右子树 -> 根节点（左右根） | 最后访问根节点 |
根据遍历序列还原二叉树规律
必记易错陷阱
专转本必考题型：给出中序遍历 + 前序遍历（或后序遍历），可以唯一确定一棵二叉树；【方法】：从前序的最前（或后序的最后）找出根节点，然后在中序遍历序列中以此根为中心，左边全属于左子树，右边全属于右子树，递归还原。 注意：单独给出“前序 + 后序”无法唯一确定一棵二叉树！
随堂自测（3 题 · 共 130 道关联题）展开作答
设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为____。
在一棵二叉树上第8层的结点数最多为____。
若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则二叉树的总的结点个数为 ____。