二分查找需要什么条件？何时能在 O(log n) 时间内完成？

它在按比较次序排好的数据中反复将查找区间减半。若数组支持 O(1) 下标访问且每次比较耗时为常数，则查找 n 个元素需要 O(log n) 时间。

两阶段锁定（2PL）的两个阶段是什么？

增长阶段：获取锁而不释放锁。收缩阶段：释放锁而不获取新锁。使用合适的冲突读写锁时，2PL 保证调度具有冲突可串行化性，但仍可能发生死锁。

B+ 树为什么适合数据库索引和范围查询？

较大的扇出使树较矮，减少页面访问。有序键和相连的叶节点支持范围扫描。哈希索引针对等值查找，本身不提供同样的有序范围访问。

记忆化与自底向上的动态规划有什么区别？

记忆化按需计算子问题，通常使用递归并缓存结果。自底向上的动态规划按依赖项已经求出的次序计算状态，通常通过填表实现。

SQL SELECT 查询的简化逻辑处理顺序是什么？

对于不含 CTE、窗口函数或集合运算的查询：FROM/JOIN → WHERE → GROUP BY 与聚合 → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET。这是逻辑模型，不一定是优化器实际执行的物理顺序。

什么是幻读？如何防止它？

另一个事务提交更改后，重复谓词查询会得到不同的匹配行集合。标准模型中的 SERIALIZABLE 防止幻读；包括 PostgreSQL REPEATABLE READ 在内的一些实现也会在较低级别防止幻读。

什么是脏读？哪个标准隔离级别最先禁止它？

读取另一个事务尚未提交的数据，无论该事务之后是否回滚。READ COMMITTED 及更强的标准隔离级别禁止脏读。

标准数组归并排序如何工作？时间和空间界是多少？

它递归排序两个半区，再在线性时间内合并。在比较耗时为常数的假设下，标准版本需要 Θ(n log n) 时间和 O(n) 辅助空间。

深度优先搜索如何检测有向图中的环？

DFS 用递归或显式栈向深处探索。指向当前 DFS 路径上仍处于活动状态的顶点的边是回边，证明存在有向环；仅仅指向任意已访问顶点并不足以证明有环。

计数排序或基数排序何时能达到线性时间？

计数排序对取值范围含 k 个值的 n 个键需 O(n+k)。基数排序若进行 d 次稳定的数位排序、基数为 b，则需 O(d(n+b))。只有这些参数允许时才是线性时间；它们利用了比较之外的键结构。

PostgreSQL 中的主键与外键有何区别？

主键以唯一、非 NULL 的值标识行。外键要求其值匹配被引用的键值，但受相应 NULL 规则约束。它可以引用同表或另一表中符合条件的 UNIQUE 键或主键。

原地堆排序的最坏时间和额外空间界是多少？

建堆需要 O(n)，随后所有取出操作合计需要 O(n log n)。若在输入数组中采用迭代下沉，堆排序最坏耗时 O(n log n)，额外空间为 O(1)。

什么是拓扑序？卡恩算法如何求得拓扑序？

在有向无环图中，每条边 u→v 都要求 u 排在 v 前面。反复输出入度为零的顶点并删除其出边，将新出现的零入度顶点入队。若输出顶点数少于 V，则有向图含环。

插入排序如何工作？近乎有序输入的耗时取决于什么？

它逐个把元素插入已排序的前缀。通常采用相邻移位或交换的版本需要 Θ(n+I) 时间，其中 I 为逆序对数量。I=O(n) 时为线性时间；输入规模小本身并不改变最坏 Θ(n²) 的界。

SQL Server 中的聚集与非聚集行存储索引有何区别？

聚集索引按键序存储表行，所以每张表最多有一个。非聚集索引具有自己的键和行定位符，也可包含其他列。这些术语和存储细节因数据库系统而异。

快速排序为什么可能耗时 Θ(n²)？随机化有何帮助？

反复出现高度不均衡的划分，例如每次都选不同键中的最小键作为枢轴，会导致二次工作量。当键互异或正确处理重复键时，随机选择枢轴可使期望耗时为 O(n log n)。三数取中是一种实用启发式方法，不保证最坏情况的界。

贪心算法与动态规划有何区别？

贪心算法直接采用局部选择，需要证明这些选择能保留一个最优解。动态规划通过递推比较方案并复用子问题结果。全局最优需要正确的模型和递推关系，不能仅凭“动态规划”这一名称保证。

迪杰斯特拉算法何时有效？常见的堆实现复杂度是多少？

边权非负时，它反复确定暂定距离最小的顶点。邻接表配合二叉最小堆的实现耗时 O((V+E) log V)。负权边可能使已确定距离的正确性论证失效。

在正常同步提交下，PostgreSQL 的 WAL 如何支持持久性？

相关日志记录在确认提交之前、也在写入已更改的数据页之前到达持久存储。崩溃后，WAL 可重放数据页尚未包含的更改。异步提交可能丢失最近已确认的事务。

最长公共子序列长度的动态规划递推式是什么？

令 L[i,j] 为长度分别为 i,j 的前缀的最长公共子序列长度。设 L[0,j]=L[i,0]=0。末字符相同则 L[i,j]=1+L[i−1,j−1]；否则 L[i,j]=max(L[i−1,j],L[i,j−1])。完整表需要 O(mn) 时间和空间。

贝尔曼–福特算法如何处理负权边并检测可达负环？

对所有边最多进行 V−1 轮松弛。若再从可达顶点松弛仍能改进距离，就说明存在从源点可达的负环。最坏耗时 O(VE)；从此负环可达的顶点没有有限的最短路径代价。

整数容量 W 的标准 0/1 背包递推式是什么？

令 D[i,w] 表示用前 i 件物品、容量为 w 时的最大价值，重量 wᵢ 为正整数。设 D[0,w]=0。若 wᵢ>w，则取 D[i−1,w]；否则取 max(D[i−1,w],vᵢ+D[i−1,w−wᵢ])。O(NW) 时间是伪多项式时间。

广度优先搜索如何在无权图中找到最短路径？

BFS 使用先进先出队列，按边数距离逐层探索顶点。在顶点入队时标记可避免重复访问。首次发现到达某个可达顶点的路径具有最少的边数。

分组查询中的 WHERE 和 HAVING 有何不同？

WHERE 在分组之前筛选输入行。HAVING 筛选产生的分组，可使用 COUNT(*)>1 等聚合条件。

什么使排序算法具有稳定性？

键相同的元素保持原来的相对次序。归并排序在相等时先取左侧元素即可实现稳定；标准原地快速排序通常不稳定。稳定性取决于具体实现。

邻接矩阵与普通邻接表如何比较？

对 V 个顶点、E 条边，矩阵需 O(V²) 空间，判断一条边是否存在需 O(1)。邻接表需 O(V+E) 空间；在未排序的表中查找边 (u,v) 需 O(deg(u))，其中 deg(u) 是该表长度。

事务的 ACID 属性各是什么意思？

原子性：效果要么全部发生，要么全部不发生。一致性：正确事务保持约束和应用不变量。隔离性：并发行为遵守所选隔离级别。持久性：已提交效果在数据库配置保证所涵盖的故障后仍然存在。

什么是不可重复读？哪个标准隔离级别可防止它？

另一个事务提交更新或删除后，再读同一行得到不同数据，或发现该行消失。REPEATABLE READ 和 SERIALIZABLE 禁止这种异常。

动态规划为何适用于许多优化问题？

最优子结构允许用子问题的最优解表达整体最优解。当子问题重叠时，存储结果可避免重复计算。状态定义和递推关系必须正确表达原问题。

INNER JOIN 和 LEFT JOIN 有何区别？

INNER JOIN 返回满足连接条件的行组合。LEFT JOIN 还保留每个未匹配的左表行，并在右表列中填入 NULL。若右表有多个匹配行，一个左表行可能产生多个输出行。

第一、第二和第三范式分别要求什么？

1NF：属性值具有原子性。2NF：满足 1NF，且任何非主属性都不依赖于任一候选键的真子集。3NF：满足 1NF，且每个非平凡依赖 X→A 中，X 为超键或 A 为主属性。主属性属于至少一个候选键。

克鲁斯卡尔和普里姆算法如何构造最小生成树？

对于连通无向加权图，克鲁斯卡尔按边权递增考察边，用并查集拒绝产生环的边。普里姆从一棵树开始，每次选择连接树内与树外顶点的最小权边来扩展。

算法、图、动态规划与关系数据库

32 张本科复习卡片，涵盖排序、图算法、动态规划、SQL、索引和事务。需要具备基础编程、数据结构和 SQL 知识。

Level: basic
Languages: zh → zh
Cards: 32
Markdown: 算法、图、动态规划与关系数据库 (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	二分查找需要什么条件？何时能在 O(log n) 时间内完成？	它在按比较次序排好的数据中反复将查找区间减半。若数组支持 O(1) 下标访问且每次比较耗时为常数，则查找 n 个元素需要 O(log n) 时间。
2	两阶段锁定（2PL）的两个阶段是什么？	增长阶段：获取锁而不释放锁。收缩阶段：释放锁而不获取新锁。使用合适的冲突读写锁时，2PL 保证调度具有冲突可串行化性，但仍可能发生死锁。
3	B+ 树为什么适合数据库索引和范围查询？	较大的扇出使树较矮，减少页面访问。有序键和相连的叶节点支持范围扫描。哈希索引针对等值查找，本身不提供同样的有序范围访问。
4	记忆化与自底向上的动态规划有什么区别？	记忆化按需计算子问题，通常使用递归并缓存结果。自底向上的动态规划按依赖项已经求出的次序计算状态，通常通过填表实现。
5	SQL SELECT 查询的简化逻辑处理顺序是什么？	对于不含 CTE、窗口函数或集合运算的查询：FROM/JOIN → WHERE → GROUP BY 与聚合 → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET。这是逻辑模型，不一定是优化器实际执行的物理顺序。
6	什么是幻读？如何防止它？	另一个事务提交更改后，重复谓词查询会得到不同的匹配行集合。标准模型中的 SERIALIZABLE 防止幻读；包括 PostgreSQL REPEATABLE READ 在内的一些实现也会在较低级别防止幻读。
7	什么是脏读？哪个标准隔离级别最先禁止它？	读取另一个事务尚未提交的数据，无论该事务之后是否回滚。READ COMMITTED 及更强的标准隔离级别禁止脏读。
8	标准数组归并排序如何工作？时间和空间界是多少？	它递归排序两个半区，再在线性时间内合并。在比较耗时为常数的假设下，标准版本需要 Θ(n log n) 时间和 O(n) 辅助空间。
9	深度优先搜索如何检测有向图中的环？	DFS 用递归或显式栈向深处探索。指向当前 DFS 路径上仍处于活动状态的顶点的边是回边，证明存在有向环；仅仅指向任意已访问顶点并不足以证明有环。
10	计数排序或基数排序何时能达到线性时间？	计数排序对取值范围含 k 个值的 n 个键需 O(n+k)。基数排序若进行 d 次稳定的数位排序、基数为 b，则需 O(d(n+b))。只有这些参数允许时才是线性时间；它们利用了比较之外的键结构。
11	PostgreSQL 中的主键与外键有何区别？	主键以唯一、非 NULL 的值标识行。外键要求其值匹配被引用的键值，但受相应 NULL 规则约束。它可以引用同表或另一表中符合条件的 UNIQUE 键或主键。
12	原地堆排序的最坏时间和额外空间界是多少？	建堆需要 O(n)，随后所有取出操作合计需要 O(n log n)。若在输入数组中采用迭代下沉，堆排序最坏耗时 O(n log n)，额外空间为 O(1)。
13	什么是拓扑序？卡恩算法如何求得拓扑序？	在有向无环图中，每条边 u→v 都要求 u 排在 v 前面。反复输出入度为零的顶点并删除其出边，将新出现的零入度顶点入队。若输出顶点数少于 V，则有向图含环。
14	插入排序如何工作？近乎有序输入的耗时取决于什么？	它逐个把元素插入已排序的前缀。通常采用相邻移位或交换的版本需要 Θ(n+I) 时间，其中 I 为逆序对数量。I=O(n) 时为线性时间；输入规模小本身并不改变最坏 Θ(n²) 的界。
15	SQL Server 中的聚集与非聚集行存储索引有何区别？	聚集索引按键序存储表行，所以每张表最多有一个。非聚集索引具有自己的键和行定位符，也可包含其他列。这些术语和存储细节因数据库系统而异。
16	快速排序为什么可能耗时 Θ(n²)？随机化有何帮助？	反复出现高度不均衡的划分，例如每次都选不同键中的最小键作为枢轴，会导致二次工作量。当键互异或正确处理重复键时，随机选择枢轴可使期望耗时为 O(n log n)。三数取中是一种实用启发式方法，不保证最坏情况的界。
17	贪心算法与动态规划有何区别？	贪心算法直接采用局部选择，需要证明这些选择能保留一个最优解。动态规划通过递推比较方案并复用子问题结果。全局最优需要正确的模型和递推关系，不能仅凭“动态规划”这一名称保证。
18	迪杰斯特拉算法何时有效？常见的堆实现复杂度是多少？	边权非负时，它反复确定暂定距离最小的顶点。邻接表配合二叉最小堆的实现耗时 O((V+E) log V)。负权边可能使已确定距离的正确性论证失效。
19	在正常同步提交下，PostgreSQL 的 WAL 如何支持持久性？	相关日志记录在确认提交之前、也在写入已更改的数据页之前到达持久存储。崩溃后，WAL 可重放数据页尚未包含的更改。异步提交可能丢失最近已确认的事务。
20	最长公共子序列长度的动态规划递推式是什么？	令 L[i,j] 为长度分别为 i,j 的前缀的最长公共子序列长度。设 L[0,j]=L[i,0]=0。末字符相同则 L[i,j]=1+L[i−1,j−1]；否则 L[i,j]=max(L[i−1,j],L[i,j−1])。完整表需要 O(mn) 时间和空间。
21	贝尔曼–福特算法如何处理负权边并检测可达负环？	对所有边最多进行 V−1 轮松弛。若再从可达顶点松弛仍能改进距离，就说明存在从源点可达的负环。最坏耗时 O(VE)；从此负环可达的顶点没有有限的最短路径代价。
22	整数容量 W 的标准 0/1 背包递推式是什么？	令 D[i,w] 表示用前 i 件物品、容量为 w 时的最大价值，重量 wᵢ 为正整数。设 D[0,w]=0。若 wᵢ>w，则取 D[i−1,w]；否则取 max(D[i−1,w],vᵢ+D[i−1,w−wᵢ])。O(NW) 时间是伪多项式时间。
23	广度优先搜索如何在无权图中找到最短路径？	BFS 使用先进先出队列，按边数距离逐层探索顶点。在顶点入队时标记可避免重复访问。首次发现到达某个可达顶点的路径具有最少的边数。
24	分组查询中的 WHERE 和 HAVING 有何不同？	WHERE 在分组之前筛选输入行。HAVING 筛选产生的分组，可使用 COUNT(*)>1 等聚合条件。
25	什么使排序算法具有稳定性？	键相同的元素保持原来的相对次序。归并排序在相等时先取左侧元素即可实现稳定；标准原地快速排序通常不稳定。稳定性取决于具体实现。
26	邻接矩阵与普通邻接表如何比较？	对 V 个顶点、E 条边，矩阵需 O(V²) 空间，判断一条边是否存在需 O(1)。邻接表需 O(V+E) 空间；在未排序的表中查找边 (u,v) 需 O(deg(u))，其中 deg(u) 是该表长度。
27	事务的 ACID 属性各是什么意思？	原子性：效果要么全部发生，要么全部不发生。一致性：正确事务保持约束和应用不变量。隔离性：并发行为遵守所选隔离级别。持久性：已提交效果在数据库配置保证所涵盖的故障后仍然存在。
28	什么是不可重复读？哪个标准隔离级别可防止它？	另一个事务提交更新或删除后，再读同一行得到不同数据，或发现该行消失。REPEATABLE READ 和 SERIALIZABLE 禁止这种异常。
29	动态规划为何适用于许多优化问题？	最优子结构允许用子问题的最优解表达整体最优解。当子问题重叠时，存储结果可避免重复计算。状态定义和递推关系必须正确表达原问题。
30	INNER JOIN 和 LEFT JOIN 有何区别？	INNER JOIN 返回满足连接条件的行组合。LEFT JOIN 还保留每个未匹配的左表行，并在右表列中填入 NULL。若右表有多个匹配行，一个左表行可能产生多个输出行。
31	第一、第二和第三范式分别要求什么？	1NF：属性值具有原子性。2NF：满足 1NF，且任何非主属性都不依赖于任一候选键的真子集。3NF：满足 1NF，且每个非平凡依赖 X→A 中，X 为超键或 A 为主属性。主属性属于至少一个候选键。
32	克鲁斯卡尔和普里姆算法如何构造最小生成树？	对于连通无向加权图，克鲁斯卡尔按边权递增考察边，用并查集拒绝产生环的边。普里姆从一棵树开始，每次选择连接树内与树外顶点的最小权边来扩展。