# 数据结构、复杂度分析（Big-O）与核心算法

> 适合具备基础编程知识者进行本科层次复习：32张卡片涵盖数组、链表、哈希、树、堆、前缀树、并查集、布隆过滤器与复杂度。

- **Canonical URL:** https://flashcards.world/flashcards/sets/b6dfbb4a-8611-400b-abb1-e03d2a0061aa/
- **Markdown URL:** https://flashcards.world/flashcards/sets/b6dfbb4a-8611-400b-abb1-e03d2a0061aa.md
- **Level:** basic
- **Languages:** zh → zh
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | 用于哈希表查询的哈希函数应具备什么性质？ | 必须具有确定性，并能良好分散预期的键。定长键的哈希计算可以为 O(1)；新出现的 L 字符字符串通常需要 O(L)。 |  |  |
| 2 | 循环数组队列如何避免出队后移动元素？ | 队首和队尾下标对容量取模后循环推进。出队只推进队首下标，因此无需移动其他元素即可复用空闲位置。 |  |  |
| 3 | 键互不相同时，二叉搜索树（BST）的排序不变量是什么？ | 对每个节点，左子树所有键都较小，右子树所有键都较大。该规则递归成立。 |  |  |
| 4 | 动态数组每次将容量翻倍时，尾部追加的均摊代价是多少？ | 每次 O(1)。一次扩容可能需要 O(n)，但从空数组开始追加 n 次的总代价为 O(n)。 |  |  |
| 5 | 采用分离链接法的哈希表，操作的期望代价与最坏代价是多少？ | 在负载有界、哈希分布良好且键操作代价为常数时，查询和删除的期望代价为 O(1)。按几何倍数扩容时，插入的期望均摊代价为 O(1)。n 个冲突键形成的链可能使操作达到 O(n)。 |  |  |
| 6 | 比较单链表与动态数组的头部插入和按下标访问代价。 | 链表：头部插入 O(1)，按下标访问 O(n)。数组：头部插入 O(n)，按下标访问 O(1)；头部插入需要移动元素。 |  |  |
| 7 | 栈如何工作，其操作何时为 O(1)？ | 后进先出（LIFO）：最后压入的元素最先弹出。在链表头部实现时，压栈、出栈和读取栈顶均为 O(1)；数组扩容可能使一次压栈达到 O(n)。 |  |  |
| 8 | 使用路径压缩和按秩合并时，union/find 的均摊代价是多少？ | 每次 O(α(n))，α 是反阿克曼函数，n 为元素数。初始化为 O(n)；该界针对操作序列，并非每次调用的最坏代价都是常数。 |  |  |
| 9 | 长度为 n、下标从零开始的堆数组中，节点 i 的父节点和孩子在哪里？ | 父节点：i>0 时为 ⌊(i−1)/2⌋。孩子：2i+1 和 2i+2，但必须小于 n。下标 0 没有父节点。 |  |  |
| 10 | BST 的查询、插入和删除如何取决于树高 h？ | 都需要 O(h)。平衡树的 h = O(log n)，链状树的 h = O(n)。期望 O(log n) 需要随机插入顺序等假设。 |  |  |
| 11 | 不相交集合结构中的 find 和 union 分别做什么？ | find(x) 返回 x 所属集合的代表。union(x,y) 在两个集合不同时合并它们；若已经属于同一集合，划分不变。 |  |  |
| 12 | 路径压缩、按秩合并和按大小合并有何区别？ | 路径压缩将访问过的节点重新指向根。按秩合并把低秩根接到高秩根下；按大小合并把较小集合接到较大集合下。秩不一定等于当前树高。 |  |  |
| 13 | 从 n 个元素自底向上建堆的代价是多少？ | O(n)。大多数节点靠近叶子，只需少量下沉；按节点高度累加工作量可得到线性总量。 |  |  |
| 14 | 二叉堆的插入、删除根和读取根各需要多少时间？ | 不需要调整数组容量时，分别为 O(log n)、O(log n) 和 O(1)。调整容量可能需要 O(n)。 |  |  |
| 15 | 什么是哈希表的负载因子，为什么可能扩容？ | α = n/m，其中 n 为条目数，m 为桶数或槽位数。超过实现规定的阈值可能触发扩容和重新散列；0.75 并非通用阈值。 |  |  |
| 16 | 开放寻址中的线性探测与二次探测有何区别？ | 条目都保存在数组中。表长为 m、初始下标为 h 时，分别探测 (h+i) mod m 和 (h+c₁i+c₂i²) mod m。二次探测需要合适的参数。 |  |  |
| 17 | 当 n → ∞ 时，将以下增长率从慢到快排序：n!、n、1、n²、log n、2ⁿ、n log n。 | 渐近顺序为：1 < log n < n < n log n < n² < 2ⁿ < n!。 |  |  |
| 18 | 对于非负函数 f 和 g，f(n) ∈ O(g(n)) 表示什么？ | 存在常数 c > 0 和 n₀ ≥ 0，使所有 n ≥ n₀ 都满足 f(n) ≤ c·g(n)。 |  |  |
| 19 | 二叉最小堆的两个定义性质是什么？ | 它是完全二叉树，每个父节点的键都不大于其孩子的键。因此根保存一个最小值。 |  |  |
| 20 | 二叉树的前序、中序和后序遍历分别按什么顺序访问？ | 前序：节点 → 左 → 右。中序：左 → 节点 → 右。后序：左 → 右 → 节点。 |  |  |
| 21 | 哪些颜色规则使红黑 BST 保持平衡？ | 节点为红或黑；根和 NIL 叶节点为黑。红节点不能有红孩子。从任一节点到其后代 NIL 叶节点的每条路径都含相同数量的黑节点。这些规则将树高限制为 O(log n)。 |  |  |
| 22 | O、Ω 和 Θ 有何区别？ | 分别表示渐近上界、下界和紧确界。它们描述指定的代价函数；O 本身并不表示最坏情况。 |  |  |
| 23 | 层序遍历如何访问二叉树？ | 使用 FIFO 队列逐个深度层访问。每个节点的左孩子先于右孩子入队，可得到从左到右的顺序。 |  |  |
| 24 | 只允许插入的布隆过滤器能给出哪些答案？ | 阴性结果表示该元素未插入过；阳性结果表示可能插入过。哈希值在位数组中置位，因此可能出现假阳性，但状态完好时不会出现假阴性。 |  |  |
| 25 | AVL 树的平衡条件是什么？ | 每个节点都满足高度(左) − 高度(右) ∈ {−1, 0, 1}，同时遵守 BST 的排序不变量。 |  |  |
| 26 | 如何修复 AVL 插入导致的左右型失衡？ | 先对左孩子左旋，再对失衡节点右旋。 |  |  |
| 27 | 双向链表为什么能在 O(1) 时间内删除给定节点？ | 前驱和后继指针可直接重新连接相邻节点。必要时更新头尾指针，无需搜索前驱。 |  |  |
| 28 | 为什么定长数组按下标访问的时间为 O(1)？ | 等长存储单元连续排列，因此地址(i) = 基址 + i·单元大小。这里假设地址运算耗时为常数。 |  |  |
| 29 | 分离链接法如何解决哈希冲突？ | 每个桶保存映射到该桶下标的条目集合，通常使用链表。落在同一桶中的不同键仍是独立条目。 |  |  |
| 30 | 对键互不相同的 BST 进行中序遍历会得到什么？ | 按严格递增顺序得到所有键；访问 n 个节点需要 O(n) 时间。 |  |  |
| 31 | 队列的访问规则及典型操作代价是什么？ | 先进先出（FIFO）：队尾入队、队首出队。使用头尾指针或固定容量的循环缓冲区时，两者均为 O(1)；若移动数组元素，出队会是 O(n)。 |  |  |
| 32 | 什么是 trie，查找 L 字符的键何时为 O(L)？ | 前缀树沿字符路径存储键，并用标记表示完整键。若每次转向下一个字符都为 O(1)，查找就是 O(L)。 |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/b6dfbb4a-8611-400b-abb1-e03d2a0061aa/).