数据结构面试题库

使用方式

题型范围：名词解释、30 秒简答、概念辨析、原理说明、工程判断和常见追问。回答时建议按“定义或不变量 - 代表操作 - 复杂度 - 边界/工程取舍”组织，不必复述教材章节。

一、基本概念与复杂度

1. 数据、数据元素、数据项和数据对象有什么区别？

问题意图：检查能否准确使用数据结构的基本术语。

30 秒回答：数据是可被程序识别和处理的符号集合；数据元素是作为一个整体处理的基本单位，也常称结点；数据项是构成数据元素的最小不可分割单位；数据对象是具有相同性质的数据元素的集合。一个学生记录可以是数据元素，学号和成绩是数据项。

展开逻辑：数据结构通常研究数据元素及其关系，而不是孤立的数据值。题目中说“结点”时，要结合上下文判断它是逻辑上的数据元素还是带指针的存储结点。

常见追问：为什么同一个数据元素在不同结构中可以用不同结点类型表示？

易错点：把数据项和数据元素当成同义词，或认为数据对象必须包含所有数据。

2. 逻辑结构、存储结构和抽象数据类型（ADT）如何区分？

问题意图：检查是否理解“接口”和“实现”的分层。

30 秒回答：逻辑结构描述元素之间的关系，如集合、线性、树和图；存储结构描述这些元素及关系在内存中的表示，典型是顺序存储和链接存储；ADT 是数据对象、关系以及允许操作的抽象集合，规定“能做什么”，而不规定“怎么存、怎么做”。

展开逻辑：同一个栈 ADT 可以用数组或链表实现。更换存储方式时，调用者只依赖入栈、出栈等接口，内部的容量策略和指针细节不应泄漏。

常见追问：为什么存储结构也必须保存元素之间的关系？

易错点：把“顺序表”误认为一种逻辑结构；链式存储并不等于逻辑上的非线性结构。

3. 算法的基本特性是什么？怎样判断一个描述不是算法？

问题意图：检查对算法可执行性的理解。

30 秒回答：算法应有零个或多个输入、一个或多个输出，具有有穷性、确定性和可行性。若步骤含糊、存在无限循环、无法由基本操作在有限时间内完成，或对合法输入没有明确输出，就不能称为完整算法。

展开逻辑：输入可以为零个，但输出不能缺失。实现时要为循环写出能变假的条件，为递归写出基例；“尽量快地处理”是目标，不是可执行步骤。

常见追问：如何用断言或不变量帮助证明循环终止和结果正确？

易错点：把“代码能运行”当成算法正确，忽略空输入、溢出和异常状态。

4. Big-O、Theta 和空间复杂度分别表达什么？

问题意图：检查复杂度表达是否严谨。

30 秒回答：大 O 给出渐近上界，Theta 给出同阶紧确界；面试中还应说明最好、平均或最坏情况。空间复杂度统计随输入规模增长的额外空间，通常不把固定大小的输入本身算作辅助空间，但递归调用栈、临时数组和哈希表空间要算入。

展开逻辑：顺序表随机访问是 O(1)，中间插入通常是 O(n)；链表找到插入位置需要 O(n)，但已知结点指针时局部插入是 O(1)。同一算法在不同表示上可能有不同复杂度。

常见追问：为什么递归遍历二叉树的辅助空间是 O(h) 而不是 O(n)？

易错点：把 O(n) 当作精确运行时间，或只报平均复杂度而不说明前提。

5. C 语言数据结构实现中，指针、所有权和内存释放怎样设计？

问题意图：检查能否把抽象算法落到可靠代码。

30 秒回答：结点由 malloc 创建后要明确由哪个容器拥有并负责 free；插入、删除和返回指针的接口要说明是否转移所有权。修改指针前保存后继，处理空指针、头结点和分配失败；释放后不要继续解引用，必要时将局部指针置空。

展开逻辑：链式结构的析构应遍历每个结点一次，避免重复释放或只释放头结点造成泄漏。若数据元素本身还拥有动态内存，应定义深拷贝、浅拷贝和析构策略。

常见追问：如何用 AddressSanitizer 或单元测试定位链表越界和泄漏？

易错点：返回局部变量地址、free 后访问结点、未检查 malloc 返回值。

二、线性表、栈、队列、串与数组

6. 线性表的定义是什么？顺序表和单链表如何选择？

问题意图：检查抽象线性关系与实现取舍。

30 秒回答：线性表是零个或多个相同类型元素组成的有限序列，除首尾外每个元素有且仅有一个直接前驱和后继。顺序表连续存储、支持 O(1) 随机访问但扩容和中间插入成本高；单链表不要求连续空间、插入删除灵活，但随机访问为 O(n) 且有指针额外开销。

展开逻辑：读多写少且索引访问频繁时选顺序表；长度变化大、局部插入删除多且已有位置指针时链表更合适。缓存局部性也会使顺序表在实际性能上占优。

常见追问：为什么链表的插入是 O(1) 仍可能比数组慢？

易错点：不说明“已知插入位置”就声称链表插入恒为 O(1)；忽略顺序表的扩容成本。

7. 单链表在结点后插入和删除结点的关键指针操作是什么？

问题意图：检查 C 语言链表基本功。

30 秒回答：在 p 后插入 s 先执行 s->next = p->next，再执行 p->next = s；删除 p 后继 q 时先保存 q = p->next，令 p->next = q->next，最后释放 q。若删除的是头结点，要更新头指针。

展开逻辑：带头结点的链表可以统一空表和首结点操作；不带头结点时要区分首结点、尾结点和单结点表。删除前应确认目标确实属于该链表，避免释放外部指针。

常见追问：如何在只有头指针的单链表中删除尾结点？

易错点：先覆盖 p->next 导致后继丢失；忘记空表和只有一个结点的情况。

8. 双向链表和循环链表比单链表多解决了什么问题？

问题意图：检查对前驱访问和边界连接的理解。

30 秒回答：双向链表每个结点有前后两个指针，可在已知结点时 O(1) 删除且能向前遍历，但空间开销和维护指针的风险更大。循环链表把尾结点指回首结点，适合轮转调度；判断结束不能用 NULL，而要判断是否回到起点。

展开逻辑：双向链表插入时要同时更新四条关系：新结点的前后指针，以及相邻结点指向新结点的指针。带头结点的双向循环链表可把空表、首尾插入统一为局部操作。

常见追问：如何验证双向链表的前后指针始终互相一致？

易错点：只更新 next 未更新 prev；循环遍历写成 while (p != NULL) 导致死循环。

9. 两个有序单链表怎样合并？如何原地删除重复值？

问题意图：检查双指针和原地操作能力。

30 秒回答：合并时用两个游标比较当前结点，把较小者接到结果尾部，某一表耗尽后直接接上另一表，时间 O(m+n)。有序表去重只需比较相邻结点，重复时摘下并释放，时间 O(n)、额外空间 O(1)。

展开逻辑：若要求稳定合并，相等时优先接左表结点；若两个表不允许修改，可以复制结点，代价是 O(m+n) 空间。循环链表需把尾指针暂时断开或显式处理回到起点。

常见追问：无序单链表去重有哪些办法？

易错点：合并后仍使用已经接入结果的游标；释放重复结点前没有保存其后继。

10. 动态数组如何扩容，怎样避免频繁搬移？

问题意图：检查顺序表的工程实现和摊销复杂度。

30 秒回答：容量不足时申请更大的连续空间，复制旧元素后释放旧空间；常用按倍数增长而非每次只加一个。单次扩容是 O(n)，但倍增策略使连续尾插的摊销时间为 O(1)，代价是可能有未使用容量和一次较大的内存峰值。

展开逻辑：扩容前要检查容量计算是否溢出、realloc 失败是否保留旧指针；元素含内部指针时不能简单按字节复制而忽略所有权。多线程场景还要保护读写和迭代器失效。

常见追问：为什么缩容不能在长度刚低于容量时立即执行？

易错点：直接把 realloc 返回值覆盖旧指针；扩容后继续使用旧地址。

11. 栈的特点是什么？如何用栈处理括号匹配或表达式求值？

问题意图：检查后进先出模型及应用。

30 秒回答：栈只允许在一端进行插入和删除，遵循后进先出。括号匹配遇到左括号入栈，右括号检查栈顶类型并弹出，结束时栈必须为空；中缀表达式求值通常用一个运算符栈和一个操作数栈处理优先级与结合性。

展开逻辑：函数调用、递归回溯和深度优先搜索都隐含使用栈。实现要检查空栈出栈、容量溢出，并明确一元运算符和括号的优先级。

常见追问：递归太深导致栈溢出时如何改写？

易错点：把队列的先进先出规则套到栈；只检查括号数量而不检查类型和嵌套次序。

12. 循环队列如何区分队空和队满？

问题意图：检查队列下标和边界处理。

30 秒回答：队列在一端入队、另一端出队，遵循先进先出。循环队列可额外维护元素个数 size，size==0 为空、size==capacity 为满；也可浪费一个槽位，用 front==rear 判空、(rear+1)%capacity==front 判满。

展开逻辑：入队后 rear=(rear+1)%capacity，出队后 front=(front+1)%capacity。采用计数法能利用全部空间，但计数必须与指针更新保持原子一致。

常见追问：为什么普通数组队列出队后不能只移动 front 而不循环？

易错点：把队满和队空都写成 front==rear；模运算的容量、下标和有符号整数处理不一致。

13. 用两个栈实现队列，或用两个队列实现栈，复杂度如何？

问题意图：检查抽象接口和摊销分析。

30 秒回答：两个栈实现队列时，入队压入输入栈；出队若输出栈为空，则把输入栈全部转移过去，再从输出栈弹出。每个元素至多转移一次，均摊 O(1)，单次最坏 O(n)。两个队列实现栈可通过每次入栈把元素搬到非空队列末端，或交换队列，单次操作最坏 O(n)。

展开逻辑：要说明空结构和转移时机。工程上若需要严格的单次延迟上界，应选择更适合的专用队列，而不能只看均摊复杂度。

常见追问：怎样让两个栈队列的出队操作最坏 O(1)？

易错点：每次出队都搬移元素，误称为 O(1)；没有说明两个栈的容量总和。

14. 串、子串和模式匹配中的“位置”如何定义？

问题意图：检查字符串作为字符线性表的基本概念。

30 秒回答：串是字符组成的有限序列；串中连续的一段字符构成子串，子串在主串中的起始下标称为位置。朴素匹配从每个可能起点逐字符比较，最坏 O(nm)；KMP 通过模式串的部分匹配信息避免主串回退，最坏 O(n+m)。

展开逻辑：实现要统一下标从 0 还是 1 开始，并为 C 字符串保留结尾 \0。KMP 的 next/前缀函数含义是最长相等真前后缀，更新时要避免越界。

常见追问：为什么 KMP 不需要回退主串指针？

易错点：把子串和子序列混淆；忘记 \0 造成长度和比较越界。

15. 数组的行优先寻址和稀疏矩阵压缩有什么工程意义？

问题意图：检查数组存储和空间优化。

30 秒回答：二维数组在 C 中按行连续存储，地址可由首地址、行跨度和列偏移计算；按列访问会产生较差的缓存局部性。稀疏矩阵大多数元素为零时，可只保存非零元素的行号、列号和值，或用压缩行格式，减少空间并加速遍历非零项。

展开逻辑：普通二维数组随机访问 O(1)，压缩格式的读取可能需要索引或二分查找。选择格式要看矩阵是否变化频繁、是否需要随机修改以及乘法运算模式。

常见追问：为什么把稀疏矩阵存成三元组不一定适合频繁随机更新？

易错点：行下标、列下标和元素大小混用；认为压缩后所有访问都比普通数组快。

16. 递归遍历和显式栈遍历如何比较？

问题意图：检查递归状态与辅助空间。

30 秒回答：递归代码直观，调用栈保存当前结点和返回位置；显式栈可以控制栈容量、携带额外状态并避免系统栈溢出。二叉树遍历两者时间都是 O(n)，辅助空间都是 O(h)，其中 h 是树高；显式栈更适合需要暂停、迭代或统一错误处理的工程代码。

展开逻辑：后序遍历的迭代版本通常需要记录上次访问结点或为栈帧保存阶段。递归函数必须有空树基例，否则会无限调用。

常见追问：一棵退化树有 n 个结点时，递归栈空间是多少？

易错点：把遍历辅助空间一律写成 O(n)；忽略最坏情况下 $h=n$。

三、树、二叉树、堆与哈夫曼树

17. 树的结点度、层数、深度和森林分别是什么？

问题意图：检查树结构术语和层次关系。

30 秒回答：结点的度是其孩子数，树的度是所有结点度的最大值；根通常记为第 1 层，树的深度或高度是结点最大层数；森林是若干棵互不相交树的集合。树中除根外每个结点只有一个双亲，但可以有多个孩子。

展开逻辑：有序树中孩子从左到右的次序有意义，无序树则不强调次序。题目若给边集合，应先确认边方向代表双亲到孩子，再计算层数。

常见追问：树和线性表都能从一个结点走到下一个结点，它们的关键区别是什么？

易错点：把叶子结点的层数当成度；把树的度与结点的度混用。

18. 二叉树有哪些基本性质？如何快速检查答案？

问题意图：检查数量关系和边界推理。

30 秒回答：第 i 层最多有 $2^{(i-1)}$ 个结点，深度为 k 的二叉树最多有 $2^k-1$ 个结点；任意非空二叉树若叶子数为 n0、度为 2 的结点数为 n2，则 $n_0=n_2+1$。完全二叉树按层序编号时，结点 i 的孩子通常是 $2i$ 和 $2i+1$（存在时）。

展开逻辑：这些关系可通过“边数等于结点数减一”验证。对含 n 个结点的完全二叉树，深度为 $\mathrm{floor}\left({\log }_{2}n\right)+1$；计算时要注意 $n=0$的空树边界。

常见追问：为什么二叉树不可能只有一个度为 1 的结点而没有叶子？

易错点：把层从 0 开始和从 1 开始的公式混用；把完全二叉树最大结点数写成 $2^{(k-1)}$。

19. 满二叉树、完全二叉树、斜树和二叉排序树有什么区别？

问题意图：检查容易混淆的定义。

30 秒回答：满二叉树每个分支结点都有两个孩子且所有叶子同层；完全二叉树除最后两层外满，最后一层结点从左到右连续；斜树每个结点至多只有一个孩子；二叉排序树还要求左子树关键字小于根、右子树关键字大于根，它不必满或完全。

展开逻辑：完全二叉树适合数组存储，斜树会使基于树高的操作退化为线性。重复关键字时二叉排序树要先约定放左侧、右侧或单独计数，否则定义不完整。

常见追问：一棵完全二叉树一定是二叉排序树吗？

易错点：看到“每层尽量填满”就称为满二叉树；把堆的大小关系当成排序树的左小右大关系。

20. 已知前序和中序序列时，如何唯一重建二叉树？

问题意图：检查遍历递归关系。

30 秒回答：前序第一个元素是根，在中序中定位该根，左侧元素构成左子树、右侧构成右子树；再按对应长度切分前序，递归重建。若关键字不重复，前序加中序可唯一确定二叉树；只给前序和后序通常不能唯一确定。

展开逻辑：为了避免每层扫描中序，可预先建立关键字到下标的映射，时间降为 O(n)。输入序列长度、集合和重复值必须先校验，否则切分可能越界或产生多棵候选树。

常见追问：给定中序和层序能否重建？需要哪些假设？

易错点：切分前序时忘记左子树结点数；忽略重复关键字导致的非唯一性。

21. 四种二叉树遍历各有什么典型用途？层序遍历怎样实现？

问题意图：检查遍历次序与数据结构选择。

30 秒回答：前序是根、左、右，适合复制树或生成前缀表达式；中序是左、根、右，二叉排序树的中序结果有序；后序是左、右、根，适合释放树或计算子树结果；层序按层从左到右，使用队列实现。

展开逻辑：层序遍历应先将根入队，循环取队头、访问并把非空孩子入队。前中后序递归的基例都是空结点返回，迭代版本需要明确压栈顺序以保证访问顺序。

常见追问：如何用后序遍历安全释放一棵二叉树？

易错点：二叉树前序和中序的“根”位置写错；层序遍历使用栈导致退化为深度优先。

22. 线索二叉树解决了什么问题？

问题意图：检查对空指针利用和遍历状态的理解。

30 秒回答：普通二叉链表中大量左右指针为空，线索二叉树把空指针改作指向中序前驱或后继的线索，并用标志位区分孩子指针和线索，从而可在不使用递归栈的情况下按指定次序遍历。建立线索时要按遍历序列维护前驱结点。

展开逻辑：线索本身不是子树关系，插入删除会改变前驱后继，维护成本高；若只做一次遍历，显式栈往往更简单。标志位错误会把线索当孩子递归，造成环或非法访问。

常见追问：为什么线索二叉树仍需要一个头结点或特殊结束标志？

易错点：忘记区分 ltag/rtag；把指向遍历后继的线索当作右孩子。

23. 树、森林与二叉树如何互相转换？

问题意图：检查孩子兄弟表示法。

30 秒回答：树可用“左孩子、右兄弟”二叉链表表示：左指针指向第一个孩子，右指针指向下一个兄弟；从树转二叉树时连接兄弟并只保留第一个孩子关系，再调整层次。森林中每棵树转成二叉树后，让后一棵树的根作为前一棵根的右兄弟。转换是可逆的。

展开逻辑：树的先根遍历对应转换后二叉树的前序遍历，树的后根遍历对应转换后二叉树的中序遍历。实现时要保证兄弟链终止并避免把不同树的根误当孩子。

常见追问：孩子兄弟表示法为什么能用固定两个指针表达任意度数的树？

易错点：把右兄弟指针当作右孩子；森林第一棵树的根没有父兄关系却错误连接。

24. 二叉排序树的查找、插入和删除为什么可能退化？

问题意图：检查不变量和最坏性能。

30 秒回答：二叉排序树保持左子树关键字小于根、右子树大于根。查找和插入沿比较结果向下一层，复杂度为 O(h)；树平衡时 $h=O\left(\log n\right)$，按有序序列插入会形成斜树，退化为 O(n)。删除叶子、单孩子和双孩子结点要分别处理，双孩子通常用中序后继或前驱替换。

展开逻辑：递归实现要返回新的子树根，以便处理删除根结点。重复键策略要与查找和删除保持一致，否则会破坏有序不变量。

常见追问：为什么删除双孩子结点后，用中序后继替换不会破坏排序性质？

易错点：只改数据不改链接导致泄漏；删除根结点时忘记更新树根指针。

25. AVL 树的平衡因子和四种旋转如何判断？

问题意图：检查自平衡查找树的局部修复。

30 秒回答：AVL 树要求任意结点左右子树高度差绝对值不超过 1。插入后从失衡结点向上回溯，若新结点在左左、右右方向分别做单右旋、单左旋；左右、右左方向做先子树旋转再根旋转的双旋。旋转保持中序关键字序列不变。

展开逻辑：结点需维护高度或平衡因子，更新顺序应先更新被下移结点再更新新根。AVL 查找 O(log n)，插入和删除也为 O(log n)，但旋转和维护元数据增加常数开销。

常见追问：删除结点后为什么可能需要沿路径连续调整多个结点？

易错点：把 LR 直接当一次左旋；旋转后高度更新顺序错误导致后续判断失真。

26. 堆是什么？建堆、插入和删除的复杂度如何？

问题意图：检查完全二叉树与局部序关系。

30 秒回答：堆是满足父子序关系的完全二叉树；父值不大于孩子是小根堆，不小于孩子是大根堆。数组中结点 i 的父子下标可用 $\frac{i}{2}、2i、2i+1$ 表示。插入上浮、删除堆顶下沉均为 O(log n)，自底向上建堆为 O(n)。

展开逻辑：堆只保证根是全局最小或最大，不保证数组整体有序。建堆的 O(n) 来自大量结点高度很小，不能简单把 n 次插入的 O(n log n) 当作唯一实现。

常见追问：为什么堆排序不是稳定排序？

易错点：把堆当作二叉排序树；上浮/下沉比较方向写反。

27. 优先队列为什么常用堆实现？工程上还要注意什么？

问题意图：检查抽象优先队列和实际约束。

30 秒回答：优先队列每次取出最高优先级元素，二叉堆能以 O(log n) 插入和删除堆顶，并以 O(1) 查看堆顶。工程上要定义相等优先级的稳定规则、容量增长、比较器和并发访问；若需要快速合并或可持久化，可能选择其他堆或树结构。

展开逻辑：比较器必须满足严格弱序，否则堆不变量可能无法维持。定时任务或事件调度可在堆顶保存最近到期事件，但取消任意事件通常需要额外索引。

常见追问：如何支持“降低某个任务优先级”并避免线性扫描？

易错点：只修改结点值不做上浮/下沉；把“优先级最高”误解为数值最大而未说明约定。

28. 哈夫曼树怎样构造？带权路径长度如何计算？

问题意图：检查贪心合并和编码原理。

30 秒回答：每次从当前森林中选权值最小的两棵树合并，父结点权值为两者之和，再把新树放回森林，直到只剩一棵。带权路径长度是每个叶子权值乘根到叶子的路径长度之和；哈夫曼树使该值最小，编码中左、右边分别记 0、1。

展开逻辑：可用最小堆维护森林，构造复杂度约为 O(n log n)。权值相同会产生多棵等价哈夫曼树，编码不一定唯一，但总带权路径长度相同；编码必须满足前缀码性质。

常见追问：为什么哈夫曼树不存在度为 1 的结点？

易错点：把内部结点权值也直接当作编码符号；计算路径长度时从 0 层还是 1 层混用。

29. 二叉树 C 语言实现如何避免递归和内存问题？

问题意图：检查树结构的工程可靠性。

30 秒回答：结点通常含数据、左指针和右指针；创建时检查分配失败，插入或删除后返回新的子树根。释放采用后序顺序，先释放左右子树再释放根；树很深时用显式栈或限制深度，避免系统栈溢出。

展开逻辑：复制树要递归复制结点而不能只复制根指针；共享子树时需要引用计数或访问标记，否则会重复释放。遍历接口应说明是否允许修改树和是否返回内部指针。

常见追问：如何检测一棵树是否有环？

易错点：先释放根再访问孩子；把共享子树当成普通树重复析构。

四、图及其典型算法

30. 图、顶点、边、路径、连通图和强连通分量如何定义？

问题意图：检查图论基本术语。

30 秒回答：图由顶点集合 V 和边集合 E 构成；无向边没有方向，有向边有起点和终点。路径是按边连续经过的顶点序列；无向图任意两点间有路径称连通图，其极大连通子图是连通分量；有向图中两点互相可达的极大子图是强连通分量。

展开逻辑：无向图顶点度是相连边数，有向图要区分入度和出度。简单图不含自环和重边，完全图的边数与顶点数有关，不能把有向和无向公式混用。

常见追问：为什么有向图“弱连通”与“强连通”不是一回事？

易错点：把有向边的入度、出度颠倒；把任意一条路径存在误说成所有路径都存在。

31. 邻接矩阵和邻接表如何选择？遍历复杂度分别是多少？

问题意图：检查表示方法与稠密度的关系。

30 秒回答：邻接矩阵用 n×n 数组表示边，判断两点是否相邻 O(1)，空间 O(n²)，适合稠密图；邻接表为每个顶点保存邻接边，空间 O(n+e)，遍历所有边 O(n+e)，适合稀疏图。矩阵遍历一个顶点的邻接点常需扫描整行 O(n)。

展开逻辑：有向图矩阵不一定对称；带权图要约定无边使用无穷大或特殊标志。邻接表中边结点的所有权和释放策略也需明确。

常见追问：动态网络中频繁增删边时，哪种表示更容易维护？

易错点：把邻接表遍历写成 O(n²) 的固定结论；忽略矩阵的初始化和无边哨兵值。

32. DFS 与 BFS 的核心思想和应用有什么不同？

问题意图：检查遍历状态及栈队列选择。

30 秒回答：DFS 沿一条路径尽量深入，递归或显式栈实现；BFS 按距离逐层扩展，使用队列实现。两者时间在邻接表上都是 O(n+e)，都要用 visited 防止重复访问。无权图最短边数路径用 BFS，连通性、回溯和拓扑辅助常用 DFS。

展开逻辑：若图不连通，应从每个未访问顶点重新启动遍历。邻接点遍历顺序会影响具体序列，但不影响访问集合和复杂度。

常见追问：BFS 求最短路时为什么不能标记到队列出队才标记？

易错点：忘记 visited 导致有环图无限循环；用 DFS 的深度优先顺序声称一定得到无权最短路。

33. Prim 和 Kruskal 如何求最小生成树？如何保证不成环？

问题意图：检查贪心策略和适用场景。

30 秒回答：Prim 从一个顶点出发，每次选择连接当前集合与外部顶点的最小边；Kruskal 将边按权值排序，依次选择不会形成环的边。Kruskal 常用并查集判断连通分量；连通图的最小生成树恰有 n-1 条边。Prim 适合稠密图，Kruskal 适合边较少或边表已排序的图。

展开逻辑：相同权值可能得到不同但等价的最小生成树。并查集合并时使用按秩合并和路径压缩可近似常数时间，不能只检查边两端是否直接相邻。

常见追问：图不连通时 Kruskal 的结果是什么？

易错点：把“最小边”不加条件地加入导致成环；把最短路径树与最小生成树混为一谈。

34. 拓扑排序如何判断有向图是否存在环？

问题意图：检查偏序关系和入度维护。

30 秒回答：AOV 网中顶点表示活动、边表示先后约束。不断选择入度为 0 的顶点输出，并删除它的出边、更新邻接点入度；若输出顶点数少于 n，说明剩余部分存在环，无法完成拓扑排序。DFS 也可用三色标记检测回边。

展开逻辑：入度为 0 的顶点可能有多个，选择不同会得到不同合法序列。队列、栈或优先队列决定结果的字典序或稳定规则。

常见追问：如何在拓扑排序中输出字典序最小的合法序列？

易错点：删除顶点时忘记更新所有出边；把无向图套用入度为 0 的定义。

35. Dijkstra 和 Floyd 分别解决什么最短路径问题？

问题意图：检查单源和多源最短路的适用条件。

30 秒回答：Dijkstra 求一个源点到其他点的最短路，要求边权非负；每轮从未确定顶点中选当前距离最小者并松弛其出边，常用堆实现。Floyd 用动态规划同时求所有点对最短路，转移为 dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])，时间 O(n³)、空间 O(n²)，可处理负边但不能有负环。

展开逻辑：Dijkstra 一旦确定的顶点不能再被负边改进，因此不能用于含负权边的图。要恢复路径需保存前驱数组；检测负环可观察 Floyd 的 dist[i][i] 是否变负。

常见追问：边权都为 1 时为什么 BFS 通常比 Dijkstra 简单高效？

易错点：把 Dijkstra 用在负权图；Floyd 的中间点循环顺序错误导致状态不完整。

36. AOE 网中的关键路径和关键活动如何理解？

问题意图：检查工程计划网络的时间分析。

30 秒回答：AOE 网用边表示活动、顶点表示事件；从源点到汇点的最长路径是关键路径，决定工程最短工期。关键活动的最早开始时间与最迟开始时间相等，延迟会直接影响工期。通常先按拓扑序求事件最早时间，再逆拓扑求最迟时间。

展开逻辑：活动持续时间应加在边上，不能把 AOV 的顶点活动定义直接套用。多个关键路径可能同时存在；若存在环，事件时间无法按拓扑序计算。

常见追问：如何识别有浮动时间但不是关键活动的边？

易错点：把最长路径问题误当作带负权的最短路；把关键路径理解成边数最多而非总工期最长。

五、查找、散列与排序

37. 顺序查找和折半查找的适用条件与复杂度是什么？

问题意图：检查查找前提和平均查找长度。

30 秒回答：顺序查找不要求记录有序，顺序或链式存储都能用，成功和失败最坏 O(n)。折半查找要求顺序存储且关键字有序，通过比较中间元素缩小区间，平均和最坏 O(log n)，但插入维护有序表的成本较高。成功查找的平均查找长度要按各记录访问概率加权。

展开逻辑：若访问概率不等，不能简单用比较次数的算术平均；失败查找也有对应判定树。链表不支持 O(1) 中点访问，直接套二分查找会失去优势。

常见追问：如何避免 mid=(low+high)/2 的整数溢出？

易错点：对无序数组使用二分查找；边界更新不排除 mid 导致死循环。

38. 二叉排序树、AVL 树和哈希表如何选型？

问题意图：检查数据结构的工程判断能力。

30 秒回答：二叉排序树支持有序遍历和范围查询，但可能退化；AVL 通过旋转保证 O(log n)，适合查询稳定、更新较少的场景；哈希表平均查找接近 O(1)，但不保持顺序，依赖散列质量，最坏可能 O(n)。需要范围查询、顺序输出或可预测最坏延迟时优先考虑平衡树。

展开逻辑：还要比较内存局部性、扩容停顿、并发策略和键值可比较性。哈希表的平均复杂度是统计结论，不应在攻击者可控输入下当作最坏保证。

常见追问：为什么数据库索引常用 B+ 树而不是普通哈希表？

易错点：宣称哈希表“永远 O(1)”；忽略排序树重复键和范围查询规则。

39. 散列表的冲突如何处理？线性探测和链地址各有什么代价？

问题意图：检查哈希不变量和冲突策略。

30 秒回答：不同关键字映射到同一地址就产生冲突。开放定址法在表内继续探测，线性探测简单但会产生聚集；二次探测可减轻一部分聚集。链地址法把同义词挂在桶的链表中，删除简单、装载因子可大于 1，但有指针开销和缓存不连续。

展开逻辑：删除开放定址元素不能简单置空，否则会截断后续探测链，通常使用墓碑标记或重建。扩容应在装载因子达到阈值前进行，并重新插入所有有效记录。

常见追问：如何设计一个均匀、可复现且不易被恶意构造的散列函数？

易错点：线性探测越过表尾不取模；链地址查找只比较地址不比较完整关键字。

40. 平均查找长度（ASL）怎样计算和解释？

问题意图：检查概率加权和性能指标。

30 秒回答：成功查找的 ASL 是每个记录关键字比较次数按其查找概率加权的期望值，即 $\mathrm{ASL}=\Sigma p_i{c}_i$；概率相等时为比较次数之和除以记录数。失败查找应按失败出口的概率或判定树叶子分别统计，不能与成功 ASL 混为一谈。

展开逻辑：顺序查找的成功 ASL 在等概率时约为 $\frac{(n+1)}{2}$；平衡二叉查找树的比较次数与层数相关。报告 ASL 时要说清楚查找成功/失败、概率分布和是否把最后一次失败比较计入。

常见追问：为什么同样的平均复杂度在偏斜访问分布下实际延迟可能很不同？

易错点：把平均查找长度写成 O(n) 就停止，不给出比较次数或概率假设。

41. 稳定排序、原地排序和自适应排序分别是什么意思？

问题意图：检查排序性质而非死记速度。

30 秒回答：稳定排序保证相等关键字的原相对次序不变；原地排序只使用常数级或很少的额外存储；自适应排序能利用已有有序性在近有序输入上加速。三者是不同维度，不能由某一个性质推出另外两个。

展开逻辑：稳定性在按多关键字排序、保留时间顺序或数据库结果时有用。实现中相等时使用 <= 还是 <、是否跨越相等元素交换，都会影响稳定性。

常见追问：为什么快速排序通常不稳定，而归并排序可以稳定？

易错点：把“原地”理解为完全不使用栈；把平均 O(n log n) 当成稳定性的证明。

42. 直接插入、希尔和冒泡排序如何比较？

问题意图：检查简单排序的适用场景。

30 秒回答：直接插入逐个把元素插入已有序前缀，最好 O(n)、平均和最坏 O(n²)，稳定且适合近有序小规模数据；希尔排序按增量分组进行插入，通常不稳定，复杂度依赖增量序列；冒泡排序反复交换相邻逆序对，稳定，若设置提前结束标志，最好可到 O(n)。

展开逻辑：插入排序移动而不是反复交换，写代码时要暂存待插入元素。希尔增量必须最终为 1，否则不能保证全局有序；冒泡排序的边界每趟缩短可减少无效比较。

常见追问：为什么插入排序在小数组上可能比复杂度更优的算法快？

易错点：忽略冒泡排序的提前终止条件；声称希尔排序稳定或有统一固定的时间复杂度。

43. 快速排序的分区不变量是什么？如何避免最坏退化？

问题意图：检查分治和边界实现。

30 秒回答：分区后，基准左侧元素应不大于基准、右侧元素应不小于基准（具体不等号取决于重复键策略），递归处理两个子区间。若每次基准都落在端点，时间退化为 O(n²)；随机选基准、三数取中或对小区间改用插入排序可降低风险，递归较深时用较小区间优先处理。

展开逻辑：原地分区需保证左右指针推进，否则遇到大量相等键会死循环。工程库常使用内省排序，在递归过深时切换堆排序，以提供 O(n log n) 上界。

常见追问：怎样处理大量重复关键字的输入？

易错点：分区后递归区间包含基准导致无限递归；随机化没有固定种子或没有防止最坏攻击。

44. 选择排序、堆排序和归并排序的复杂度与稳定性如何比较？

问题意图：检查综合选型能力。

30 秒回答：简单选择排序最好、平均、最坏均 O(n²)，原地但通常不稳定；堆排序最好、平均、最坏均 O(n log n)，原地但不稳定；二路归并排序各情况均 O(n log n)，可稳定但需要 O(n) 辅助空间。若内存紧张且要最坏保证可选堆排序，若要稳定和外部排序可选归并。

展开逻辑：堆排序缓存局部性通常不如快速排序；归并排序可通过自底向上或外部归并处理超内存数据。选择排序在写次数昂贵的介质上有时反而有价值，因为交换次数少。

常见追问：外部排序为什么常采用多路归并而不是直接快速排序？

易错点：把“归并排序原地”当成默认性质；认为选择排序交换少就一定运行更快。

45. 如何用 C 语言实现一个可测试的排序函数？

问题意图：检查算法代码、接口和测试意识。

30 秒回答：接口应接收数组指针、元素个数和比较器，明确是否允许修改输入、是否稳定以及失败行为。实现中使用 size_t 防止负下标，比较和交换不能越界；测试空数组、单元素、重复值、已排序、逆序、极值和随机数据，并用断言验证输出有序及元素多重集合不变。

展开逻辑：若元素大小可能溢出，不能用减法直接做比较器；交换大对象要考虑临时缓冲和对齐。可将算法与测试数据生成、性能计时、Sanitizer 检查分离，避免测试代码污染生产接口。

常见追问：怎样验证排序没有丢失或重复元素？

易错点：比较器返回 $a-b$ 导致整数溢出；只测试随机数据，漏掉重复键和空输入。

47. 并查集解决什么问题？路径压缩和按秩合并为什么有效？

问题意图：检查动态连通性问题和摊还复杂度的理解。

30 秒回答：并查集维护若干互不相交集合，支持查找元素所属代表元和合并两个集合，适合连通分量、等价关系和 Kruskal 算法。路径压缩把查找路径上的节点直接指向根，按秩或按大小合并让较矮树挂到较高树下，两者结合后的单次操作摊还复杂度接近常数 $O(\alpha \left(n\right))$。

展开逻辑：代表元只表示集合身份，不一定是最小编号；合并前先比较两个根，不能把任意节点直接相连，否则树高可能退化。并查集擅长合并和连通性判断，不支持高效拆分集合或维护一般的路径长度。

常见追问：为什么只做路径压缩但不按秩合并，仍可能出现较深的树？

易错点：把并查集当成普通树遍历，或在合并时忘记更新根节点的秩/大小。

48. 字典树（Trie）适合哪些查询？与哈希表如何取舍？

问题意图：检查前缀查询、字符集和空间复杂度之间的工程判断。

30 秒回答：Trie 按字符逐层组织字符串，查找、插入和前缀匹配的时间主要与字符串长度 L 有关，可直接枚举某个前缀下的所有词。哈希表平均精确查找接近 $O\left(1\right)$，但不保留字典序和前缀结构；Trie 需要更多节点和指针，适合自动补全、词典和路由前缀匹配，哈希表适合内存敏感的精确键查询。

展开逻辑：节点可以用定长数组、稀疏映射或压缩边表示，选择取决于字符集和词表密度；删除时要区分共享前缀的节点。工程上还要考虑大小写、Unicode 编码、缓存局部性和恶意超长输入。

常见追问：为什么在字符集很大且词表稀疏时，Trie 的定长子指针数组会浪费空间？

易错点：把 Trie 的复杂度写成与词典总规模无关，或认为哈希表天然支持最长前缀匹配。

49. 如何用哈希表和双向链表实现 LRU 缓存？

问题意图：检查多数据结构组合、复杂度和淘汰策略。

30 秒回答：哈希表把键映射到链表节点，双向链表按最近使用顺序排列；访问或更新节点时把它移动到表头，容量满时删除表尾节点并从哈希表移除。这样查询、插入、更新和淘汰都能达到平均 $O\left(1\right)$，同时保持明确的最近最少使用顺序。

展开逻辑：链表节点应同时保存键和值，删除和移动要正确维护前后指针及头尾哨兵；更新已有键不能重复占用容量。并发场景需要锁或分片，缓存失效、过期时间和大对象内存占用也要单独设计。

常见追问：为什么只用哈希表不能在 $O\left(1\right)$ 时间找到最久未使用的键？

易错点：移动节点后忘记更新哈希表指针，或淘汰链表节点却保留了对应哈希表项。

50. B 树和 B+ 树为什么适合外存索引？

问题意图：检查树高、磁盘块访问和范围查询的关系。

30 秒回答：B 树和 B+ 树通过高分支度降低树高，使一次磁盘块读入可以比较多个关键字，减少随机 I/O。B+ 树的内部节点只存索引，所有记录集中在叶节点且叶节点相互链接，范围查询和顺序扫描更高效；B 树的记录可分布在内部节点，单点查询可能提前结束但范围遍历不如 B+ 树规整。

展开逻辑：阶数要根据页大小、键值长度、指针和缓存命中率选择；插入和删除通过分裂、合并或重新分配维持占用下限。数据库还要考虑聚簇/非聚簇索引、重复键、并发锁和崩溃恢复，不能只看渐进复杂度。

常见追问：为什么 B+ 树叶节点链表能提高范围查询速度？

易错点：把 B+ 树的所有数据都放在根节点，或忽略节点分裂后的父节点更新和磁盘页边界。

51. 数组、链表和动态数组如何选择？

问题意图：考查访问模式、内存局部性和更新代价。

30 秒回答：数组连续存储、随机访问快但中间插入代价高；链表插入删除在已知节点时快但访问需遍历且局部性差；动态数组兼顾连续存储和尾部扩容，扩容会产生摊还成本。选择取决于访问、更新和内存约束。

展开逻辑：同时说明缓存命中、迭代器失效和扩容策略。频繁中间插入不一定首选链表，还要看是否能批量移动或使用分块结构。

常见追问：为什么理论 O(1) 的链表插入在工程中可能更慢？

易错点：只比较渐进复杂度，不考虑缓存、分配和指针追逐。

52. 摊还分析和最坏复杂度有什么区别？

问题意图：检查动态结构复杂度表述。

30 秒回答：最坏复杂度约束单次操作的最大代价；摊还分析把一串操作的总成本平均到每次，允许个别操作很慢。例如动态数组扩容单次 O(n)，但采用倍增扩容时连续插入的摊还复杂度为 O(1)。

展开逻辑：可用聚合、记账或势能法证明，并说明摊还保证不是随机平均，不依赖输入概率分布。

常见追问：摊还 O(1) 是否意味着每一次操作都在常数时间内完成？

易错点：把摊还复杂度当作最坏单次复杂度，或使用加一扩容却声称仍是 O(1) 摊还。

53. 哈希冲突有哪些解决方法？

问题意图：考查哈希表的正确性与性能。

30 秒回答：常见方法有拉链法和开放定址法；开放定址又包括线性探测、二次探测和双重哈希。负载因子过高会使查找变慢，删除时需使用墓碑或重排保证探测链不断裂。

展开逻辑：说明哈希函数应均匀分布，扩容要重新散列。开放定址适合连续内存但对删除和聚集敏感，拉链法更易处理高负载但有额外指针开销。

常见追问：为什么开放定址表删除元素不能简单置为空？

易错点：忽略负载因子、聚集和删除标记，或把哈希冲突说成哈希函数错误。

55. 拓扑排序什么时候不存在？

问题意图：考查有向图的环与依赖关系。

30 秒回答：拓扑排序只适用于有向无环图。若 Kahn 算法处理后仍有节点入度不为零，或 DFS 发现回到当前递归栈的边，说明图中存在环，拓扑序不存在。

展开逻辑：区分有向环与无向图回边，并说明多个入度为零节点时拓扑序可能不唯一。工程依赖图还需报告环的具体路径。

常见追问：为什么 DFS 访问过节点不等于发现环？

易错点：只用 visited 数组而不维护当前路径状态，或把无向图判环规则直接套到有向图。

56. 最短路算法如何按边权选择？

问题意图：检查图算法的适用条件。

30 秒回答：无负权时可用 Dijkstra；边权为 -1、0、1 等特殊范围可用相应队列优化；允许负权但无负环时可用 Bellman-Ford，检测到可继续松弛的负环则最短路无定义。全对可用 Floyd-Warshall。

展开逻辑：Dijkstra 的贪心前提是已确定距离不会被负边降低。选择时还要考虑稀疏/稠密图、单源/多源和内存规模。

常见追问：为什么 Dijkstra 不能直接处理负边？

易错点：忽略负环、把 BFS 用于任意权重图，或混淆最短路径和最小生成树。

57. 二叉堆为什么适合实现优先队列？

问题意图：考查堆的结构和复杂度。

30 秒回答：二叉堆是完全二叉树，用数组存储并满足父节点优先级不低于子节点；查看最小/最大值 O(1)，插入和删除堆顶 O(log n)，建堆可在线性时间完成。它不保证中序有序。

展开逻辑：上滤用于插入，下滤用于删除或调整；数组父子下标公式要统一从零还是一开始。需要稳定排序或任意元素快速查找时应选其他结构。

常见追问：为什么自底向上建堆是 O(n) 而不是 O(n log n)？

易错点：把堆误认为完全排序数组，或把堆顶删除写成直接替换后不下滤。

59. 外部排序为什么通常采用多路归并？

问题意图：考查内存受限下的 I/O 优化。

30 秒回答：数据无法全部放入内存时，先分块读入、内部排序并写成有序段，再进行多路归并。多路归并减少磁盘往返轮数，缓冲区大小和归并路数要按内存、I/O 带宽和文件系统调优。

展开逻辑：总成本主要由顺序读写和归并趟数决定，不能只看 CPU 比较次数。稳定性、临时文件空间和故障恢复也要纳入设计。

常见追问：为什么随机 I/O 通常比顺序 I/O 更影响外部排序性能？

易错点：把外部排序当成内存排序，或忽略临时段的磁盘容量。

60. 如何为数据结构选择不变量并做边界测试？

问题意图：考查实现正确性和测试方法。

30 秒回答：先写出结构不变量，例如堆序、链表无环、树的平衡条件和哈希表探测规则，再覆盖空结构、单元素、满容量、重复值、极端键和错误操作。每次修改后用断言和随机对拍检查不变量。

展开逻辑：把接口前置条件、后置条件和资源所有权写清楚，区分逻辑错误、整数溢出和并发竞态。性能测试应与正确性测试分开并记录数据规模。

常见追问：为什么随机测试不能替代针对性边界测试？

易错点：只测正常路径，或用结果样例而不验证结构内部不变量。