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

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

- **Canonical URL:** https://flashcards.world/flashcards/sets/8a582d6a-5bc4-4ff1-ad7e-b9865fa4ba89/
- **Markdown URL:** https://flashcards.world/flashcards/sets/8a582d6a-5bc4-4ff1-ad7e-b9865fa4ba89.md
- **Level:** basic
- **Languages:** zh → zh
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 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 | 克鲁斯卡尔和普里姆算法如何构造最小生成树？ | 对于连通无向加权图，克鲁斯卡尔按边权递增考察边，用并查集拒绝产生环的边。普里姆从一棵树开始，每次选择连接树内与树外顶点的最小权边来扩展。 |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/8a582d6a-5bc4-4ff1-ad7e-b9865fa4ba89/).