简介这份湖北大学数据结构期末试卷A卷PDF面向计算机与信息安全专业本科生及考研复习者用于期末冲刺与知识点系统梳理。试卷覆盖判断分析、简答与应用分析等题型涉及带权有向图关键路径、邻接表求边数与入度、顺序查找平均查找长度、出栈序列判定、由先序和中序推后序、递归函数fun(x,n)求幂及调用次数、链栈存储选择、特殊矩阵与稀疏矩阵压缩、顺序表删除操作纠错、二路归并排序各趟结果、Prim与Kruskal最小生成树执行过程、二叉排序树构造与查找ASL、平衡二叉树插入调整、哈希表线性探查等核心考点。压缩包仅含1个PDF文件约252KB轻量便于打印和移动端翻阅。已有376人学习下载适合按章节刷题后对照课堂笔记查漏补缺每道题都对应具体章节便于定位薄弱环节并安排二轮复习也可作为教师命题与讲评的参考样卷。1. 数据结构期末试卷真正拉分的地方不在最后一道大题期末季常有人拿着数据结构期末试卷的回忆版来问选择题感觉全对最后两道算法题几乎空白卷面分卡在及格线上下。翻草稿纸能看出问题不在“不会”而在“写不出来”——单链表逆置的指针顺序画了三遍还是丢节点Dijkstra 的松弛条件写对了却忘了更新前驱循环队列的判满条件跟判空写成了同一个。数据结构期末试卷这类闭卷笔试考的是在无编译器、无断点、无打印的条件下把结构想清楚并一次写对这跟平时在 IDE 里试错完全是两回事。下面按题型拆解、代码模板、纸上推演、丢分排查、自测验证的顺序走一遍目标是让复习时间压到最该压的地方而不是把整本书再抄一遍。2. 题型与分值拆开看复习时间该往哪三类题上压先把卷面当成一个预算问题。多数数据结构期末试卷的结构大同小异选择题和填空题占 20 到 30 分判断题和简答题占 15 到 25 分剩下的 40 到 50 分给算法设计题和综合应用题。分值分布不等于得分难度分布真正决定能不能上 80 分的往往是中间那档“会但容易写错”的题而不是最后那道压轴。带过几轮复习之后我一般会先做一件事把最近三五套卷子的题型列成一张表标上自己的实际得分率再决定时间往哪投。2.1 从卷面结构倒推哪些题属于“保底分”保底分指的是只要概念清楚、不粗心就能拿到的部分线性表的基本定义、栈和队列的特性、二叉树的性质第 i 层最多 2^(i-1) 个节点、n 个节点的完全二叉树高度、图的度与边的关系、几种排序的稳定性。这部分内容碎但门槛低适合用零散时间过比如每天固定二十分钟翻概念卡片而不是拿整块时间啃。保底分没拿满就去攻算法题是最常见的策略性错误因为算法题写对一道的期望收益可能还不如把选择题的两个易混点分清。反过来综合应用题里的画图题构造哈夫曼树、画邻接表、写出某趟排序后的序列属于“过程分”即使最后结果算错中间步骤写清楚也能拿一半以上。这类题的正确策略是过程写全、编号标清、每步都留痕不要为了省时间只写最终答案。2.2 把考点分成“必须手写”和“只需口述”两栏这是我认为最有用的一个动作。拿一张 A4 纸对折左边写“必须能在纸上默写出来的”右边写“能说清楚原理和复杂度就行”。必须手写的通常包括顺序表的插入删除、单链表的头插尾插与逆置、循环队列的入队出队、二叉树的三种递归遍历、由两种遍历序列还原二叉树、图的邻接矩阵与邻接表构造、冒泡/插入/选择/快速/归并中的两三种排序过程、二分查找的判定树。这些内容有一个共同点考场上没有提示必须靠肌肉记忆写出结构正确的代码或步骤。只需口述的包括各种结构的定义与 ADT 描述、算法时间复杂度的推导结论、稳定性对比、B 树与 B 树的区别、哈希冲突处理的几种方法及其优缺点。这些适合用“自问自答”的方式过能连续说满一分钟不卡壳就算过。两栏分开的好处是你不会在“背定义”上花掉本该用来默写代码的时间也不会在考场上才发现某个结构从来没手写过。2.3 七天复习表的排法每天两小时怎么切按每天两小时、七天倒排我一般这样切前三天每天 40 分钟过概念和选择填空易错点80 分钟默写代码模板第四、五天专攻综合应用题把遍历还原、最短路手算、排序过程各推三遍第六天做一套完整卷子并计时第七天只看错题和自己的默写稿不再碰新题。这个排法的关键在第六天。很多人复习到后期只看不写结果考场上前二十分钟手是僵的。完整计时做一套的价值不只是查漏更是让手适应连续书写四十分钟代码的强度。计时的时候用手机秒表选择题控制在 25 分钟内超过就停强迫自己进入下一部分。题型常见分值区间建议耗时占比复习动作选择与填空20–3025%概念卡片每天二十分钟判断与简答15–2520%自问自答能口述即过算法设计25–3535%纸上默写模板不看参考综合应用15–2520%手算推演过程写全表格里的耗时占比是对复习时间的分配不是考场时间。考场上算法设计题建议留足 40 分钟因为读题、想清楚边界、写代码、检查每一步都比平时慢。3. 线性结构手写题顺序表、单链表、循环队列的三份代码模板线性结构是数据结构期末试卷里最稳定的得分点题型几乎年年出现给一个顺序表写插入删除、给一个单链表写逆置或找中间节点、给一个循环队列写判空判满。这类题不难但丢分往往丢在细节上下标从 0 还是从 1 开始、搬移方向反了导致覆盖、链表改指针前没保存后继。下面三份模板可以直接默写重点看注释里标出的顺序和边界。3.1 顺序表插入删除搬移方向决定成败def seq_insert(data, length, i, x): # data: 预分配好容量的列表length: 当前元素个数 # i: 插入位置按 1 开始计教材常见约定x: 待插入元素 if length len(data): raise OverflowError(顺序表已满) if i 1 or i length 1: raise IndexError(插入位置非法) # 从最后一个元素开始往后挪必须倒序否则前面的值会覆盖后面的 for j in range(length, i - 1, -1): data[j] data[j - 1] data[i - 1] x return length 1这段代码的核心在range(length, i - 1, -1)。如果写成正序data[i]会先被data[i-1]覆盖再往后搬的时候拿到的就是已经被改过的值结果整段数据错位。考场上的判断方法很简单插入是“从后往前挪”删除是“从前往后挪”两者方向相反。参数上要留意的有两个。一是i的基准教材里顺序表位置常从 1 开始但数组下标从 0 开始写代码时要么统一转换要么在函数开头就注明约定别写到一半混用。二是容量检查length len(data)和length len(data)差一个等号前者才是对的因为len(data)是容量上限length等于它时已经没有空位。删除的模板同理只是方向反过来def seq_delete(data, length, i): if i 1 or i length: raise IndexError(删除位置非法) x data[i - 1] for j in range(i - 1, length - 1): data[j] data[j 1] return x, length - 1复杂度上插入和删除的平均移动次数都是 n/2最坏 n最好 0在表尾操作所以平均时间复杂度 O(n)。这个结论要能当场推不能只背。3.2 单链表逆置与找中点三个指针的赋值顺序单链表逆置是数据结构期末试卷里出现频率最高的手写题之一因为它同时考指针操作和循环不变式。模板只有六行但这六行的顺序不能变class Node: def __init__(self, val, nxtNone): self.val val self.nxt nxt def reverse(head): prev, cur None, head while cur: nxt cur.nxt # 第一步先把后继存下来否则改完指向就找不到后面了 cur.nxt prev # 第二步把当前节点指向前驱 prev cur # 第三步前驱前移 cur nxt # 第四步当前节点前移 return prev # 循环结束时 cur 为空prev 是新头赋值顺序错一步就断链这是血泪经验。最常见的错法是先写cur.nxt prev再写nxt cur.nxt第二次拿到的已经是改过的指针剩下的节点全丢。检查方法在纸上画三个格子标上 prev、cur、nxt然后逐行模拟两轮看有没有节点脱离链表。返回值的细节也常被忽略循环结束时cur是None新头是prev返回head是错的。另外要问清楚题目是否要求带头结点带头结点的版本返回值是head本身只是把head.nxt之后的节点逆置这两种写法在卷面上要分清。找中间节点用快慢指针代码更短但有一个考场陷阱def middle(head): slow fast head while fast and fast.nxt: slow slow.nxt fast fast.nxt.nxt return slow节点个数为奇数时返回正中间偶数时返回偏右的那个。如果题目要求“偏左”循环条件要改成while fast.nxt and fast.nxt.nxt或者在初始化时让fast head.nxt。这一步不看清题干就写很容易整题扣分——不是代码错是语义不对。3.3 循环队列为什么必须牺牲一个存储单元循环队列的判空判满是最容易翻车的地方。顺序存储的队列如果不做处理front rear既可以表示空也可以表示满二义性没法区分。教材里的标准解法是牺牲一个单元class CircularQueue: def __init__(self, cap): # 实际可用容量是 cap数组开 cap 1留一个空位区分队空和队满 self.data [None] * (cap 1) self.front 0 self.rear 0 def enqueue(self, x): if (self.rear 1) % len(self.data) self.front: raise OverflowError(队满) self.data[self.rear] x self.rear (self.rear 1) % len(self.data) def dequeue(self): if self.front self.rear: raise IndexError(队空) x self.data[self.front] self.front (self.front 1) % len(self.data) return x def size(self): return (self.rear - self.front len(self.data)) % len(self.data)判空是front rear判满是(rear 1) % n front两个条件差一个取模后的相邻关系。size()里的 len(self.data)是为了处理rear小于front的绕回情况不加会得到负数。另一种解法是额外维护一个count变量队满条件写成count cap。这种写法不用牺牲单元但要在入队出队时同步维护count漏一处就错。考场上我一般推荐前者因为条件少、不容易忘。答题时要写明“牺牲一个单元”这个设计选择过程分往往就在这句话上。4. 树与图的纸上推演遍历还原、邻接表和 Dijkstra 手算表树和图是数据结构期末试卷里分值最重、也最容易“看着会、下笔错”的部分。它们不像线性表那样有固定模板考的是推演过程。这一章给三个可复用的推演方法遍历序列还原、图的存储构造、最短路手算表。共同思路是先把中间状态落到纸面上再往下走不要在心里默算。4.1 由先序中序还原二叉树三个合法性判定题目给先序和中序序列要求画出二叉树。标准做法是递归先序第一个元素是根在中序里找到它左边是左子树右边是右子树再按长度切分先序序列。写成代码是这样def build(pre, ino): # pre: 先序序列ino: 中序序列 if not pre: return None root_val pre[0] if root_val not in ino: raise ValueError(序列非法根不在中序中) k ino.index(root_val) # 根在中序中的位置 左子树节点数 if len(pre) ! len(ino): raise ValueError(序列非法长度不等) root Node(root_val) root.left build(pre[1:k 1], ino[:k]) root.right build(pre[k 1:], ino[k 1:]) return root切分的关键是pre[1:k1]先序序列里根占一位后面连续 k 个是左子树剩下的才是右子树。k 来自中序里根的位置也就是左子树的节点数。这个对应关系写错整棵树就歪了。卷面上宁可多写一步合法性检查。三个判定是两个序列长度必须相等先序第一个元素必须能在中序里找到切出来的左右子树长度必须能对上。前两个是硬性错误第三个是常见的手误。做完之后用后序序列反推一遍验证能发现大部分错误。后序加中序还原是同样的思路只是根从后序末尾取。先序加后序不能唯一确定一棵二叉树这个结论本身就是简答题的常客要能说清楚原因缺少中序就无法区分只有一个孩子的子树是左还是右。4.2 邻接矩阵与邻接表先画表再算度图的存储考法很固定给一个带权图要求写出邻接矩阵和邻接表再算某个顶点的度。这两步都不难但书写量大容易漏边。邻接矩阵是 n×n 的方阵无权图用 0/1带权图用权值加一个无穷大符号表示不连通。无向图的矩阵关于主对角线对称写完之后检查一遍对称性能抓出大半错误。顶点的度等于该行非零或非无穷元素的个数有向图要分出入度出度看行入度看列。邻接表是每个顶点挂一条链表节点存邻接点编号和权值。书写时按顶点编号顺序排列每条链表按题目给定边的顺序挂不要自己重排否则跟标准答案对不上。无向图每条边要在两个顶点的链表里各出现一次这一点最容易漏。邻接矩阵的空间复杂度是 O(n²)适合稠密图邻接表的空间复杂度是 O(ne)适合稀疏图。判断稠密还是稀疏粗略看边数是否接近 n² 量级。这个选型理由是简答题的常见问法要能一句话说清矩阵判断两点是否相邻是 O(1)但要遍历某点的所有邻居是 O(n)邻接表反过来。4.3 Dijkstra 手算表每一轮只做三件事Dijkstra 是综合应用题的高频考点考法通常是“从某点出发写出到其余各点的最短路径和路径长度”。手算时不要凭感觉用表格按轮次推每轮只做三件事选当前未确定集合里 dist 最小的点加入已确定集合、用它松弛邻居、更新前驱。给一个五顶点的例子边为 A-B 4、A-C 2、B-C 1、B-D 5、C-D 8、C-E 10、D-E 2求 A 到各点的最短路。轮次已确定集合 Sdist(A)dist(B)dist(C)dist(D)dist(E)本轮松弛初始{A}042∞∞—1{A, C}0321012C→B 得 3C→D 得 10C→E 得 122{A, C, B}032812B→D 得 8优于 103{A, C, B, D}032810D→E 得 10优于 124全部032810—最终 A 到 B、C、D、E 的最短距离分别是 3、2、8、10。推的时候有两个细节要盯住第一每轮只能从“未确定”的顶点里选最小的已经进 S 的不再参与第二松弛时必须比较dist[u] w dist[v]只写更新不写比较会把更长的路径覆盖上去。Dijkstra 不能处理负权边这是简答题的经典追问。原因是它的正确性依赖“已确定顶点的距离不会再变小”这个贪心前提负权边会破坏这个前提。会否定这一点比会算一张表更能拿到过程分。最小生成树的手算同理。Prim 从起点出发每次选连接“已选集合”和“未选集合”的最小边Kruskal 把所有边排序从小到大选用并查集判环。两者的适用场景要分清稠密图用 Prim稀疏图用 Kruskal这个结论在选择题里几乎每年出现。5. 丢分排查数据结构期末试卷里最常见的五类错误复习到后期提分空间最大的不是新知识而是把已经会做的题的错误率压下去。下面五类错误是从大量错题里归纳出来的高频项每一条都按“现象、原因、解决”写对照自己的草稿纸看中一条改一条。5.1 指针与下标断链和越界现象一单链表逆置写完后只剩两三个节点后面的全丢了。原因是改指针和保存后继的顺序反了先执行cur.nxt prev再取cur.nxt拿到的已经是改过的值。解决办法是固定四步顺序存后继、改指向、前驱前移、当前前移并且在纸上用三个格子模拟两轮确认没有节点脱链。现象二顺序表插入后数据整体右移了一位或者最后一个元素被覆盖。原因是搬移用了正序循环前面的值覆盖了后面待搬的值。解决方法是牢记“插入倒着搬、删除正着搬”并且把循环的起止下标写出来核对一遍插入是从length到i删除是从i-1到length-2。现象三循环队列的size()返回负数。原因是rear绕回后小于front直接相减得到负值。解决方法是加上数组长度再取模写成(rear - front n) % n其中 n 是数组实际长度含那个空位。5.2 条件与前提判空判满、负权、稳定性现象四循环队列的入队判断永远不触发队满后覆盖了队头元素。原因是判满条件写成了rear front跟判空撞了。解决办法是明确采用“牺牲一个单元”的方案判满写成(rear 1) % n front并在答题时把这句话写出来说明设计选择。现象五Dijkstra 用在带负权边的图上算出的距离比实际最短路径还大。原因是贪心前提不成立已确定集合里的点后来还可能被更短的路径更新。解决办法是看题干有没有“非负权”这个限定没有的话优先考虑 Bellman-Ford 或者题干其实在考“为什么不能用”。另外求最长路径也不能直接套 Dijkstra把权值取负再跑一遍同样不成立这一点简答题常设陷阱。现象六快速排序写成不稳定还振振有词。稳定性指的是相等元素在排序前后相对次序是否保持。快速排序、选择排序、堆排序不稳定冒泡、插入、归并、基数排序稳定。这个表要背但更要知道原因快排的分区交换会跨越相等元素归并的合并按顺序取左半部分所以稳定。答题时先给结论再给一句原因比只写结论得分高。6. 交卷前用随机对拍自检给链表和排序各写一段验证脚本复习阶段最有效的一个习惯是把纸上的算法真的敲一遍用随机数据跟标准库对拍。这件事看起来费时间实际上能把“以为自己会了”和“真的写对了”之间的差距暴露出来。我一般会写两个小脚本一个验排序一个验链表跑通之后再回到纸上默写手感完全不一样。排序的对拍最简单用内置的sorted当参考答案import random def quick_sort(a): if len(a) 1: return a pivot a[len(a) // 2] left [x for x in a if x pivot] mid [x for x in a if x pivot] right [x for x in a if x pivot] return quick_sort(left) mid quick_sort(right) cases [[], [1], [2, 1], [3, 3, 3], list(range(20)), list(range(20, 0, -1))] for _ in range(2000): n random.randint(0, 30) cases.append([random.randint(-50, 50) for _ in range(n)]) for a in cases: assert quick_sort(a) sorted(a), ffail on {a} print(all pass)这段脚本的价值在用例集不在代码本身。空列表、单元素、全相等、已升序、已降序这五类边界正好对应考场上最容易写错的分支递归终止条件、分区后中间段的处理、全相等时是否退化。随机用例负责覆盖组合情况固定用例负责保证边界不漏。链表用“逆置两次应还原”来验证不需要参考答案def to_list(head): out [] while head: out.append(head.val) head head.nxt return out for _ in range(500): vals [random.randint(0, 99) for _ in range(random.randint(0, 15))] head None for v in reversed(vals): # 尾插法建表保持原顺序 head Node(v, head) assert to_list(reverse(reverse(head))) valsreverse是第 3 章那份模板。两次逆置还原检查的是指针操作是否可逆——如果第一次逆置就丢了节点第二次不可能还原出原序列。这个方法比对着答案一行行看高效得多。考场上当然没有脚本但复习时跑过几百组随机数据之后你对边界条件的敏感度会明显不同。看到“带头结点还是不带”“偶数个节点取偏左还是偏右”“队满时数组实际长度是多少”这类描述手会先于脑子做出反应。我自己的习惯是每默写完一个模板立刻在电脑上敲一遍跑一次对拍然后再合上屏幕在纸上重写。第一次写对不算数隔一天还能写对才算。这个流程听起来笨但它把“看懂了”和“考场上写得出来”之间那段距离补上了。希望帮到你。本文还有配套的精品资源点击获取