★ FEATURED ARTICLE 简介这是一份湖北大学2022—2023学年第一学期《数据结构》期末试卷A卷闭卷适合计算机相关专业本科生期末复习、考研自测及教师命题参考。试卷围绕图论关键路径、栈的出栈序列判断、平均查找长度、二叉树遍历与还原、递归函数实现、链栈存储选择、特殊矩阵压缩等核心考点设置判断分析、简答与应用分析三类题型既考查概念理解也要求动手计算与算法推演。资源为单个PDF文件共252KB内容清晰便于打印或电子阅读。目前已吸引375人学习浏览是梳理数据结构重点、检验掌握程度的实用资料。通过练习可熟悉常见题型和解题思路强化对图、查找、树、递归及存储结构等章节的理解适合考前集中刷题与查漏补缺。1. 数据结构期末试卷不是背课本而是拆卷子某高校的《数据结构》期末试卷每年都有一批学生考前背了半本教材最后却在算法设计题上翻车。我见过不少同学能把排序的时间复杂度背得滚瓜烂熟但一到手写代码就卡壳也有人刷了十套卷子结果遇到“删除链表中倒数第N个节点”还是挂在了边界条件上。实际上数据结构期末试卷考的不是记忆而是两种能力把抽象结构映射成可运行代码以及把复杂度分析写清楚。这篇文章完全围绕“某高校《数据结构》期末试卷”这类考试展开从题型拆解到算法题得分点再给你几条能直接照做的避坑建议。不管你是第一次考还是补考按这个思路拆卷子方向不会偏。2. 试卷题型拆解分值分布与命题逻辑某高校的《数据结构》期末试卷题型一般分为选择题、应用题包括手动模拟和简答、算法设计题三大类。分值比例通常选择题占20%~30%应用题占30%~40%算法设计题占30%~40%。这只是一个大致区间有的年份会把应用题里的“画图题”单列有的年份会把“阅读程序写结果”也放进来。所以你拿到卷子先浏览一遍把题型数量和分数标在题干旁边再决定时间分配。2.1 选择题概念题为什么总丢分选择题是整张卷子里最“杂”的部分。你以为自己背住了概念但实际上丢分的往往是那些“追反例”的题目。丢分原因之一是只记住了定义的关键词但没有理解边界。比如“二叉树是每个节点最多有两个子树的树”这句话是对的但反过来“度为2的树也是二叉树”就是错的因为度为2的树要求每个节点恰好有两个子节点而二叉树允许空子树。复习时要把每个定义都做“正向”和“反向”两种表述正向成立不代表反向成立。丢分原因之二是混淆相似结构。比如“循环队列”和“队列”的区别循环队列是为了解决假溢出入队出队用取模。题目问“循环队列队满条件是什么”时如果你只记得front rear就会掉坑因为空和满都可能出现这个条件所以需要牺牲一个元素位来区分。这类题需要亲手把入队出队流程画几遍而不是背公式。丢分原因之三是复杂度判断凭感觉。选择题常给一个代码片段问你时间复杂度。比如for i in range(n): for j in range(i, n):这个双重循环内层循环次数是n-i总数是n (n-1) ... 1所以是 O(n^2)。但有些同学看到双重循环就写 O(n^2)却不看内层是否总是从固定值开始。正确的做法是在草稿纸上写出迭代次数总和而不是只看循环嵌套层数。为了应对选择题我建议建立一张“结构-操作-复杂度”表格把线性表、栈、队列、串、树、图、散列表的关键操作都列出来。复习时用手遮住内容自己推复杂度推不出来就翻书。这样最后几天你可以只看标记部分。选择题里还会出现“排序稳定性”的题目这种题没有真正意义上的“技巧”只能靠例子记忆。我常用序列[2a, 1, 2b]去验证冒泡和插入排序会保持2a在2b前面所以稳定选择排序在把最小值换到前面时可能把2a换到后面所以不稳定。2.2 应用题画图与手动模拟的标准步骤应用题考的是“会不会操作”通常包括构造二叉排序树并计算查找成功和失败的平均查找长度给定序列画出插入到散列表的冲突过程用 Prim 算法或 Kruskal 算法求最小生成树用 Dijkstra 算法求单源最短路径把中缀表达式转后缀表达式等。这一部分最大的问题不是不会而是答题步骤不完整。我见过的翻车现场包括只画出最终树没有中间过程散列表冲突处理只写下标不写用的是“线性探测”还是“链地址法”Dijkstra 只填最终距离表不写每一轮选了哪个节点。这些省略都会让阅卷人怀疑你并没有真正理解算法只是背了结论。我给你一套可以套用到所有应用题的标准流程。第一步在答题纸最上方写出输入序列按顺序编号。第二步把每一步的操作写出来比如“插入55大于3向右”一边写一边画新的结构。第三步对于算法模拟题每轮更新距离表或结构图并用笔标记当前选中的节点。第四步在最后结果旁边写一句“最终得到如下结构”把最终结果框起来。省略中间步骤是应用题扣分的最常见原因。以“构造二叉排序树”为例序列[45, 24, 53, 12, 37, 50]的插入过程是45 成为根24 小于45成为左子树53 大于45成为右子树12 小于45且小于24成为24的左子树37 小于45但大于24成为24的右子树50 小于53成为53的左子树。如果你只画最终树阅卷人无法判断你是否理解二叉排序树的定义甚至无法判断你插入顺序是否正确。所以每一步都要画并在节点旁边写上插入序号比如根节点旁写“45(1)”24旁写“24(2)”。再比如散列表题题面是“线性探测法构造散列表表长10散列函数H(key)key mod 10序列为 [12, 23, 45, 35, 78]”。你要写出每个元素计算出的下标以及冲突后探测的路径12 mod 10 2下标2空放入23 mod 10 3放入45 mod 10 5放入35 mod 10 5冲突线性探测到6放入78 mod 10 8放入。你必须明确写出“采用线性探测法冲突后依次检查下一单元”这才能拿到过程分。2.3 算法设计题从伪代码到可运行代码的差距算法设计题阅卷时思路分和代码分通常是分开的。有的学校要求先写思路再写代码思路占3~5分代码占8~10分。所以即便代码写不出来也要写出思路不能空着。很多同学伪代码写得很好但一写真实代码就漏掉边界。伪代码里“交换节点”一句话实际需要临时变量伪代码里“遍历数组”实际需要写i的起始和结束条件。这种差距只能通过多写来弥补。我建议你在复习最后阶段每天手写一道算法题不要只看必须笔写。写十道之后你对函数签名、循环边界、返回值的处理会明显有感觉。而且算法设计题常常是教材原题变形比如“在带头节点的单链表中删除所有重复元素”教材里通常有类似题目。你最好把课本里所有关于线性表、二叉树、图、排序的算法都过一遍至少做到能默写。另一个差距是复杂度分析。有些同学代码写对了但问复杂度时答错比如“归并排序时间复杂度”有人答 O(n^2)。算法设计题的第二问往往是“分析复杂度”你需要掌握递推式T(n) 2T(n/2) O(n)的解是 O(n log n)并且要能用自己的话推导而不是死记。从这张卷子的命题逻辑看选择题筛掉概念不清的人应用题筛掉不会操作的人算法设计题直接筛掉代码能力不足的人。接下来我们进入核心考点的复习路径。3. 核心考点复习路径从线性表到排序的必拿分点3.1 链表操作指针修改顺序与哨兵节点链表几乎是每套数据结构期末试卷的必考题。选择题考它与顺序表的对比算法题直接要求手写插入、删除、反转或合并。这里的本质是“指针修改顺序”只要记住“先保存后修改”就能避开大部分坑。以“删除链表中倒数第N个节点”为例一次遍历的做法是双指针第一个指针先走 N 步然后两个指针一起走第一个指针走到末尾时第二个指针正好指向目标节点的前驱。最麻烦的是“删除头节点”的场景解决办法是加一个虚拟头节点把删除头节点也统一成普通删除。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def remove_nth_from_end(head: ListNode, n: int) - ListNode: dummy ListNode(nexthead) # 哨兵节点避免单独处理头节点删除 fast dummy slow dummy # fast 先走 n1 步因为 dummy 不算链表中的真实节点 for _ in range(n 1): fast fast.next # 两个指针同步走直到 fast 到达末尾 while fast: fast fast.next slow slow.next # 此时 slow 指向目标节点的前驱 slow.next slow.next.next return dummy.next代码里的dummy是关键。没有哨兵节点你需要额外判断“要删的是不是头节点”否则返回头节点时可能返回一个被删的节点。这个哨兵节点不占实际数据只是让代码逻辑统一。复杂度方面链表只遍历一次时间 O(n)额外空间 O(1)。阅卷时看到你先让fast走 N 步再同步移动就知道你在用双指针。链表反转也是高频题递归和迭代两种写法都要会。迭代版需要三个指针prev、cur、next_temp。每次先把cur.next存起来再修改cur.next指向prev然后三个指针整体后移。很多同学写到最后忘了把原链表的头变成尾返回的是新链表的头。你可以记住原链表的头节点在反转后应该指向None新链表的头是原始链表的尾。3.2 二叉树遍历递归框架与迭代版取舍树是数据结构卷子中分值最大的一个板块尤其是二叉树。遍历、深度计算、最近公共祖先、路径和、构造最优二叉树全都能出题。二叉树题目最天然的解法是递归因为树本身就是递归定义的结构。中序遍历的递归写法非常固定先处理左子树然后访问当前节点再处理右子树。需要注意空树和返回值拼接。def inorder_traversal(root): if root is None: return [] result [] result.extend(inorder_traversal(root.left)) result.append(root.val) result.extend(inorder_traversal(root.right)) return result这段代码的递归退出条件是root is None返回空列表。递归就是“左子树结果 当前值 右子树结果”。时间 O(n)每个节点访问一次空间 O(h)h 是树高最坏退化成链时 O(n)。很多同学会问“为什么空间不是 O(1)”因为递归调用栈会占内存迭代版用栈也一样。但某些题目会限制“不能用递归”你必须掌握迭代版。前序和中序的迭代差异只在访问节点的时间点。中序迭代需要先一路向左把沿途节点压栈到底后弹出访问再转向右子树。def inorder_traversal_iter(root): stack [] cur root result [] while stack or cur: while cur: stack.append(cur) # 向左走到最左 cur cur.left cur stack.pop() # 弹出当前节点 result.append(cur.val) # 访问 cur cur.right # 转向右子树 return result这里外层循环条件是stack or cur因为一开始栈为空但cur不为空走到最后两个条件都假才结束。注意内层while cur必须在每次弹出后重置cur为右孩子。如果忘了cur cur.right就会无限循环。迭代版空间同样 O(h)但避免了函数递归可能导致的栈溢出。考试时如果没要求迭代用递归能写得更快如果要求“非递归”就用这段。3.3 图算法邻接矩阵、Dijkstra 与最小生成树图的题比树少但一旦出题就是大题常见的是要求手动模拟最短路径或最小生成树。复习时要抓住两个关键动作“每次选最小”和“更新邻居”。如果想用代码实现 Dijkstra优先队列版本最常用。dist[start] 0每次从堆里弹出距离最小的未访问节点然后松弛它的所有邻居。import heapq def dijkstra(graph, start): n len(graph) # 节点总数 dist [float(inf)] * n dist[start] 0 visited [False] * n heap [(0, start)] # (距离, 节点) while heap: d, u heapq.heappop(heap) if visited[u]: continue visited[u] True for v, w in graph[u]: if dist[v] dist[u] w: dist[v] dist[u] w heapq.heappush(heap, (dist[v], v)) return dist这里graph[u]是一个列表每个元素是(v, w)表示从u到v的边权重w。heap是优先队列保证每次弹出的节点距离最小。visited数组防止重复访问也避免负权边导致的无限更新。这个算法只适用非负权图期末卷通常默认正权边。复杂度是 O((VE)logV)因为每个节点可能入堆多次但堆操作是 logV。手动模拟 Dijkstra 时你需要画一个距离表每一轮标记“当前选中的节点”然后更新它邻居的距离。很多同学在卷子上直接给最终距离表丢失了过程分。最好的习惯是每轮都写一行例如初始: A距离0其余∞ 第1轮: 选A更新B为5C为2 第2轮: 选C更新D为6这样阅卷人能看到你的每一步思考。Prim 算法和 Kruskal 算法也要练。Prim 是从一个顶点开始每次加入“连接已选集合和未选集合中最小边”Kruskal 是每次选择全局最小边并判断是否成环。判断成环用并查集卷子上可能让你画并查集合并过程。3.4 查找与排序稳定性、复杂度与手写实现查找和排序是必考题而且经常串联先排序再用二分查找。复习时除了复杂度还要背下稳定性结论。稳定的排序有冒泡、插入、归并不稳定的有选择、快排、堆排序。注意稳定性是针对“相同元素的相对顺序”而言的不只看算法名字。手写快排是最常见的算法题核心是 partition 操作。这里给出一个固定写法基准取最后一个元素。def quicksort(arr, low, high): if low high: return pivot arr[high] # 取最后一个元素为基准 i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] partition_pos i 1 quicksort(arr, low, partition_pos - 1) quicksort(arr, partition_pos 1, high)代码里low high是递归退出条件如果漏掉当区间为空或单元素时会陷入无限递归。i初始为low - 1遍历过程中每发现一个小于等于基准的元素就把i后移并交换。最后把基准放到i1位置此时基准左边全部小于等于基准右边全部大于基准。快排平均 O(n log n)最坏 O(n^2)最坏情况发生在一开始基准就是最大或最小元素。为了规避可以用三数取中但手写考试通常用固定基准。二分查找也是必考常常作为应用题或算法题。def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1这里left right是循环条件表示查找区间存在。如果写成left right会漏掉目标恰好在下标left处的情况。mid left (right - left) // 2比(left right) // 2更安全虽然纸笔考试不会溢出但阅卷人看到这种写法会认为你考虑细致。二分查找的时间是 O(log n)但前提是数组有序。4. 算法设计题的高分答法阅卷视角与步骤4.1 先写函数签名类型、参数与返回值阅卷老师看算法题时第一眼看函数签名然后看主逻辑。如果签名写错后面代码再对也会扣分。某高校《数据结构》期末试卷的算法题通常用自然语言描述题目不给你函数原型你需要自己定义合理的签名。比如“删除有序链表中的重复元素”你可以定义函数为def delete_duplicates(head: ListNode) - ListNode:参数是链表头返回处理后的链表头。别返回None除非空链表。如果题目要求“返回新链表头”一定要保存修改后的头。很多人操作完直接返回原来的head结果头节点已经被删除返回的就是一个被移除的节点。这种细节阅卷人一眼能看出来。还有一类题要求通过参数返回结果比如“写一个函数将数组元素反转”。这时你可以定义def reverse_array(arr: list) - None并在文档注释里说明“原地修改数组无返回值”。如果你不说明阅卷人可能认为你忘了返回结果。在答题纸上你可以用文字明确“本函数原地修改输入数组”避免误解。4.2 伪代码三层结构边界、主体与越界我习惯把一道算法题的答案分成三层边界处理、主体操作、越界处理。边界是空输入、单元素、头节点特殊主体是循环或递归越界是下标是否合法。这相当于在答题纸上给自己搭了一个框架。伪代码不能省略关键细节。比如“遍历链表”要写清楚cur head; while cur ! None:如果你只写“循环直到结尾”阅卷人无法判断你有没有考虑空链表。所以时间再紧也至少把循环头和退出条件写完整。越界是数组题最容易出错的地方。比如二分查找里的mid计算如果你写mid (low high) // 2遇到大整数相加可能溢出。虽然纸笔考试没有真溢出但阅卷人会看你有没有习惯写low (high - low) // 2。这个细节能区分高分和及格分。另一个例子是数组反转你需要把i和j两个指针的结束条件写成while i j而不是while i ! j因为i和j可能交叉跳过。4.3 典型题完整作答快速选择第K大的元素我们来看一道典型题给定无序整数数组返回第 K 个最大的元素。这道题可以考快速排序思想、堆排序甚至哈希去重。我会选择快速选择算法期望时间 O(n)最坏 O(n^2)。先写思路利用快速排序的分区函数每次把数组分成小于等于基准和大于基准的两部分。如果基准下标恰好是目标下标则返回基准值否则只递归目标所在的那一侧。这样平均只需要 O(n) 时间因为每次只处理一半。def quick_select(nums, left, right, target): while left right: pivot nums[right] i left - 1 for j in range(left, right): if nums[j] pivot: i 1 nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] if i target: return nums[i] elif i target: left i 1 else: right i - 1 def find_kth_largest(nums, k): target len(nums) - k # 第 K 大的元素在升序数组中的下标 return quick_select(nums, 0, len(nums)-1, target)这里target len(nums) - k因为第 K 大相当于升序排列后倒数第 K 个元素。比如数组[3,2,1,5,6,4]k2第2大是5升序后是[1,2,3,4,5,6]下标len-24对应的元素是5。每次分区后只递归包含target的那一侧所以期望时间 O(n)。如果基准每次都选到最大或最小就会退化成 O(n^2)。阅卷时写出“快排分区思想每次只处理目标所在区间”的思路描述再加这段代码基本能拿满分。这道题还有另一种解法维护一个大小为 K 的小根堆遍历数组堆满后如果当前元素比堆顶大就弹出堆顶再入堆。最后堆顶就是第 K 大。这个解法也很快时间 O(n log K)而且不会退化。如果你在卷子上写了堆和快选两种解法至少会让阅卷人觉得你知识面广。5. 数据结构期末试卷避坑指南5个高频踩坑点5.1 划掉链表节点后丢了指针现象在链表中删除某个节点后想继续访问它的后继发现找不到链表了。比如写循环while cur:删除cur后写cur cur.next但此时cur.next可能已经被释放或断开。原因删除操作把当前节点的next指针修改了或者释放了当前节点内存后续访问自然出错。核心是没有在删除前保存下一个节点的地址。解决所有链表删除操作先写next_node cur.next再执行删除最后cur next_node。这个习惯能覆盖绝大多数链表删除题。如果你用 Python虽然内存不会立即释放但逻辑上cur.next可能已经变成别的值所以必须保存。5.2 递归遍历树时栈溢出现象在某高校模拟卷里二叉树退化成链表递归中序遍历直接爆栈。平时小树测试没问题测试数据一大就挂。原因递归深度等于树高极端情况下树高 O(n)。还有的同学没写递归终止条件或者终止条件写成了if root.left:而不是if root is None:导致递归无限向下。解决先检查递归基线条件确保每次调用都向空树逼近。如果题目明确说“节点数很多”直接用迭代栈。在试卷上你可以加一句话“此递归写法在树高过大时可能栈溢出可改为迭代”阅卷人会认为你考虑到了边界。5.3 图遍历漏掉 visited 标记现象用邻接表做 DFS结果陷入无限循环因为图里有环。很多同学把树的遍历直接搬到图上认为递归能自动结束。原因树是没有环的递归访问子树不会重复访问祖先图可能包含环如果没有标记访问过会不断重复访问同一个节点。解决在遍历函数入口写if v in visited: return并在第一次访问时立刻加入visited。记住图遍历“先标记再遍历”而不是“先遍历再标记”。如果先遍历再标记在环上仍可能重复入栈。5.4 排序稳定性判断凭感觉现象选择题问“哪些排序算法是稳定的”凭记忆选择把选择排序归为稳定丢分。原因混淆了稳定性的定义。稳定指的是“相同元素的相对顺序不变”。选择排序每次把最小值换到前面如果最小值是重复元素它可能在交换过程中越过另一个相等元素导致顺序变化。解决用一个小例子验证。例如序列[2a, 1, 2b]排序后如果是[1, 2a, 2b]则稳定如果是[1, 2b, 2a]不稳定。遇到稳定性题目先在草稿纸上写这个例子跑一遍别凭感觉。同时记住冒泡、插入、归并稳定选择、快排、堆排序不稳定。5.5 复杂度分析只数循环嵌套现象分析题遇到三层循环就写 O(n^3)遇到递归就不知道怎么写。比如分析 DAG 拓扑排序会写 O(VE)而不是单纯看循环层数。原因复杂度是“操作次数随输入规模增长的阶数”不是循环层数。有的循环虽然嵌套但内层总次数是固定的有的递归每一层规模减半整体不是简单的乘法。解决先画递归树或列出每层循环的迭代次数。比如二叉树遍历每个节点访问一次整体是 O(n) 而不是 O(n^2)。快速排序的递归树深度期望是 log n每层处理 n 个元素所以是 O(n log n)。如果在试卷上时间不够至少单独写清楚主要操作的发生次数例如“每个顶点入堆一次每条边松弛一次”这也能拿到部分分。6. 考前冲刺用限时自测把错题变成后悔药6.1 90分钟模拟考按真实卷子的题量配比建议你在考前三天找一套某高校往年的《数据结构》试卷或相同题型的模拟卷掐表90分钟完整做一遍。环境要像考场不说话、不查书、不中断。做题顺序建议先做算法设计题再做应用题最后做选择题。因为算法题分值高而且需要清醒的思路选择题相对独立放在后面即使时间紧也能快速作答。时间分配上选择题控制在20分钟应用题40分钟算法题30分钟。如果某一题卡了5分钟没思路先跳过去别在一个题上耗完所有时间。做完不要马上对答案休息10分钟再订正。这一步的价值是暴露真实的时间压力。很多同学平时能做对考场上写不完就是没有模拟过限时。90分钟模拟考还能让你注意到自己的书写速度如果字写得太慢应用题画图会拖后腿。6.2 错题归因把错误分成概念型、代码型、分析型对完答案后把错题分成三类。概念型指“怎么也想不起来定义”比如忘了散列表装填因子的公式代码型指“思路对但写不出来”比如快排 partition 写错循环边界分析型指“能写出代码但复杂度算错”。每一类用不同策略补。概念型回归教材专门看定义和性质代码型把正确答案手抄一遍再遮盖住自己重新写分析型需要把对应算法的递归树或操作次数重新推演一遍。错题分类不要求多但每道都要归类这样才能知道最弱的点。我当年把所有错题归成这三类结果发现代码型占了一半于是集中补了三天手写链表和树效率比盲目刷题高得多。你还可以给每类错题标一个“复发风险”等级比如连续两次错的标记为高优先级考前最后一天优先看高优先级错题。6.3 最后一天的手写训练代码和复杂度表格考前一天不要再学新知识。重点做两件事第一在白纸上手写核心算法代码包括链表反转、中序遍历、快排、二分查找、Dijkstra。每个代码控制在15分钟以内写完检查边界。第二把常用结构和算法的复杂度笔画成一张表格贴在书桌旁。考前看一眼稳定性结论和几个递归关系式比如T(n) 2T(n/2) O(n)对应 O(n log n)。我自己的习惯是考前晚上把所有算法题的代码用手机拍照存下来睡前快速翻一遍。这不是临时抱佛脚而是让大脑保持“代码模式”。另外你还可以把常犯的错误写在便签上考前看一眼比如“递归先写退出条件”“链表删除先保存后继”。这些细节不会帮你多拿十分但能避免不必要的失分。卷子上的代码题说到底就是把你平时练过的那几种模式重新输出一遍。数据结构的规律性很强只要你肯花时间手写、画图、推复杂度一定能看到进步。希望这篇围绕某高校《数据结构》期末试卷的拆解能帮到你稳扎稳打考场见。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
