1. 为什么你需要这份习题答案从“会做题”到“会思考”的跨越如果你正在啃严蔚敏老师的《数据结构C语言版》并且翻到了第八章那你大概率正处在一个关键的爬坡期。这本书的习题尤其是第八章的题目向来以“概念深、综合性强、代码实现细节多”著称。很多同学拿到题目要么感觉无从下手要么写出的代码漏洞百出调试半天也找不到原因。这时候一份靠谱的习题答案其价值远不止于“对答案”那么简单。它更像是一位经验丰富的“陪练”在你独立思考和尝试之后为你提供解题思路的验证、代码实现的参考以及更重要的——帮你理解题目背后数据结构设计的精妙之处完成从“看懂书”到“会做题”再到“会思考”的质变。第八章“查找”是整个数据结构课程中承上启下的核心章节。它不像线性表、栈队列那样直观也不如图、排序那样复杂但它将前面学到的线性结构、树形结构如二叉排序树与算法效率分析时间复杂度、空间复杂度紧密结合是检验你是否真正理解数据结构“为何存在”以及“如何应用”的试金石。本章的习题往往不是让你简单调用一个search函数而是要求你深入理解顺序查找、折半查找、分块查找、二叉排序树、平衡二叉树AVL树、B树、B树以及哈希表等各种查找结构的内在逻辑、适用场景、性能边界和实现细节。因此这份“最详细”的答案其目标不是给你一个可以照抄的代码文本而是致力于为你拆解每一道题目的设计意图、核心考点、实现难点以及常见的思维陷阱。我会假设你已经对课本内容有了基本了解但可能在将理论转化为代码、处理边界条件、进行效率优化时遇到了障碍。接下来我们将不按简单的题号顺序罗列而是根据知识模块和难度进阶重新组织这些习题带你进行一场深度的“查找”专题训练。2. 静态查找表算法思想与效率分析的基石第八章开篇的习题多围绕静态查找表即查找过程中数据集合不变展开重点是吃透不同查找算法的思想并能够严谨地分析其性能。这是后续学习更复杂动态查找结构的基础。2.1 折半查找的递归与非递归实现对比课本介绍了折半查找的非递归算法但习题中常要求实现其递归版本并比较两者优劣。题目示例编写折半查找的递归算法。核心考点递归思想的运用、函数参数的设计需要传递查找区间的上下界、递归终止条件的准确把握。详细答案与解析// 假设数据存储在整型数组 a 中下标从 1 到 n与严蔚敏书中约定一致key 为待查找值 int BinSearch_Recursive(int a[], int low, int high, int key) { // 递归终止条件查找区间无效 if (low high) { return 0; // 返回 0 表示查找失败书中常用 0 作为无效下标 } int mid (low high) / 2; // 计算中间位置 if (key a[mid]) { return mid; // 查找成功返回元素位置 } else if (key a[mid]) { // 关键点在左半区间继续查找区间变为 [low, mid-1] return BinSearch_Recursive(a, low, mid - 1, key); } else { // 在右半区间继续查找区间变为 [mid1, high] return BinSearch_Recursive(a, mid 1, high, key); } }调用方式int pos BinSearch_Recursive(a, 1, n, key);为什么这样设计参数low和high这是递归的核心。每一次递归调用查找区间都在缩小必须通过参数明确传递当前的区间范围。如果只传数组和key递归将无法进行。终止条件low high这表示搜索区间已为空没有元素可查。这是折半查找失败的唯一标准条件必须放在函数开头进行判断。时间复杂度与空间复杂度分析时间复杂度与非递归版本一样都是O(log₂n)。因为每次递归都将问题规模减半。空间复杂度递归版本需要系统栈来保存每一层递归的调用信息参数、返回地址等。在最坏情况下查找失败到最深层递归深度为树的高度即O(log₂n)。这是与非递归版本空间复杂度O(1)的主要区别。对于极大的n递归可能导致栈溢出而非递归版本则无此风险。实战心得在真正写代码时要特别注意mid的计算是否会导致整数溢出。当low和high都是很大的整数时(low high)可能会超出整型范围。更安全的写法是int mid low (high - low) / 2;。虽然课本习题数据量通常不大但养成这个习惯在工程实践中至关重要。2.2 判定树与平均查找长度ASL的计算这是必考的理论计算题要求根据给定的查找算法或数据特性画出判定树并计算成功和不成功情况下的平均查找长度。题目示例对长度为 n 的有序表进行折半查找试求其成功和不成功时的平均查找长度分别用 ASLsucc 和 ASLunsucc 表示。核心考点判定树的概念、二叉树的性质、查找长度定义的理解。详细答案与解析 折半查找的判定树是一棵平衡二叉树注意不是AVL树但形态上是平衡的。对于有 n 个结点的判定树树高 h ⌈log₂(n1)⌉。成功ASL (ASLsucc)等于每个结点查找成功所需的比较次数即该结点在树中的层数乘以该结点被查找的概率然后对所有结点求和。假设每个元素被查找的概率相等均为 1/n。第 i 层上的结点数最多为 2^(i-1) 个。查找第 i 层上的结点恰好需要 i 次比较。因此ASLsucc ≈ (1/n) * Σ( i * 第 i 层结点数 )。当 n 很大时可以近似为ASLsucc ≈ log₂(n1) - 1。更精确的公式需要根据 n 的具体值构造判定树后累加计算课本中有详细推导。不成功ASL (ASLunsucc)折半查找失败的过程最终会停留在判定树的空指针域即叶子结点的子结点上。这些空指针域有 n1 个。假设失败落在每个空指针域的概率相等。需要计算从根结点到每个失败结点空指针域的路径长度比较次数。对于树高为 h 的判定树失败结点只可能出现在第 h 层或第 h-1 层。ASLunsucc (1/(n1)) * Σ( 失败结点的父结点所在层数 )。通常ASLunsucc 也近似于 O(log₂n)。避坑指南混淆结点一定要区分“数据结点”和“失败结点”。失败结点不是实际存在的数据而是查找路径的终点。概率假设计算ASL的前提是“等概率”查找。如果题目未说明通常默认为等概率。若概率不等则需要使用加权求和。实战技巧对于具体的 n比如12最快的方法是亲手画出一棵对应的判定树在结点上标出对应的数组下标或值在空指针处标出失败区间。然后数一数每一层有几个结点/失败点直接套公式计算。这个过程能极大地加深你对折半查找过程的理解。3. 动态查找结构二叉排序树与平衡化实战从二叉排序树BST开始查找结构进入“动态”领域即查找过程中可以方便地插入和删除元素。这里的习题开始涉及复杂的指针操作和树形结构的维护。3.1 二叉排序树的插入、删除与性能分析题目示例编写算法在二叉排序树中查找值为 key 的结点并删除之。核心考点二叉排序树的性质、删除操作的三种情况分类讨论、指针修改的细节。详细答案与解析 删除二叉排序树中的结点是本章的难点之一必须分情况处理待删除结点是叶子结点直接将其父结点对应的指针置为NULL然后释放该结点。待删除结点只有左子树或只有右子树让其父结点指向它的左孩子或右孩子然后释放该结点。这相当于“绕过”了该结点。待删除结点既有左子树又有右子树这是最复杂的情况。为了保证删除后仍保持二叉排序树的性质需要找到该结点的直接前驱或直接后继来替代它。直接前驱是其左子树中的最大结点即左子树中最右下角的结点。直接后继是其右子树中的最小结点即右子树中最左下角的结点。通用策略常用直接前驱替代。即用直接前驱的值覆盖待删除结点的值然后问题转化为删除那个直接前驱结点。由于直接前驱结点至多只有一个左孩子因为它已经是最大的了所以删除它又回到了情况1或情况2变得简单。代码框架与关键点typedef struct BSTNode { int data; struct BSTNode *lchild, *rchild; } BSTNode, *BSTree; // 删除二叉排序树中值为key的结点 Status DeleteBST(BSTree *T, int key) { if (!*T) return FALSE; // 树空或未找到 else { if (key (*T)-data) { // 找到执行删除操作 return DeleteNode(T); } else if (key (*T)-data) { // 在左子树中继续查找 return DeleteBST((*T)-lchild, key); } else { // 在右子树中继续查找 return DeleteBST((*T)-rchild, key); } } } // 删除结点p并重接其左右子树 Status DeleteNode(BSTree *p) { BSTree q, s; if (!(*p)-lchild !(*p)-rchild) { // 情况1叶子结点 free(*p); *p NULL; } else if (!(*p)-rchild) { // 情况2只有左子树 q *p; *p (*p)-lchild; free(q); } else if (!(*p)-lchild) { // 情况2只有右子树 q *p; *p (*p)-rchild; free(q); } else { // 情况3左右子树均存在 // 寻找直接前驱即左子树的最右下结点 q *p; s (*p)-lchild; while (s-rchild) { q s; // q记录s的父结点 s s-rchild; } // 此时s指向被删结点的直接前驱 (*p)-data s-data; // 用前驱的值覆盖待删除结点的值 if (q ! *p) { // 说明直接前驱不是待删结点的直接左孩子 q-rchild s-lchild; // 重接q的右子树 } else { // 说明直接前驱就是待删结点的左孩子即左孩子没有右子树 q-lchild s-lchild; // 重接q的左子树 } free(s); } return TRUE; }为什么指针参数是BSTree *T因为删除操作可能需要修改根结点的指针例如删除根结点本身。使用二级指针或C中的引用BSTree T可以在函数内部直接修改调用者传来的树指针。这是C语言处理这类问题的常见技巧。性能分析与实战心得 二叉排序树的查找、插入、删除操作的时间复杂度高度依赖于树的形态。在最好情况树完全平衡下时间复杂度为O(log n)。但在最坏情况树退化成一条链例如插入有序序列下时间复杂度会退化到O(n)。这正是引入平衡二叉树AVL树的根本原因。在习题中如果要求你分析一组特定序列构成的BST的性能一定要先画出这棵树直观判断其平衡程度。3.2 平衡二叉树AVL树的旋转操作理解AVL树是BST的优化通过旋转操作保持树的平衡。习题通常要求画出插入/删除某个结点后AVL树如何通过旋转重新平衡。题目示例依次将关键字序列 {16, 3, 7, 11, 9, 26, 18, 14, 15} 插入到一棵初始为空的AVL树中画出每插入一个关键字后的AVL树形态。核心考点平衡因子的计算、四种旋转类型LL, RR, LR, RL的判断与实现。详细答案与解析 这道题是经典的AVL树构建练习。解题的关键在于每插入一个结点后从该结点向根回溯找到第一个失去平衡的祖先结点记为A然后根据A的平衡因子以及导致不平衡的插入位置判断旋转类型。旋转类型判断口诀LL型右单旋在A的左孩子(L)的左子树(L)插入导致不平衡。解决对A进行一次右旋。RR型左单旋在A的右孩子(R)的右子树(R)插入导致不平衡。解决对A进行一次左旋。LR型先左后右双旋在A的左孩子(L)的右子树(R)插入导致不平衡。解决先对A的左孩子进行左旋转化为LL型再对A进行右旋。RL型先右后左双旋在A的右孩子(R)的左子树(L)插入导致不平衡。解决先对A的右孩子进行右旋转化为RR型再对A进行左旋。逐步插入过程简述关键步骤插入1637插入7后根结点16的平衡因子为-2左子树高且是左孩子(3)的右子树插入属于LR型。需先左旋3再右旋16。插入11此时树是平衡的。插入9插入9后结点7的平衡因子为-2是左孩子(3)的右子树插入注意这里的“左孩子”是相对于失衡结点7而言的其左孩子是3但3的右子树是119插在11的左子树上这里需要仔细画图。实际上插入9导致结点16失衡平衡因子为-2且是左孩子(7)的左子树插入不对7的右子树有119插在11的左边。所以对于结点16失衡是由左孩子(7)的右孩子(11)的左子树插入引起的属于LR型对16而言。需要从下往上找到第一个失衡结点。...后续插入类似分析避坑指南与心得回溯找A一定要从新插入的结点开始沿着父指针向上计算每个祖先结点的平衡因子找到第一个|bf| 1的结点它就是失衡结点A。不要凭感觉猜。判断类型确定A后看导致A失衡的子树是A的哪个孩子L还是R再看新结点是插在这个孩子的哪个子树L还是R。组合起来就是LL, LR, RL, RR。画图画图画图这是解决所有AVL树习题最有效的方法。在纸上一步步画旋转前后对比理解指针是如何改变的。光靠脑子想很容易乱。代码实现的心得AVL树的旋转代码并不长但指针操作极其容易出错。在写代码时建议先用纸笔画好旋转前后的拓扑图标出需要修改的指针通常是3-4个然后按照固定顺序例如先处理子结点再处理父结点编写代码并立刻进行简单的测试如手动模拟一个LL或RR情况。4. 哈希表冲突处理与性能估算的工程思维哈希表是另一种重要的查找结构它通过哈希函数将关键字映射到存储地址理想情况下能达到O(1)的查找时间。本章习题重点考察哈希函数的构造、冲突处理的方法以及查找效率的分析。4.1 哈希函数构造与冲突处理算法实现题目示例设哈希表长为11哈希函数为 H(key) key % 11采用线性探测再散列处理冲突。试在0~10的散列地址空间中对关键字序列 {22, 41, 53, 46, 30, 13, 01, 67} 构造哈希表并求在等概率情况下查找成功和不成功的平均查找长度。核心考点哈希函数计算、线性探测法、ASL的计算哈希表下的ASL计算与树不同。详细答案与解析步骤一构造哈希表关键字2241534630130167H(key)08928211插入22H(22)0地址0空放入。插入41H(41)8地址8空放入。插入53H(53)9地址9空放入。插入46H(46)2地址2空放入。插入30H(30)8地址8已被41占用发生冲突。采用线性探测检查地址9已被53占地址10空所以30放入地址10。探测次数为2检查了8和9最后放在10。插入13H(13)2地址2已被46占用冲突。线性探测地址3空所以13放入地址3。探测次数为2。插入01H(01)1地址1空放入。插入67H(67)1地址1已被01占用冲突。线性探测地址2被46占地址3被13占地址4空所以67放入地址4。探测次数为3。最终哈希表如下/表示空地址012345678910关键字2201461367///415330步骤二计算成功时的平均查找长度ASLsucc查找成功时需要计算找到表中每个已有关键字所需的比较次数即探测次数。22H(22)0一次命中比较1次。41H(41)8一次命中比较1次。53H(53)9一次命中比较1次。46H(46)2一次命中比较1次。30H(30)8冲突比较了地址8、9最后在10找到比较3次。13H(13)2冲突比较了地址2、3在3找到比较2次。01H(01)1一次命中比较1次。67H(67)1冲突比较了地址1、2、3、4在4找到比较4次。总比较次数 11113214 14 ASLsucc 总比较次数 / 关键字个数 14 / 8 1.75步骤三计算不成功时的平均查找长度ASLunsucc查找不成功时意味着待查关键字不在表中。我们需要计算对于每个哈希地址按照冲突解决策略需要比较多少次才能确定“查找失败”。这是哈希表ASL计算的难点。 对于线性探测法查找失败时从哈希地址开始一直向后探测直到遇到一个空位置才确认失败。注意比较次数包括最后与空位置的比较。假设哈希函数值域为0~10表长11我们计算每个地址H(key)下查找失败的比较次数地址0探测0若为空则失败1次若不为空是22则继续探测1。探测1若为空则失败。所以需要一直探测到空位。从地址0开始0(22)-1(01)-2(46)-3(13)-4(67)-5(空)。比较了6次才遇到空位地址5。地址1从1开始1(01)-2(46)-3(13)-4(67)-5(空)。比较了5次。地址2从2开始2(46)-3(13)-4(67)-5(空)。比较了4次。地址3从3开始3(13)-4(67)-5(空)。比较了3次。地址4从4开始4(67)-5(空)。比较了2次。地址5从5开始5(空)。比较了1次。地址6从6开始6(空)。比较了1次。地址7从7开始7(空)。比较了1次。地址8从8开始8(41)-9(53)-10(30)-0(22)-1(01)-2(46)-3(13)-4(67)-5(空)。比较了9次。注意线性探测是循环的从8走到表尾10后回到表头0继续地址9从9开始9(53)-10(30)-0(22)-1(01)-2(46)-3(13)-4(67)-5(空)。比较了8次。地址10从10开始10(30)-0(22)-1(01)-2(46)-3(13)-4(67)-5(空)。比较了7次。总失败比较次数 65432111987 47 ASLunsucc 总失败比较次数 / 哈希函数值域大小 47 / 11 ≈ 4.27为什么ASLunsucc这么高这是因为线性探测法容易产生“堆积”现象即冲突的记录会连成一片。一旦发生冲突后续的探测路径会变长极大地影响了失败查找的性能。这也说明了为什么在实际工程中当哈希表填充因子元素数/表长较大时线性探测的性能会急剧下降通常需要扩容rehashing。实战心得与不同冲突处理方法对比线性探测实现简单但容易产生堆积ASLunsucc可能很高。平方探测可以缓解堆积但表长必须为4k3型的素数时才能探测到所有位置。再哈希法需要设计多个哈希函数计算开销稍大。链地址法这是最常用且稳定的方法。将冲突的记录放在同一个链表中。ASLsucc ≈ 1 α/2α为装载因子ASLunsucc ≈ α e^(-α)。性能优于开放定址法且处理删除操作更简单。在习题中如果采用链地址法ASL的计算就变成了计算在每个链表中查找的平均长度。5. 综合应用与算法设计从理论到代码的桥梁第八章的最后部分习题往往更具综合性可能要求你设计一个结合多种查找思想的算法或者解决一个实际背景的查找问题。这部分最能体现你对本章知识的融会贯通能力。5.1 利用B树/B树特性设计文件索引系统题目示例思想延伸简述为何在数据库索引和文件系统中大量使用B树或B树而不是二叉排序树或AVL树核心考点B树/B树与内存查找树的本质区别、磁盘I/O特性对数据结构选择的影响。详细答案与解析 这是一个经典的面试题和思考题。其核心原因在于计算机存储系统的层次结构和磁盘I/O的高成本。磁盘I/O与数据局部性磁盘尤其是机械硬盘的读写以“页”Page通常为4KB或更大为单位且随机访问速度极慢寻道时间旋转延迟。相比之下内存访问速度极快。因此减少磁盘I/O次数是设计外存磁盘数据结构的第一要务。二叉树的“瘦高”问题二叉排序树或AVL树每个结点通常只存储一个关键字和两个指针。对于海量数据比如10亿条记录树会变得非常“高”。查找一个关键字可能需要访问树高O(log₂n)个结点。如果每个结点存储在不同的磁盘页中就意味着需要数十次磁盘I/O这是无法接受的。B树的“矮胖”优势B树的一个结点可以存储多个关键字和对应的指针。一个结点的大小正好设计成一个磁盘页的大小。这样一次磁盘I/O就可以读入一个包含大量关键字的结点。虽然B树的结点内可能需要顺序或折半查找但这发生在内存中成本可忽略不计。由于每个结点的分支数阶数m很大所以B树非常“矮胖”树高很低O(logₘn)。对于10亿条记录如果B树的阶数m200树高可能只有4-5层这意味着最多只需要4-5次磁盘I/O就能找到目标性能提升是数量级的。B树相对于B树的优势B树在B树基础上做了优化非叶子结点仅存索引不存实际数据记录只存关键字和子指针。这使得一个结点能容纳更多的关键字进一步降低树高。叶子结点链表串联所有叶子结点包含全部关键字信息并且按大小顺序链接成一个链表。这使得范围查询如查找20到100之间的所有记录效率极高只需要找到起始点然后顺着链表遍历即可。而在B树中范围查询可能需要在不同层级的结点间反复跳跃效率低下。更稳定的查询效率B树任何查找都必须走到叶子结点路径长度相同查询性能稳定。代码设计启示虽然课后习题不要求实现完整的B树但理解其插入、删除、分裂、合并的过程至关重要。在实现时关键结构体可能如下#define M 5 // B树的阶根据磁盘页大小和关键字大小计算得出 typedef struct BTreeNode { int keyNum; // 结点中当前关键字个数 int keys[M]; // 关键字数组实际使用[0..keyNum-1] struct BTreeNode *children[M1]; // 孩子指针数组比关键字多一个 bool isLeaf; // 是否为叶子结点 } BTreeNode;插入一个关键字时如果结点已满keyNum M-1就需要进行分裂。这是B树实现中最复杂的部分需要仔细处理关键字的上移和孩子指针的重新分配。5.2 哈希表与链地址法处理重复关键字题目示例假设某查找系统允许关键字重复请设计一个基于哈希表链地址法的查找算法要求能够返回所有匹配的关键字记录。核心考点链地址法的实际应用、如何处理冲突链表中的多个相同关键字。详细答案与解析 在标准链地址法中冲突的关键字被链接在同一个哈希地址的链表上。如果允许重复那么链表上就可能存在多个结点的key值相同。我们的查找算法需要找出所有匹配的结点。数据结构设计typedef struct Record { int key; // ... 其他数据字段 ... struct Record *next; } Record, *RecordList; RecordList hashTable[TABLESIZE]; // 哈希表每个元素是一个链表头指针查找算法设计// 查找所有关键字为key的记录并将它们存入结果数组result[]中返回找到的记录数 int SearchAll(RecordList hashTable[], int key, Record *result[], int maxResults) { int count 0; int addr Hash(key); // 计算哈希地址 Record *p hashTable[addr]; // 指向该地址的链表头 while (p ! NULL count maxResults) { if (p-key key) { result[count] p; // 找到一条记录存入结果数组 } p p-next; } return count; // 返回找到的记录数量 }为什么这样设计返回所有结果算法遍历整个冲突链表将所有key匹配的结点指针收集起来。这是与不允许重复的查找找到第一个就返回的核心区别。使用结果数组通过参数result数组和maxResults上限将找到的记录返回给调用者。这种方式比在函数内部动态分配内存更安全、接口更清晰。调用者需要预先分配足够大的数组。时间复杂度平均情况下ASL仍然接近O(1α)但最坏情况所有关键字都冲突会退化到O(n)。对于重复关键字的查找平均需要遍历α个结点链表平均长度并在其中找出所有匹配项。进阶思考插入与删除插入允许重复时插入操作变得简单直接采用头插法或尾插法将新记录添加到对应链表的头部或尾部即可无需判断是否已存在。删除删除操作则需要小心。如果要删除所有关键字为key的记录就需要遍历整个链表进行删除。如果只删除其中一个则需要指定额外的条件如时间戳、唯一ID等。这份针对严蔚敏《数据结构》第八章习题的深度解析旨在穿透“答案”本身揭示每一类题目背后的数据结构思想、算法逻辑和实现细节。真正的掌握不在于记住这些代码和步骤而在于理解每一步“为什么这么做”以及“换一种条件该怎么做”。当你再遇到新的查找问题时能够清晰地判断该选用顺序查找、折半查找、二叉排序树、AVL树、B树还是哈希表并清楚每一种选择背后的代价与收益那才是真正学懂了这一章。