用于哈希表查询的哈希函数应具备什么性质？

必须具有确定性，并能良好分散预期的键。定长键的哈希计算可以为 O(1)；新出现的 L 字符字符串通常需要 O(L)。

循环数组队列如何避免出队后移动元素？

队首和队尾下标对容量取模后循环推进。出队只推进队首下标，因此无需移动其他元素即可复用空闲位置。

键互不相同时，二叉搜索树（BST）的排序不变量是什么？

对每个节点，左子树所有键都较小，右子树所有键都较大。该规则递归成立。

动态数组每次将容量翻倍时，尾部追加的均摊代价是多少？

每次 O(1)。一次扩容可能需要 O(n)，但从空数组开始追加 n 次的总代价为 O(n)。

采用分离链接法的哈希表，操作的期望代价与最坏代价是多少？

在负载有界、哈希分布良好且键操作代价为常数时，查询和删除的期望代价为 O(1)。按几何倍数扩容时，插入的期望均摊代价为 O(1)。n 个冲突键形成的链可能使操作达到 O(n)。

比较单链表与动态数组的头部插入和按下标访问代价。

链表：头部插入 O(1)，按下标访问 O(n)。数组：头部插入 O(n)，按下标访问 O(1)；头部插入需要移动元素。

栈如何工作，其操作何时为 O(1)？

后进先出（LIFO）：最后压入的元素最先弹出。在链表头部实现时，压栈、出栈和读取栈顶均为 O(1)；数组扩容可能使一次压栈达到 O(n)。

使用路径压缩和按秩合并时，union/find 的均摊代价是多少？

每次 O(α(n))，α 是反阿克曼函数，n 为元素数。初始化为 O(n)；该界针对操作序列，并非每次调用的最坏代价都是常数。

长度为 n、下标从零开始的堆数组中，节点 i 的父节点和孩子在哪里？

父节点：i>0 时为 ⌊(i−1)/2⌋。孩子：2i+1 和 2i+2，但必须小于 n。下标 0 没有父节点。

BST 的查询、插入和删除如何取决于树高 h？

都需要 O(h)。平衡树的 h = O(log n)，链状树的 h = O(n)。期望 O(log n) 需要随机插入顺序等假设。

不相交集合结构中的 find 和 union 分别做什么？

find(x) 返回 x 所属集合的代表。union(x,y) 在两个集合不同时合并它们；若已经属于同一集合，划分不变。

路径压缩、按秩合并和按大小合并有何区别？

路径压缩将访问过的节点重新指向根。按秩合并把低秩根接到高秩根下；按大小合并把较小集合接到较大集合下。秩不一定等于当前树高。

从 n 个元素自底向上建堆的代价是多少？

O(n)。大多数节点靠近叶子，只需少量下沉；按节点高度累加工作量可得到线性总量。

二叉堆的插入、删除根和读取根各需要多少时间？

不需要调整数组容量时，分别为 O(log n)、O(log n) 和 O(1)。调整容量可能需要 O(n)。

什么是哈希表的负载因子，为什么可能扩容？

α = n/m，其中 n 为条目数，m 为桶数或槽位数。超过实现规定的阈值可能触发扩容和重新散列；0.75 并非通用阈值。

开放寻址中的线性探测与二次探测有何区别？

条目都保存在数组中。表长为 m、初始下标为 h 时，分别探测 (h+i) mod m 和 (h+c₁i+c₂i²) mod m。二次探测需要合适的参数。

当 n → ∞ 时，将以下增长率从慢到快排序：n!、n、1、n²、log n、2ⁿ、n log n。

渐近顺序为：1 < log n < n < n log n < n² < 2ⁿ < n!。

对于非负函数 f 和 g，f(n) ∈ O(g(n)) 表示什么？

存在常数 c > 0 和 n₀ ≥ 0，使所有 n ≥ n₀ 都满足 f(n) ≤ c·g(n)。

二叉最小堆的两个定义性质是什么？

它是完全二叉树，每个父节点的键都不大于其孩子的键。因此根保存一个最小值。

二叉树的前序、中序和后序遍历分别按什么顺序访问？

前序：节点 → 左 → 右。中序：左 → 节点 → 右。后序：左 → 右 → 节点。

哪些颜色规则使红黑 BST 保持平衡？

节点为红或黑；根和 NIL 叶节点为黑。红节点不能有红孩子。从任一节点到其后代 NIL 叶节点的每条路径都含相同数量的黑节点。这些规则将树高限制为 O(log n)。

O、Ω 和 Θ 有何区别？

分别表示渐近上界、下界和紧确界。它们描述指定的代价函数；O 本身并不表示最坏情况。

层序遍历如何访问二叉树？

使用 FIFO 队列逐个深度层访问。每个节点的左孩子先于右孩子入队，可得到从左到右的顺序。

只允许插入的布隆过滤器能给出哪些答案？

阴性结果表示该元素未插入过；阳性结果表示可能插入过。哈希值在位数组中置位，因此可能出现假阳性，但状态完好时不会出现假阴性。

AVL 树的平衡条件是什么？

每个节点都满足高度(左) − 高度(右) ∈ {−1, 0, 1}，同时遵守 BST 的排序不变量。

如何修复 AVL 插入导致的左右型失衡？

先对左孩子左旋，再对失衡节点右旋。

双向链表为什么能在 O(1) 时间内删除给定节点？

前驱和后继指针可直接重新连接相邻节点。必要时更新头尾指针，无需搜索前驱。

为什么定长数组按下标访问的时间为 O(1)？

等长存储单元连续排列，因此地址(i) = 基址 + i·单元大小。这里假设地址运算耗时为常数。

分离链接法如何解决哈希冲突？

每个桶保存映射到该桶下标的条目集合，通常使用链表。落在同一桶中的不同键仍是独立条目。

对键互不相同的 BST 进行中序遍历会得到什么？

按严格递增顺序得到所有键；访问 n 个节点需要 O(n) 时间。

队列的访问规则及典型操作代价是什么？

先进先出（FIFO）：队尾入队、队首出队。使用头尾指针或固定容量的循环缓冲区时，两者均为 O(1)；若移动数组元素，出队会是 O(n)。

什么是 trie，查找 L 字符的键何时为 O(L)？

前缀树沿字符路径存储键，并用标记表示完整键。若每次转向下一个字符都为 O(1)，查找就是 O(L)。

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

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

Level: basic
Languages: zh → zh
Cards: 32
Markdown: 数据结构、复杂度分析（Big-O）与核心算法 (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
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)。