绪论与算法分析
数据结构 = 逻辑结构 + 存储结构 + 运算；算法分析衡量时间与空间代价。
基本概念
- 数据元素、数据项、数据对象
- 逻辑结构：集合、线性、树形、图状
- 存储结构：顺序存储、链式存储、索引存储、散列存储
- 运算：插入、删除、修改、查找、排序、遍历
算法与复杂度
- 算法特性：有穷性、确定性、可行性、输入、输出
- 时间复杂度：基本语句执行次数的数量级
- 空间复杂度：除输入外的辅助空间
- 常见阶：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)
【选择题】下列时间复杂度数量级最高的是？A. O(nlogn) B. O(n²) C. O(2ⁿ) D. O(logn)
答案：C。指数阶增长最快：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)。
【选择题】算法的时间复杂度与什么因素直接相关？
答案：问题的规模 n。时间复杂度是输入规模 n 的函数，衡量基本操作执行次数随 n 的增长阶。
【概念题】简述数据的逻辑结构与存储结构的关系。
答案：逻辑结构是数据元素间的抽象关系（独立于计算机）；存储结构是逻辑结构在计算机中的表示（物理实现），同一逻辑结构可有多种存储结构。
线性表
顺序表随机访问、链表灵活插入删除；两者是后续结构的基础。
顺序表
- 用一组地址连续的存储单元存储，随机存取 O(1)
- 插入/删除平均移动 n/2 个元素，时间 O(n)
- 容量固定，可动态扩容（倍增分配）
- 适用：频繁查找、元素个数稳定
单链表
- 每个结点含数据域 + 指针域，头指针/头结点
- 查找需从头遍历 O(n)；已知前驱时插入/删除 O(1)
- 头插法/尾插法建立链表
- 适用：频繁插入删除、长度动态变化
双链表与循环链表
- 双链表：前驱指针 + 后继指针，双向遍历
- 循环链表：尾结点指向头结点，可从任一结点遍历全表
- 静态链表：数组模拟指针（游标），适用于无指针语言
- 循环双链表判空：head->next == head
【选择题】在长度为 n 的顺序表中删除第 i 个元素，平均移动元素个数为？
答案：(n−1)/2（约 n/2）。删除需将后续元素前移，各位置等概率时平均移动 (n−1)/2 个。
【选择题】顺序表与单链表相比，最大的优势是？
答案：随机存取。顺序表按下标 O(1) 访问任意元素；链表必须从头遍历。
【概念题】单链表带头结点有什么好处？
答案：头结点使空表和非空表的处理统一，插入/删除首结点时无需单独修改头指针。
栈、队列与数组
栈后进先出、队列先进先出；数组是线性表的多维推广。
栈 Stack
- LIFO：只允许在栈顶插入/删除
- 顺序栈与链栈；栈空/栈满判定
- 应用：函数调用、括号匹配、表达式求值、递归
- 入栈序列 abc 的出栈序列数：卡特兰数
队列 Queue
- FIFO：队尾入队、队头出队
- 循环队列：front 指向队头、rear 指向队尾下一个位置
- 判满：(rear+1)%MaxSize == front；判空：front == rear
- 应用：层次遍历、广度优先搜索、缓冲
数组与矩阵压缩
- 一维/多维数组按行优先或列优先存储
- 地址计算：Loc(a[i][j]) 由基地址 + 偏移
- 对称矩阵压缩存储下三角约 n(n+1)/2 个元素
- 稀疏矩阵：三元组表、十字链表存储
【选择题】循环队列中 front=3、rear=5、MaxSize=6，则队列中元素个数为？
答案：2。元素个数 = (rear − front + MaxSize) % MaxSize = (5−3+6)%6 = 2。
【选择题】栈和队列的共同点是？
答案：都只允许在端点处插入和删除元素。栈限制栈顶、队列限制队尾入队头出，是操作受限的线性表。
【概念题】递归函数执行时依靠什么数据结构保存现场？
答案：栈。系统调用栈保存每层递归的参数、局部变量与返回地址，先进后出。
串与模式匹配
串是字符组成的线性表；模式匹配是串的核心算法。
串的基本概念
- 子串、主串、前缀、后缀；串长
- 存储：定长顺序存储、堆分配存储、块链存储
- 串的模式匹配：在主串中找子串（模式串）首次出现位置
朴素匹配 vs KMP
- 朴素匹配：逐个字符比较，失败回溯主串 i，最坏 O(n×m)
- KMP 算法：利用 next 数组避免主串指针回溯
- next[j]：模式串前 j−1 个字符的最长相等前后缀长度 + 1（约定 next[1]=0）
- KMP 时间复杂度 O(n+m)
【概念题】KMP 算法相比朴素匹配算法的核心改进是什么？
答案：主串指针不回溯。利用 next 数组让模式串跳跃式移动，避免重复比较，平均/最坏时间 O(n+m)。
【选择题】串 'abab' 的长度为？
答案：4。串长即字符个数。
【概念题】next[1] 的约定值是多少？
答案：0（按 1 起始编号约定）。第一个字符失配时模式串整体后移一位。
树与二叉树
二叉树遍历、线索化、哈夫曼树、BST 与 AVL——树是 408 的大户。
二叉树基础
- 性质：n₀ = n₂ + 1（叶子 = 度为 2 结点 + 1）
- 第 k 层最多 2^(k−1) 个结点；深度 h 最多 2^h − 1
- 完全二叉树：叶子只出现在最后两层，最底层靠左
- 顺序存储（数组下标关系）与链式存储
遍历与线索化
- 先序：根左右；中序：左根右；后序：左右根；层次
- 已知先序+中序 或 后序+中序可唯一确定二叉树
- 线索二叉树：利用空指针指向前驱/后继，lTag/rTag 标记
- 遍历序列的栈实现与递归对应
哈夫曼树与编码
- 哈夫曼树：带权路径长度 WPL 最小的二叉树
- 构造：每次取两个最小权值结点合并
- 哈夫曼编码：前缀编码，压缩数据
- n 个叶子结点的哈夫曼树共有 2n−1 个结点
BST 与 AVL
- 二叉排序树 BST：左小右大，中序遍历有序
- BST 查找：平均 O(logn)，最坏（单支树）O(n)
- 平衡二叉树 AVL：左右子树高度差 ≤ 1
- AVL 插入需 LL/RR/LR/RL 四种旋转调整
【选择题】对任意二叉树，若叶子结点数为 n₀，度为 2 的结点数为 n₂，则成立的关系是？
答案：n₀ = n₂ + 1。由分支计数：结点总数 = 边数 + 1 = n₁ + 2n₂ + 1，联立消去 n₁ 即得。
【选择题】一棵完全二叉树有 100 个结点，其叶子结点数为？
答案：50。完全二叉树度为 1 的结点最多 1 个；n=n₀+n₁+n₂ 且 n₀=n₂+1 → 100=2n₀−1+n₁，n₁=1（100 为偶数）→ n₀=50。
【概念题】n 个叶子结点的哈夫曼树共有多少个结点？
答案：2n−1。哈夫曼树只有度为 0 和 2 的结点，n₀+n₂ = n+(n−1) = 2n−1。
图
存储、遍历、最小生成树、最短路径、拓扑排序与关键路径。
存储与遍历
- 邻接矩阵：n×n，O(n²) 空间，稠密图适用
- 邻接表：顶点表 + 边表，O(n+e)，稀疏图适用
- DFS（深度优先，栈/递归）、BFS（广度优先，队列）
- 遍历可判断连通性；生成树/生成森林
最小生成树 MST
- Prim 算法：从顶点出发扩展，O(n²)，适合稠密图
- Kruskal 算法：按边权从小到大并入，O(eloge)，适合稀疏图
- MST 不唯一，但权值和唯一（边权互异时唯一）
最短路径
- Dijkstra：单源，非负权，O(n²)
- Floyd：所有顶点对，动态规划，O(n³)
- BFS 可求无权图最短路径
- 负权边：Dijkstra 失效，用 Bellman-Ford
拓扑排序与关键路径
- 拓扑排序：DAG 才有；每次删入度为 0 的顶点
- 拓扑序列不唯一；有环则无拓扑序列
- 关键路径：AOE 网中从源点到汇点的最长路径
- 关键活动：最早开始 = 最迟开始；缩短关键活动可缩短工期
【选择题】Prim 算法适合求解什么类型图的最小生成树？
答案：稠密图。Prim 时间复杂度 O(n²) 与边数无关，稠密图（边多）优势明显；Kruskal O(eloge) 适合稀疏图。
【概念题】一个有向图存在拓扑序列的充要条件是什么？
答案：该图为有向无环图（DAG）。存在环则环上顶点永远有入度，无法全部删除。
【选择题】Dijkstra 算法不能用于带什么边的图？
答案：负权边。负权会破坏「已确定最短路径」的贪心前提，需用 Bellman-Ford 等算法。
查找
从顺序查找到哈希表，核心指标是平均查找长度 ASL。
线性查找与二分
- 顺序查找：ASL = (n+1)/2，O(n)
- 折半查找：有序表，ASL = log₂(n+1) − 1，O(logn)
- 折半查找判定树：平衡二叉排序树，比较次数 = 结点深度
- 分块查找：索引顺序表，ASL = 索引查找 + 块内顺序查找
树形查找
- B 树：多路平衡查找树，m 阶；根至少 2 个孩子、非叶至少 ⌈m/2⌉ 个孩子
- B+ 树：叶子结点链成链表，适合数据库索引/文件系统
- 红黑树：自平衡 BST，插入删除 O(logn)（408 了解层次）
散列表 Hash
- 散列函数：除留余数法 H(key)=key%p（p 取不大于表长 m 的最大素数）
- 冲突解决：开放定址法（线性探测、平方探测、再散列）
- 冲突解决：链地址法（拉链法）
- 装填因子 α = 表中记录数/表长；ASL 与 α 有关
- 查找成功/失败 ASL 计算是常考点
【选择题】长度为 n 的有序表采用折半查找，其时间复杂度为？
答案：O(log₂n)。每趟比较将区间减半，最多比较 ⌈log₂(n+1)⌉ 次。
【选择题】除留余数法选 p 的常用原则是？
答案：p 取不大于散列表表长的最大素数。减少地址聚集，分布更均匀。
【概念题】链地址法解决冲突的基本思想是什么？
答案：把所有散列地址相同的记录链在同一个单链表中，表头存于散列表对应单元。
排序
九大排序的时间、空间、稳定性——综合大题的弹药库。
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 特点 |
|---|---|---|---|---|---|
| 直接插入 | O(n²) | O(n²) | O(1) | 稳定 | 基本有序时快 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 | 增量递减分组插入 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 相邻交换 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | 不稳定 | 基准划分，最坏基本有序 |
| 简单选择 | O(n²) | O(n²) | O(1) | 不稳定 | 每趟选最小 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 建堆+调整 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 | 二路归并 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 | 按位分配收集 |
【选择题】下列排序算法中，平均时间复杂度为 O(nlogn) 的是？A. 冒泡 B. 直接插入 C. 快速排序 D. 简单选择
答案：C。快速排序平均 O(nlogn)；冒泡、插入、选择平均均为 O(n²)。
【选择题】下列排序算法中，属于稳定排序的是？
答案：直接插入、冒泡、归并、基数。希尔、快排、简单选择、堆排序不稳定。
【选择题】快速排序在什么情况下最坏时间复杂度为 O(n²)？
答案：序列基本有序或每次划分极不平衡时。此时每次只减少一个元素，递归深度 n，比较 O(n²)。