简介这份doc文档收录数据结构与算法期中练习题参考答案适合正在复习期中考试的高校计算机专业学生及自学者使用。内容覆盖基本概念、线性结构、栈和队列、二叉树、稀疏矩阵等核心章节既有时间复杂度和空间复杂度的概念辨析也有顺序表插入、二叉树编号、循环队列元素个数等典型计算题可帮助读者巩固知识点并对照自测。包内为单个doc文件压缩包大小318KB内容集中便于直接打开查看。目前已有127人学习适合考前快速过一遍易错点与答题思路或作为平时作业的参考核对。通过该文档的答案与关键计算步骤可重点理解链表指针修改、静态链表增删、稀疏矩阵三元组表转换等较易失分题型在实际解题时更快抓住解题切入点。1. 拿到这份数据结构与算法期中练习题答案.doc先别急着背它到底能帮你什么期中考试前很多人手上都有一份《数据结构与算法期中练习题答案.doc》里面通常是一套套选择题、应用题、手写代码题的题目和参考答案。这份文档能帮你快速建立考点地图哪些章节占分高、哪些题型反复出现、标准答案长什么样。但我要先泼一盆冷水doc 里的答案不等于正确答案更不能直接背了上考场。数据结构与算法不是背诵型科目期中考试考的是你能否在限时场景里手写栈、队列、二叉树遍历和排序算法并算对时间复杂度和空间复杂度。把这份答案当参考索引用逐题验证、亲手跑一遍它才有价值。这篇笔记适合正在复习数据结构这门课、考前只有一周时间、想靠练习快速摸清题型的人也适合自己整理过答案但不确定对不对的初学者。我会按怎么拆题、怎么用代码验证、怎么避开 doc 文档的坑来展开。2. 把 doc 里的题按考点拆开数据结构与算法期中到底考什么2.1 从答案反推题型选择题、应用题、手写代码题三类打开任何一份期中练习题答案第一件事不是从头看到尾而是先浏览一遍答案的格式。答案里如果是 A、B、C、D 或“正确/错误”说明这是选择判断题考点集中在定义和性质上答案里如果出现两行式子加一句结论比如“T(n)O(n log n)”“平均查找长度 ASL3.3”说明这是应用题考点在计算答案里如果是一段 C 或 C 代码这就是手写代码题考点在实现能力。我的习惯是把 doc 里的题按这三类重新分堆分堆后复习效率会高很多。选择题靠刷应用题靠算手写代码题靠默写三类题目的复习方式完全不同。选择题考的是概念边界比如栈“后进先出”的具体场景、二叉树第 k 层最多几个结点、哈希表冲突处理的线性探测法应用题考的是计算熟练度比如快速排序在最好和最坏情况下的时间开销手写代码题考的是你会不会把逻辑转成循环和递归。如果你发现这份答案里的选择题占了七成那说明出题老师更看重基础概念如果应用题和代码题占大头就要把重心放到手算和上机验算上。期中考试没有期末那么综合但它的题型和期末高度一致。2.2 时间复杂度与空间复杂度最容易白给分也最容易错的计算点时间复杂度是数据结构和算法里最基础也最容易被忽略的考点。期中考试的选择题第一题大概率是“下面哪个算法的时间复杂度是 O(n²)”这种级别应用题里也常出现“求某段嵌套循环的 T(n)”的题目。我看到很多同学在答案的 doc 里抄“该算法时间复杂度为 O(n)”根本不看循环边界。比如下面这段for (i 1; i n; i * 2) { for (j 0; j n; j) { // 常数操作 } }外层循环每轮 i 加倍循环次数是 log₂(n)内层循环 n 次所以是 O(n log n)不是 O(n)。这种答案在 doc 里经常被写错原因是只看了内层没看外层。验证方法也很简单把 n 从 100 改成 10000跑程序统计基本操作次数看增长倍率是不是接近 log n 的倍率。空间复杂度这里有个常见误区递归算法的空间开销要算上调用栈。期中考试里考斐波那契数列递归实现的空间复杂度答案往往是 O(n)因为递归深度是 n而不是 O(1)。我在 doc 里见过把递归归为 O(1) 的错误答案这是把“变量个数”和“栈帧深度”搞混了。判分时老师看的是你有没有算调用栈这层开销所以拿到答案后把每道算法题的“递归深度”单独标出来比背结论更稳。2.3 线性表、栈与队列数组和链表实现的选择题套路线性表这块期中练习的经典选择题是“数组实现的线性表和链表实现的线性表哪个插入删除更快”。答案通常是“链表插入删除注意别被前一句骗了”。数组插入需要移动元素平均移动 n/2 次链表插入需要先找到前驱结点查找本身是 O(n)。所以严格说在“已知位置”插入链表快在“按值查找后插入”两者都要算查找开销。doc 里如果只写“链表插入快”那是把前提吞了考试时会翻车。栈和队列的考点更固定入栈出栈序列、循环队列的队空队满判断、用栈模拟递归。我建议把答案里的“不可能的出栈序列”类题目全部自己做一遍比如“入栈顺序 1,2,3,4出栈序列可能是 4,3,2,1可能是 2,1,4,3但不可能是 3,1,4,2”。这种情况画个栈的示意图每一步入栈、出栈都标出来答案对不对一眼就能看出。循环队列那类题重点看答案有没有区分“牺牲一个存储单元”的写法很多 doc 里的答案默认队满条件是 (rear1)%maxsizefront但有的教材用 size 计数结果判空判满条件完全不同。3. 用代码验证答案把 doc 里的算法题跑成可执行程序3.1 最小验证环境用 Python 快速搭一个刷题沙箱验证练习题答案最直接的办法是把 doc 里的代码题和结果题重新实现一遍。不一定非要用 C 语言期中考试手写代码可能要求 C但验算用 Python 更快逻辑对了再翻译回 C 也不难。我通常会在本机建一个algo_check/目录每个章节一个.py文件文件名直接写考点比如stack_queue.py、sort_check.py、kmp_next.py。这样复习到最后这个目录就是你的可执行错题本。先搭一个最简环境不需要 IDE命令行能跑python3就行。下面这个脚本是我每次验算前都会先准备的“计时与计数工具”它能帮你看清楚一个算法的基本操作到底执行了多少次import time def count_ops(n, modeloop): ops 0 if mode nested_log: # 对应 O(n log n) 的嵌套循环结构 i 1 while i n: for j in range(n): ops 1 i * 2 elif mode bubble: # 双层循环对应冒泡排序最内层比较次数 for i in range(n): for j in range(n - i - 1): ops 1 return ops for n in [10, 100, 1000]: start time.perf_counter() ops count_ops(n, nested_log) elapsed time.perf_counter() - start print(fn{n}: ops{ops}, time{elapsed:.6f}s)这段代码的逻辑是count_ops里两个分支分别模拟常见双层循环结构nested_log对应外层倍增内层线性的情况bubble对应冒泡排序的比较次数。time.perf_counter()用于测量单次执行耗时但小数据量时计时有抖动所以更可靠的指标是ops的数值。把 n 增大 10 倍看 ops 增长多少倍就能判断复杂度量级。比如nested_log模式下n 从 100 变 1000ops 的增长倍率是 10 再乘 log 关系和理论对得上的话答案就没写错。3.2 暴力枚举与剪枝先跑出正确结果再谈优化期中练习里经常有“给定数组找两个数之和等于目标值”的算法题。常见答案有两种暴力枚举双循环 O(n²)或者用哈希表 O(n)。doc 里通常会给后一种答案但如果你没看懂我建议先把暴力版本写出来结果对了再去优化。暴力枚举是最可靠的参考答案因为它的逻辑简单、不容易错只是慢。下面这段就是一个完整验证def two_sum_bruteforce(nums, target): 暴力枚举所有下标对返回第一对满足条件的下标。 参数 nums: 整数列表target: 目标值。 返回值: [i, j] 或 None。 n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return None def two_sum_hash(nums, target): 哈希表方案把已访问的值存入字典键是元素值值是下标。 每遍历一个新元素只查一次字典总时间 O(n)。 seen {} for idx, val in enumerate(nums): need target - val if need in seen: return [seen[need], idx] seen[val] idx return None test_nums [2, 7, 11, 15] print(two_sum_bruteforce(test_nums, 9)) print(two_sum_hash(test_nums, 9))暴力枚举的逻辑是两层循环把所有下标对都试一遍i从 0 开始j从i1开始保证不重复也不产生自己加自己的情况。哈希表方案的关键在need target - val每轮先查“缺多少”再决定是否把当前值放进去。参数说明nums是无序数组target是目标和返回值统一是下标列表。如果 doc 答案只写了“双指针法”你反而要警惕因为双指针要求数组有序原题没说有序就是坑。这种用暴力验证答案的方式能帮你发现很多“答案本身缺少前提条件”的问题。3.3 KMP 与字符串匹配用答案里的 next 数组反推过程KMP 算法是数据结构里的硬骨头期中考试爱考“求模式串的 next 数组”或“KMP 匹配过程”。doc 里的答案通常直接给一个 next 数组比如模式串ababaa的 next 是011223但很多同学对着答案也不知道怎么算出来的。我的做法是把 next 数组计算过程写成函数让程序自己推导再和 doc 里的答案对比。def build_next(pattern): 计算 KMP 的 next 数组部分匹配值1 的写法。 参数 pattern: 模式串字符串。 返回值: next 列表长度与 pattern 相同。 m len(pattern) next_arr [0] * m next_arr[0] 0 i, j 1, 0 while i m: if pattern[i] pattern[j]: j 1 next_arr[i] j i 1 else: if j 0: j next_arr[j - 1] else: next_arr[i] 0 i 1 # 题目常用 next 数组从 1 开始计数整体后移并补 0 shifted [0] next_arr[:-1] return shifted for p in [ababaa, abaabc, aaaa]: print(p, build_next(p))这段代码的思路是标准 KMP 构造 next 的迭代过程i表示当前要填的位置j表示已匹配的前缀长度。当pattern[i] pattern[j]时前缀长度加一不匹配时j回退到上一轮的部分匹配值而不是直接归零这是 KMP 比暴力匹配高效的核心。最后把结果整体后移一位是因为教材里 next 数组下标从 1 开始且 next[1]0很多答案文档用的是这种写法。参数说明传入的pattern是模式串返回的shifted是教材版 next 数组。如果跑出来的结果和 doc 不一致先检查 doc 里的写法是从 0 还是从 1 开始这是 KMP 答案最容易错位的地方。4. 期中算法题的 3 类典型答案校正排序、递归、图遍历4.1 排序算法用测试用例检验答案的排序稳定性和边界行为期中考试的排序题经常是“给一组数写出快速排序第一趟结果”或“冒泡排序每一趟的结果”。doc 里的答案常常只给最终排序结果丢了中间过程这对复习没多大帮助。我一般会让程序把每趟排序后的数组打出来和手算答案对拍。另一个容易出错的是稳定性冒泡排序稳定快速排序不稳定选择排序不稳定归并排序稳定。答案里如果写“选择排序是稳定的”那直接可以判定错误。用下面这段代码可以同时验证排序结果和中间过程def bubble_sort_with_trace(arr): 冒泡排序每一轮的结果都记录下来用于和练习题答案对拍。 参数 arr: 待排序列表函数会修改原列表。 返回: 每一轮结束后的列表快照。 n len(arr) traces [] for i in range(n): swapped False for j in range(n - i - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True traces.append(list(arr)) if not swapped: break return traces data [5, 1, 4, 2, 8] for idx, snapshot in enumerate(bubble_sort_with_trace(data)): print(f第{idx 1}轮: {snapshot})这段代码的逻辑是每一轮把相邻逆序元素交换n - i - 1是因为第 i 轮结束后数组尾部已经有 i 个元素排好。swapped是提前退出标记如果一轮下来没有发生交换说明数组已经有序后面的轮次不用再跑。返回值traces是每轮快照方便对比 doc 里的手算过程。参数说明arr是原列表函数会原地修改如果想要不修改原列表调用前先传data[:]。这种对拍方式能快速揪出“答案漏写一轮”或“交换次数数错”的问题。4.2 递归与分治写出可复现的递归树别只背返回值递归题是期中考试应用题的重灾区尤其是“求斐波那契第 n 项”“二分查找比较次数”“汉诺塔移动次数”。doc 里的答案往往只写一个数字比如“递归调用 5 次”但不画递归树。遇到这种题我会用带缩进的递归日志把调用过程打出来这样既能验证次数也能看清递归深度是不是和答案一致。def fib_trace(n, depth0): 打印斐波那契递归调用的树形结构。 参数 n: 当前要求的项depth: 递归深度用于缩进显示。 返回: 斐波那契第 n 项的值。 indent * depth print(f{indent}fib({n})) if n 1: return n return fib_trace(n - 1, depth 1) fib_trace(n - 2, depth 1) print(结果:, fib_trace(5))输出会清晰显示fib(5)调用了fib(4)和fib(3)fib(4)又调用fib(3)和fib(2)以此类推。这个打印逻辑本身不改变递归计算只是把进入函数时的参数和深度打印出来。参数说明n是第几项depth是递归深度只在调试时用正常调用不需要传。如果 doc 答案说“斐波那契递归总调用次数是 15 次”你跑一下fib(5)数一数打印行数马上知道对不对。另一个注意点是递归深度等于最大缩进层数这个值也决定了空间复杂度期中考试考过“递归求斐波那契的空间复杂度”答案就是 O(n)。4.3 图的遍历与最短路径手算答案与程序结果对拍图这块期中练习常见考点是“深度优先遍历序列”“广度优先遍历序列”和“迪杰斯特拉求最短路径”。doc 里的答案通常是一串顶点序列。这里有个很大的坑图的邻接表存储时如果每个顶点的邻接点顺序不一样遍历结果就不同。答案文档如果没给出图的存储结构那遍历序列就不是唯一的。所以拿到图遍历答案先看 doc 里的图长什么样、邻接表怎么排的再写程序验证。下面是一个用邻接表做 DFS 的验证脚本重点是看遍历顺序是否与答案一致from collections import defaultdict def dfs_order(graph, start): 深度优先遍历按邻接点顺序输出顶点序列。 参数 graph: 字典键是顶点值是邻接点列表start: 起点。 返回: 遍历序列列表。 visited set() order [] def dfs(v): visited.add(v) order.append(v) for nxt in graph[v]: if nxt not in visited: dfs(nxt) dfs(start) return order # 这是一个有向图邻接表人为规定每个顶点的邻接点顺序 g defaultdict(list) edges [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)] for u, v in edges: g[u].append(v) # 为每个顶点的邻接点排个固定顺序 g[1] [2, 3] g[2] [4] g[3] [4] g[4] [5] print(dfs_order(g, 1))这段代码的逻辑是dfs函数先把自己加入visited再按邻接表顺序递归访问未访问的邻接点。defaultdict(list)保证不存在的键也能直接 append。参数说明graph的键值对顺序会直接影响输出序列所以我在构建完边之后又手动覆盖了g[1]、g[3]的顺序目的就是明确“答案基于什么样的邻接表”。如果 doc 答案的 DFS 序列和程序输出不一样不要急着说答案错先检查邻接点顺序把文档里邻接表的列出来跟着走一遍大部分矛盾出在邻接表顺序而不是算法本身。5. 避坑这份练习答案 doc 里常见的 5 个坑从乱码到错误结论5.1 现象doc 打开后公式乱码、下划线错位答案里的时间复杂度看不清原因很直接doc 是老式 Word 格式公式、特殊符号比如 O(n²)、队列指针的箭头、树的结构图在 WPS 或新版 Office 里渲染不一致。我见过一份答案里的O(log n)显示成了O(logn)也有人把front rear看成front ! rear。 解决方法先别做题把文档另存为 PDF 或者用 LibreOffice 转成 docx 再打开至少保证符号正常显示。如果公式还是乱就自己按“时间复杂度章节”重新整理一份清单把每题的答案手抄一遍这步花不了 20 分钟但能救回很多误判。5.2 现象答案只有最终结论没有推导过程比如“平均查找长度 ASL 7/3”这是练习答案的老毛病尤其是应用题和判断题。原因通常是出题人默认读者已经会推了但恰恰是推导过程才是考试给分点。解决方式是把这类题单独标记自己补推导比如哈希表线性探测的 ASL要写出每个关键字的探测次数再求平均。补完推导后用 3.2 节的暴力枚举思想写一个小程序模拟哈希插入验证 ASL 对不对。这一步能帮你把“背答案”变成“会算”。5.3 现象答案版本与教材不匹配比如 next 数组有两种定义KMP 的 next 数组、循环队列的队满条件、二叉树高度的定义根节点高度是 0 还是 1不同教材写法不同。我在实践中遇到过答案是“模式串 next 为 011234”另一本教材的答案是“010120”两边都没错只是定义不同。解决方法是先确认老师课上用哪种约定再决定是否采纳 doc 里的答案。如果 doc 没标明教材版本就按“从 0 开始”和“从 1 开始”各算一遍然后在文档首页写下你采用的约定避免考前混乱。5.4 现象手写代码题答案用的是 C 语言但函数名、返回值都不可运行有的答案文档代码是从网上摘的头文件缺失scanf和printf混用甚至main函数都没有。原因是作者只复制了核心函数删掉了运行上下文。解决方法是把每个代码题补成一个能直接编译运行的完整小程序。我一般用 Python 重写逻辑因为代码短、无头文件烦恼等逻辑验证完再按 C 语言格式手写一遍到笔记本上。不要直接背网上的不完整代码考试时随手写出来的很容易在边界条件上翻车。5.5 现象答案在常规数据下正确但没考虑空表、满栈、单结点树等边界这是最危险的一类错误。比如“删除单链表中某个结点”的答案只写了常规情况的指针修改没写删除头结点时怎么办“二分查找”只写了普通情况没写 low 和 high 的更新边界。原因就是出题人自己也没跑过极端用例。解决方式是拿到一个算法答案后主动构造 3 个边界用例空输入、只有一个元素、重复元素。把这些用例跑到程序里只要有一个报错或结果不对就说明答案不完整。我也是这么干的这比通读十遍答案都有效。6. 把练习题答案变成自己的错题本一份可复查的期中复习清单最后一章我建议你做一件比“刷完整个 doc”更有用的事把这份答案文件变成你自己的错题本。具体做法是建一个表格三列题目来源、我的答案是否正确、错误原因归类。错误原因不要写“粗心”要写具体类型比如“没判断链表为空”“时间复杂度少算了外层循环”“KMP next 数组起始下标搞混”。这样考前最后一天只看这个表格的错误原因列表就能快速定位薄弱点。这个错题本还可以配合第 3 章的沙箱目录使用。每个章节一个文件文件顶部写清该章节的考点和踩坑记录。比如sort_check.py顶部写“快速排序不稳定选择题别选稳定”kmp_next.py顶部写“本项目采用 next 从 1 开始另一本书从 0 开始考试先看题目约定”。复习时打开这些文件跑一遍验证脚本再翻错题本比从头看 doc 快得多。我自己的教训是期中复习最忌讳从头到尾再读一遍答案文档那样会重复巩固错误。只有把每题答案过一遍程序验证错误才会真正暴露。希望这份笔记能帮你在复习周少踩几个坑把时间花在真正会考的算法和数据结构上。本文还有配套的精品资源点击获取