简介湖北大学2022—2023学年第一学期《数据结构》期末试卷A卷以PDF形式整理成压缩包共1个文件、252KB版式清晰适合打印或导入平板练习。这份试卷面向期末备考的在校本科生、考研复习者及数据结构自学者能够帮助使用者熟悉高校出题风格检验图论、查找、二叉树、递归与存储结构等章节的掌握程度。试卷按判断分析、简答、应用分析等题型分层设置覆盖关键路径、带权有向图与邻接表存储、平均查找长度、二叉树遍历与中序先序重构、递归函数调用次数与结果推导、链栈适用性、二路归并排序、普里姆和克鲁斯卡尔算法、平衡二叉树构建、哈希线性探查等核心知识兼顾概念辨析与实际计算强化从理论到应用的完整训练。已有375人学习结合预览中的知识点总结可快速定位高频考点、检验复习效果适合考前集中突破无论是期末模拟、专题强化还是错题复盘都能帮助使用者提高解题熟练度。1. 一份数据结构期末试卷到底在考什么数据结构是计算机专业里挂科率最高的一门课而期末试卷往往是整门课最浓缩的产物。见过不少同学平时作业全对考试却跌在“题型不熟”和“手写代码不规范”上——期末试卷考的不是你会不会看书而是你能不能在三小时内把线性表、树、图、查找、排序这些模块的知识压缩成卷面上可判分的答案。这篇笔记就是围绕一份典型的高校数据结构期末试卷展开题型怎么分布、每章考点聚焦在哪里、算法设计题阅卷真正看什么、哪些失分点几乎每届都发生。适合读这篇文章的人有三类正在冲刺期末的学生想给学生出模拟卷的助教以及想靠一张卷子快速定位自己薄弱模块的考研复习者。我会按“拆卷面结构 → 逐章划重点 → 给可抄的模拟题 → 排失分坑 → 教你怎么用卷子反推复习”的顺序写全部基于我这些年帮人突击复习数据结构的经验不依赖某所学校内部资料只讲通用性和可复现的做法。2. 卷面结构拆解题型、分值分布与出题逻辑2.1 一份典型试卷的九宫格从选择到算法设计不管哪所学校数据结构期末试卷的题型基本被卡在五类里单项选择题、填空题、判断题、简答/应用题、算法设计题。前四类考察“概念是否清晰、计算是否熟练”最后一类直接考察“能不能写代码”这也是拉分最狠的部分。综合几所高校近年的情况常见分值分布是单选 20 分每题 2 分填空 1015 分判断 10 分简答/应用 2530 分算法设计 2535 分。总分通常 100 分考试时间 120 或 150 分钟。出题逻辑通常是“知识点遍历 重点倾斜”的组合。遍历体现在每一章都出题哪怕只有一两分倾斜体现在树、图、排序、查找这四章占了简答和算法设计的大头。如果你复习时间有限优先把这几章的课后题吃透比从头翻书更划算。题型常见分值考察能力失分主因单选题1820概念辨析、复杂度计算选项近似记混定义填空题1015精确记忆术语与公式关键字不写如“堆”写成“堆排序”判断题810快速判定性质忽略“一定”“必须”等绝对词简答/应用题2530构造过程、写步骤过程不全只写结果算法设计题2535数据结构选型、代码实现只写思路不写代码或边界没处理2.2 出题人的“重点倾斜”规律把近几年的卷子放在一起看会发现出题人极其偏爱几个固定模型二叉树的各种遍历序列互推、哈夫曼树构造与编码长度计算、图的邻接矩阵与邻接表转换、Prim 与 Kruskal 构造最小生成树、散列表的冲突处理、快排与堆排序的过程模拟。这些模型在卷面上要么是简答题要么是算法设计题的背景。我一般建议学生按“计算类考点”和“代码类考点”分两条线复习。计算类考点的共同特征是结果唯一比如给定中序和后序序列求二叉树答案写错就没分必须靠大量手算练出速度代码类考点则看重结构完整度和边界处理比如链表反转时指针丢失是典型扣分点。两条线各自的练习方式完全不同混在一起复习容易两头都抓不住。2.3 算法设计题阅卷真正的判分依据算法设计题通常给出 23 小题每题 815 分比如“设计算法删除单链表中所有值为 x 的结点”“写出二叉树后序遍历的非递归算法”。阅卷时看三个维度一是数据结构选型是否合理用数组硬写树的层序遍历不算错但会被扣分二是核心逻辑是否完整尤其循环终止条件和指针移动顺序三是代码规范包括函数头、返回值、边界判断。很多人误以为“写了主要思路就有分”实际上不少课程组的评分标准里思路只占 30% 左右的分值剩下 70% 要看代码本身。我的建议是哪怕写不完全也要把函数签名、局部变量声明、关键循环框架写出来这能拿到结构分而不是空白一片。3. 核心考点聚焦每章必考模型与一道可复现的模拟题3.1 线性表与栈队列算法设计题的常客线性表部分必考链表的插入、删除、反转、合并尤其是单链表的原地操作。题目往往不给头结点或者给一个带头结点链表两种写法的边界条件不一样这是常见的翻车点。栈和队列则偏爱“用栈实现队列”“用队列实现栈”“表达式求值”这几个模型其中后缀表达式求值几乎是必练题。给你一道可以直接拿去自测的算法设计题这也是期末卷上出现频率最高的一类# 删除单链表中所有值等于 target 的结点带头结点 def delete_all(head, target): prev head # prev 始终指向当前检查结点的前驱 cur head.next # cur 指向当前检查结点 while cur is not None: if cur.data target: prev.next cur.next # 跳过 curprev 不动 cur prev.next # 继续检查下一个 else: prev cur # 不删除时prev 前进 cur cur.next return head这段代码的核心逻辑是“双指针遍历删除”。prev用于记录待删除结点的前驱head是带头结点链表的头这样能统一处理“第一个结点就被删掉”的情况。while cur is not None是遍历终止条件如果把cur.next也写进条件里就会漏掉对最后一个结点的判断。这里最容易被忽视的是删除分支中prev不能移动如果删掉当前结点还让prev前移就会跳过被删除结点的后继。参数方面target是待删除值函数返回头结点方便链式调用。3.2 树与二叉树简答和算法题双热点树的考点集中在二叉树性质、遍历序列互推、哈夫曼树建树与编码、二叉排序树和平衡调整。遍历序列互推是选择题和简答题的固定题型给定前序中序或中序后序推原二叉树核心是“中序序列用来分左右子树前序/后序用来确定根”。哈夫曼树这里注意构造过程中每次合并必须取当前权值最小的两个结点且新结点权值放回集合后要重新参与比较很多学生在这里排序出错导致编码长度算错。算法设计题里最常考二叉树非递归遍历和求树深。非递归中序遍历是标配你必须熟练使用栈模拟递归# 二叉树中序遍历非递归实现 def inorder_norec(root): stack [] cur root result [] while cur is not None or stack: while cur is not None: stack.append(cur) # 一路向左压栈 cur cur.left cur stack.pop() # 左子树全处理完弹栈 result.append(cur.data) # 访问根结点 cur cur.right # 转向右子树 return result这段代码的结构是“外层循环控制整体内层循环压左链”。while cur is not None or stack是循环条件它保证处理完根结点的左子树后还能回到根再去遍历右子树。stack保存的是尚未访问但已经入栈的结点出栈顺序天然就是中序。需要特别注意的是cur cur.right这一行如果把它写在访问结点之前就会变成先访问右子树再访问根完全错误。二叉树的存储结构这里默认用left和right指向左右孩子在考试手写代码时建议先声明data、left、right三个属性避免阅卷人不知道你的结点怎么定义。3.3 图图的存储与遍历简答必有一席图这一章简答必出图的遍历序列、最小生成树或最短路径算法题偶尔考拓扑排序和邻接表操作。图的遍历序列有个大坑结果依赖存储结构。同一个图用邻接矩阵存和用邻接表存DFS 和 BFS 的访问顺序可能完全不同因为邻接表里的边表顺序会影响出边访问的先后。考试时题目如果没给存储结构你要主动说明“以下按邻接表存储边表按顶点序号升序排列”否则阅卷人没法判定你的序列对不对。最小生成树这里MST 的性质可以出一道经典判断题“若图中有 n 个顶点 n-1 条边则图必为树”答案是错的——n 个顶点 n-1 条边且连通才是树如果不连通则构成森林。这种带“必”字的绝对判断是选择题和判断题的高频挖坑点。复习时把图论里所有带“一定”“必须”“所有”的命题拉一个清单逐个验证基本能覆盖判断题。3.4 查找与排序过程模拟题占比最高的两章查找部分重点考二分查找的比较次数判定、二叉排序树构造、散列表装填因子与平均查找长度计算。排序部分则是各类排序的过程模拟、稳定性判断和复杂度背诵。期末卷最爱出“给出一组关键字写出快速排序第一趟结束后的序列”这类小题考的就是 partition 过程的理解。# 快速排序第一趟 partition以第一个元素为基准 def partition(arr, low, high): pivot arr[low] # 基准元素 while low high: while low high and arr[high] pivot: high - 1 arr[low] arr[high] # 从右边找到小于 pivot 的移到左边 while low high and arr[low] pivot: low 1 arr[high] arr[low] # 从左边找到大于 pivot 的移到右边 arr[low] pivot # 基准归位 return low # 返回基准最终位置这段代码是快排第一趟的标准实现。两个内层while必须都带low high条件否则指针会越界比较符号要注意右指针找的是比基准小的所以用 pivot跳过不小于的左指针找的是比基准大的用 pivot跳过不大于的。这里相等元素跳过反而保证了稳定性但在很多教科书实现中相等元素会跨过基准导致不稳定这是面试和期末都爱考的辨析点。pivot arr[low]把基准先存起来相当于腾出一个空位后续交替填充利用的正是这个空位理解这一点整个 partition 代码就不会写乱。哈希表构造题也是高频常见冲突处理是线性探测法和链地址法。线性探测法要求装填因子控制在合理范围计算平均查找长度时要区分成功和失败两种场景成功场景除以表内已有元素个数失败场景除以表长很多人在这一步算错。4. 期末失分避坑五条每届都有人踩的坑4.1 算法题只写思路不写代码白丢 70% 分值现象简答题满满当当算法设计题空白一大片只写了一句“定义一个栈来实现”然后没下文。考后对答案时说“思路我会就是不知道怎么写出来”。原因平时刷题都是用编译器帮自己兜底手写代码能力完全没练过。算法设计题判分的结构分、逻辑分、规范分全都拿不到。解决考前两周每天手写一道算法题直接写在白纸上不经过编译器。写完对照标准答案逐行查函数签名、变量初始化、循环条件、指针移动、返回值。重点练习单链表操作、二叉树递归与非递归遍历、快排 partition、二分查找四类基本覆盖期末算法题的八成场景。4.2 复杂度分析漏掉递归栈空间选择题送分变送命现象选择题问“求二叉树深度的递归算法空间复杂度”很多人选 O(1)觉得只用了一个变量存深度正确答案是 O(n)。原因递归算法的空间复杂度包括系统调用栈的开销每层递归都要压栈保存现场。树的高度等于栈的深度所以是 O(n)这里的 n 是树高。解决见到递归算法先画递归调用链看看最深能压几层。任何递归算法的空间复杂度都不可能是 O(1)至少是 O(递归深度)这可以帮你排除至少一个错误选项。4.3 哈希表平均查找长度“失败”和“成功”混着算现象给出散列表和冲突处理方式让算查找成功的平均长度学生算出来比标答多 2 以上查步骤发现把失败探测也算了进去。原因成功和失败的平均查找长度计算公式不同。成功情况下分母是表中元素个数 n统计每个元素查找时的比较次数后相加失败情况下分母是表长 m需要模拟每个散列地址都可能产生一次不成功的查找才能算出期望比较次数。解决拿到哈希题先圈出题目关键词——“成功”还是“失败”。两种都练一遍对比结果你就知道差异有多大。另外线性探测法在算失败时探测序列要遇到空位置才停止这也是容易数错的地方。4.4 图的遍历序列不说明存储结构答案成了“薛定谔的序列”现象卷子上直接写“DFS 序列1 2 3 4 5…”没写邻接矩阵还是邻接表结果阅卷按另一种存储结构的标准判扣了整道题的序列分。原因不同存储结构下出边顺序不同。邻接矩阵按顶点编号扫描邻接表按边表链顺序扫描只要边表插入顺序不同DFS 访问序完全可能不同。题目没明示而你的答案和标答不一致就会被判错误。解决做题第一步先确认存储结构。如果题面没说你在答案开头写一行“按邻接表存储假设边表顶点按升序排列”再给序列。写存储结构这个动作本身就让阅卷人知道你的答案是有依据的至少不会误判。4.5 排序题记混稳定性和“哪些排序能用链表实现”现象判断题写“直接插入排序是稳定的希尔排序也是稳定的”后半句是错的但很多人记反。多选题“下列哪些排序可以方便地用链表实现”有人全选实际上堆排序和折半插入排序对链表不友好。原因稳定性不是靠背口诀记的而是来源于比较和交换的过程。直接插入排序的相等元素不交换位置所以稳定希尔排序分组后可能跨越多个位置移动相等元素所以不稳定。链表实现方面堆排序需要随机访问链表做不到。解决把五类重点排序冒泡、直接插入、简单选择、快排、归并按“稳定/不稳定”画一张表再配上各自的时间/空间复杂度。这张表不是背的是你拿一组带重复数字的序列手跑一遍过程自己得出结论的。跑过一遍比背十遍口诀都管用。5. 用卷子反推复习重点考点矩阵与限时自测法先搭建一个“考点 × 题型”矩阵这是我从考前突击里提炼出来的最有效方法。拿近三年的期末卷如果不方便找原卷就拿教材每章课后题里的典型题代替统计每个考点在选择题、简答题、算法题里各出现几次填在下表里考点选择题简答题算法题复习权重单链表操作中低高必须手写栈与队列应用中高中必须手写二叉树遍历与性质高高高必考核心图遍历与最小生成树中高低重点理解排序过程模拟高高低多手算查找与散列高中中计算熟练统计完你会发现算法题的高频区集中在链表和二叉树简答题的高频区在树、图、排序。那么时间分配就有了依据算法题练习占 40% 精力简答计算占 40%选择判断只占 20%。接下来是限时自测法。找一段完整的两小时按考试规格做一份模拟卷可以是教材总复习题拼凑也可以是课程组往年公开的样卷。自测时要模拟考场环境不翻书、不查资料、不中断。做完不要立刻看答案先把没把握的题目标出来再对照参考答案逐题评分最后统计失分类型是概念记忆型失分还是计算粗心型还是算法设计型。这个统计决定了你最后一周的复习方向——如果是算法设计型失分占大头说明代码量不够需要每天手写两到三道算法题如果计算粗心型居多说明知识掌握没问题缺的是限时训练手感和检查习惯。最后分享一个我自己的教训有一年复习时我迷信“刷题数量”把课后题全做了一遍但每道题都是边看书边做最后卷子上的算法题看起来眼熟却写不出来。后来改成“闭卷限时 手写代码 对照评分”只练了十道高频算法题效果比刷五十道题还好。数据结构期末考的底层逻辑就是“会写代码 会算过程 概念精准”三样缺一不可。你按这个思路把卷面结构、考点矩阵、限时自测结合起来期末前的复习方向就不会跑偏。希望帮到你。本文还有配套的精品资源点击获取