数据结构期末试卷拆解：手工模拟、算法设计与对拍自测

简介面向湖北大学计算机与信息工程学院数据结构课程复习的期末试卷PDF对应2022—2023学年度第一学期A卷适合信息安全等专业学生考前自测、章节梳理与查漏补缺。资源包仅含1个PDF文件大小约252KB按闭卷考试形式编排完整呈现判断分析题、简答题和应用分析题等常见题型单份文档便于打印后限时练习。试卷覆盖带权有向图与关键路径、邻接表存储、出栈序列判断、顺序查找平均查找长度、二叉树遍历还原、递归函数调用次数、链栈选择、矩阵压缩、二路归并排序、Prim与Kruskal算法、二叉排序树及平衡二叉树构建、哈希线性探查等核心内容。已有376人学习下载可用于对照课堂重点检查概念辨析、计算过程和算法分析能力也适合作为教师命题或同学间讨论的参考材料。1. 一份数据结构期末试卷卡住人的向来不是概念本身考前三天桌上摊开一份数据结构期末试卷选择题、填空题、判断题还能连蒙带猜撑过去翻到「画出直接插入排序每一趟的结果」「写出模式串的 next 数组」「用邻接表实现 Dijkstra 并填写距离表」这三道大题笔就停住了。这类题并不考你知不知道什么叫排序、什么叫最短路它考的是能不能在纸上把中间过程一步不错地推完。整份卷子的骨架多年没大变四十来分客观题打底五十来分手写模拟和算法设计拉开差距最后十分复杂度分析收尾。这份卷子值得认真拆——它同时是学生的过关线、助教出模拟卷的模板、以及检验自己数据结构基本功最省事的一块试金石。下面按考点拆骨架、按题型写可复现的代码、最后给一套能自己跑的对拍脚本。2. 把卷子摊开看骨架三类题型的分值分布与判分点2.1 一份典型卷面的题型与分值结构不同学校的卷子细节各异但分值骨架高度相似。我手头整理过的几份卷子题型配比基本落在下面这张表的区间里偏理论的卷子会把复杂度分析提到 15 分偏工程的卷子会加一道 10 分的代码填空题。题型常见题量卷面分值建议用时失分率选择题102015 min低填空题51010 min中判断题5105 min低手工模拟题33045 min高算法设计题22035 min高复杂度分析1~21010 min中这三段题目的性质完全不同。客观题是覆盖面题考的是「线性表的顺序存储和链式存储各自适合什么操作」这种记忆加理解手工模拟题是过程题考的是你能不能把算法在具体数据上一步步执行完算法设计题是表达题考的是你能不能把思路翻译成别人看得懂的伪代码。三种能力不能互相替代很多人客观题能拿 90%手工模拟题却只对一半原因就在这里。按这张表安排复习顺序和按章节顺序从头看效率差得很远。第一章绪论里的概念题只占两三分而排序和查找两章的内容撑起了手工模拟题的绝大部分。真要突击先保手工模拟题和复杂度分析这两块的知识点集中、题型固定、练三道就能见效客观题靠刷选择题库边际收益递减得很快。2.2 判分点在哪过程分比结果分贵手工模拟题的评分规则几乎都是按趟给分。「写出直接插入排序每一趟的结果」给一个六元素数组标准答案有五趟中间结果加一个最终结果评分细则通常是每趟 1 分最后一趟写错但前面四趟对照样能拿 4 分。反过来直接跳到最终有序结果中间全空着最多给 1 分。这就是为什么这类题必须老老实实写过程哪怕你心算就知道答案。算法设计题的判分更明显是三段式思路描述、伪代码或代码、复杂度分析常见配比是 3:5:2 或者 3:6:1。只贴一段代码不写思路很多时候拿不到满分思路写清楚了代码有个小 bug思路分基本能保住。我见过不少卷子两个学生代码几乎一样一个写了三行思路说明一个没写分差能有 3 分。这三行字是整个卷子里性价比最高的三行。复杂度分析题同样有套路。要求「分析下面这段代码的时间复杂度」标准做法是逐层标出循环执行次数再相乘而不是直接报结论。哪怕结论写错过程标对了还能拿步骤分。空白只写一个 O(n²)对了拿满分错了零分。2.3 用期望失分排复习顺序知道分值还不够还得知道自己的正确率。同样是 30 分的手工模拟题正确率 45% 和正确率 85% 完全是两种复习优先级。用「分值 ×1 − 自估正确率」算出期望失分从高到低排就是考前三天该补的顺序。下面这段脚本可以直接改数字跑。# 按期望失分给题型排复习优先级 # 每一项(题型, 卷面分值, 自估正确率) sections [ (选择题, 20, 0.85), (填空题, 10, 0.70), (判断题, 10, 0.90), (手工模拟题, 30, 0.45), (算法设计题, 20, 0.30), (复杂度分析, 10, 0.60), ] rows [] for name, score, acc in sections: lose score * (1 - acc) # 期望失分 分值 × 丢分概率 rows.append((name, score, acc, lose)) rows.sort(keylambda r: r[3], reverseTrue) total sum(r[3] for r in rows) or 1 for name, score, acc, lose in rows: print(f{name:8} 分值{score:3} 正确率{acc:5.0%} f期望失分{lose:5.1f} 占总失分{lose/total:6.1%})逻辑很直白lose越大说明这块补上去能捞回的分越多排在前面先补。三个参数里最关键的是acc一定要用做过真题之后的真实正确率别填理想值——把手工模拟题的正确率填成 0.9脚本就会让你去刷选择题结果正式考试那 30 分大面积失守。score要按你手上那份卷子的实际分值改别照抄这张表。跑出来的排序如果显示手工模拟题和算法设计题占了总失分的七成以上那复习计划就定点到这两块其他题型保持手感即可。这套算法在带课时用它排模拟卷的题量也很好用——按期望失分分配练习量比平均分配省时间。3. 手工模拟题的代码复现链表、栈队列、二叉树怎么在纸上走对手写模拟最靠不住的地方是「我以为我推对了」。指针一改前后关系错一位后面全错自己还看不出来。我的做法是把卷子上那道题原封不动敲进编辑器跑一遍让程序把每一步的状态打出来再跟纸上写的对照。跑通一次这类题基本就不会再错。3.1 带头结点的单链表插入删除的指针顺序卷子上的链表题十有八九是带头结点的题干会明确写「头结点不存储数据、不计入表长」。这个约定必须先确认因为它决定插入时要不要单独处理空表。下面这段把插入和删除都写成「先找前驱、再改指针」的统一形式。class Node: __slots__ (val, next) def __init__(self, val): self.val val self.next None def build(vals): 带头结点建表head.val 无意义 head Node(None) tail head for v in vals: tail.next Node(v) tail tail.next return head def show(head, tag): cur, out head.next, [] while cur: out.append(str(cur.val)); cur cur.next print(f{tag}: - .join(out)) def insert_after(head, pos, val): 在第 pos 个数据结点之后插入pos0 表示插在表头 p head for _ in range(pos): if p is None: return False p p.next if p is None: return False node Node(val) node.next p.next # 先接后 p.next node # 再断前顺序不能反 return True def delete_pos(head, pos): 删除第 pos 个数据结点pos 从 1 开始 p head for _ in range(pos - 1): if p.next is None: return False p p.next q p.next if q is None: return False p.next q.next q.next None # 断开被删结点便于回收 return Trueinsert_after里两行赋值的顺序是这类题的全部考点所在。node.next p.next必须在p.next node之前反过来的话p后面的整条链就丢了卷面上表现为「插入后链表长度变短」这是批改时最常见的错误图形。delete_pos里pos从 1 开始计算pos1删的是第一个数据结点循环只走 0 次p停在头结点上逻辑自然成立——这就是带头结点的好处第一个位置和中间位置用同一段代码。跑一下看过程h build([3, 7, 11, 15]) show(h, 初始) insert_after(h, 2, 9); show(h, 第2个后插入9) delete_pos(h, 1); show(h, 删除第1个) delete_pos(h, 99); show(h, 删除越界位置)输出应该是3 - 7 - 9 - 11 - 15和7 - 9 - 11 - 15最后一次返回 False 且链表不变。如果你纸上的结果和这个对不上问题一定出在指针赋值顺序或者pos的起始基准上这两处排查比盯着纸看快得多。3.2 循环队列的队满判定三个变量的写法最容易错循环队列是填空和判断的重灾区通常给一个容量为MAXSIZE的数组、front和rear两个指针让你判断队空队满、算队长。判满有三种流派少用一个存储单元、设size计数、设tag标记。卷子题干里给了哪个就得按哪个写混用必错。少用一个单元的写法最常见front rear队空(rear 1) % MAXSIZE front队满队长(rear - front MAXSIZE) % MAXSIZE实际可用元素数只有MAXSIZE - 1。带size计数的写法front rear队空size MAXSIZE队满队长直接就是size。下面用 Python 把第一种写出来其他两种只是改判满条件。class CircularQueue: def __init__(self, maxsize): self.maxsize maxsize self.data [None] * maxsize self.front 0 self.rear 0 self.size 0 def is_empty(self): return self.front self.rear # 与 size 无关 def is_full(self): return self.size self.maxsize # 本实现用 size 判满 def enqueue(self, x): if self.is_full(): return False self.data[self.rear] x self.rear (self.rear 1) % self.maxsize self.size 1 return True def dequeue(self): if self.is_empty(): return None x self.data[self.front] self.front (self.front 1) % self.maxsize self.size - 1 return x def length(self): return self.size这里我在代码里用了size判满is_empty仍然用front rear这是两个流派混着写属于最典型的自我误导来源。如果卷子用「少用一个单元」判满那么enqueue必须先判(rear 1) % maxsize front且实际能装maxsize - 1个元素length()要用(rear - front maxsize) % maxsize。考试时建议先在草稿上把front、rear、size三个变量的当前值列成一行每执行一次操作更新一次比在脑子里转圈可靠。3.3 由前序和中序重建二叉树再回推遍历序列「已知前序序列和中序序列画出这棵二叉树」是几乎必出的题。手画的时候容易在左右子树的边界上数错一位用代码重建一遍立刻现形。关键是前序的第一个元素是根在中序里找到这个根左边就是左子树的中序右边是右子树的中序长度确定之后再回前序里切。class TNode: def __init__(self, *seq): self.val seq[0] if seq else None self.left seq[1] if len(seq) 1 else None self.right seq[2] if len(seq) 2 else None def rebuild(pre, mid): if not pre or not mid: return None root_val pre[0] k mid.index(root_val) # 根在中序中的位置 node TNode(root_val) node.left rebuild(pre[1:k1], mid[:k]) node.right rebuild(pre[k1:], mid[k1:]) return node def postorder(t, out): if t is None: return postorder(t.left, out) postorder(t.right, out) out.append(t.val) def levelorder(t): res, q [], [t] if t else [] while q: cur q.pop(0) res.append(cur.val) if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) return resk是关键参数。mid.index返回 0 起下标所以左子树中序是mid[:k]共k个元素对应前序里的pre[1:k1]也是k个右子树中序mid[k1:]长度是n-1-k前序同样从k1切到末尾。这四个切片只要有一个写错树就长歪了而且一般要到画完下三层才能发现。卷一上的前序中序都是去重的如果序列里有重复值index找到的可能不是你想的那个根这种情况卷子一般不会出但自己写练习时要留意。重建完顺手把后序和层序打出来正好对应卷子上「写出该树的后序遍历序列」和「写出层序遍历序列」两小问。层序遍历的队列那一行q.pop(0)在列表上做是 O(n) 的考试写伪代码时无所谓真要跑大数据量换collections.deque更合适。4. 图与排序的大题模板让每一趟中间结果都能打印出来排序和图算法这两块卷子上要求的都是「过程可视化」画出每一趟排序的结果、填写 Dijkstra 的距离表和前驱表。人脑模拟这些过程出错概率极高正确做法是写一遍、打印每一趟、跟答案核对。4.1 邻接矩阵还是邻接表先看卷子要你填什么表这两种存储方式选哪个卷子一般会直接指定但有一类题干只给一张图让你自己「设计合适的存储结构并实现」。判断依据是边数和顶点数的关系稠密图用邻接矩阵判断两点间是否有边 O(1) 直接查稀疏图用邻接表遍历某个顶点的所有邻接点只要花 O(度) 的时间。顶点数 100 以内、边数接近 n² 的邻接矩阵反而更好写INF填满的空位置也不心疼。真正的坑在边上带权且图是小规模稀疏的时候。用邻接矩阵Dijkstra 的每一轮扫描是 O(n²)看起来笨但正好对应卷子上那张手算表用邻接表加优先队列是 O((ne)log n)跑得快但打印出来的过程跟卷子上要求填的表格式对不上。我的一般做法是需要模拟手工表的场合用邻接矩阵需要实际跑的场合用邻接表加堆。INF float(inf) def build_matrix(n, edges, directedFalse): edges: [(u, v, w)]顶点编号 0..n-1 adj [[INF] * n for _ in range(n)] for i in range(n): adj[i][i] 0 for u, v, w in edges: adj[u][v] w if not directed: adj[v][u] w return adjadj[i][i] 0这一步不能省。很多人建完矩阵忘了把对角线置零后续 Dijkstra 松弛时会把自己到自己的距离更新成一个正数结果全错。directed参数用来切换有向和无向无向图对称赋值一次就够不要写成两次循环。4.2 Dijkstra 手算表的逐行生成卷子上的 Dijkstra 题通常给一张带权图和源点要求填一张表每一轮选中的顶点、各顶点的当前最短距离、以及最终的最短路径。用代码把每一轮的状态打印出来正好就是那张表的内容。def dijkstra(adj, src, namesNone): n len(adj) name names or [str(i) for i in range(n)] dist [INF] * n prev [-1] * n done [False] * n dist[src] 0 def fmt(a): return .join(∞ if x INF else str(x) for x in a) print(初始 dist , fmt(dist)) for step in range(n): u -1 for i in range(n): if not done[i] and (u -1 or dist[i] dist[u]): u i if u -1 or dist[u] INF: break done[u] True for v in range(n): if not done[v] and dist[u] adj[u][v] dist[v]: dist[v] dist[u] adj[u][v] prev[v] u print(f第{step1}轮 选中 {name[u]:3} fdist {fmt(dist)} prev {prev}) return dist, prev三个数组的作用必须分清dist是当前已知最短距离会不断被松弛变小prev记录每个顶点的前驱最后沿prev回溯就是最短路径done标记已经确定终点的顶点一旦置 True 不再参与后续松弛——这是 Dijkstra 能保证正确的前提也是它不能处理负权边的原因。u -1的初值判断是为了让第一个候选点无条件入选不要写成dist[i] dist[u]直接比较那样u初值 0 会漏掉其他情况。names参数是为了输出时显示 A、B、C 这类顶点名卷子上的图一般用字母标注用names[A,B,C,D,E]传进去打印出来的表直接就能抄。fmt里把INF显示成 ∞跟卷面符号一致核对时不容易看串。4.3 六种排序的每一趟输出与稳定性对照排序题在卷面上通常有两种问法给一个数组写出某算法每一趟之后的结果或者比较几个算法的复杂度、稳定性。前一种必须逐趟打印后一种靠下面这张表背。算法平均最坏空间稳定性卷面常考点直接插入O(n²)O(n²)O(1)稳定每趟结果、比较次数希尔O(n^1.3)O(n²)O(1)不稳定增量序列、按增量分组冒泡O(n²)O(n²)O(1)稳定一趟有无交换快速O(nlogn)O(n²)O(logn)不稳定一次划分结果、枢轴位置简单选择O(n²)O(n²)O(1)不稳定交换次数堆排序O(nlogn)O(nlogn)O(1)不稳定建初堆、每次调整归并O(nlogn)O(nlogn)O(n)稳定每趟归并结果直接插入排序的逐趟打印最短先写它def insertion_trace(a): a a[:] print(初始:, a) for i in range(1, len(a)): key, j a[i], i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key print(f第{i}趟:, a) return akey必须先把a[i]存下来因为a[i]的位置马上会被覆盖。while条件的a[j] key决定了算法是稳定的相等时不后移相同元素的相对顺序保持不变。如果卷子问「该算法是否稳定为什么」答案就落在这个上写成就不稳定了。快速排序的一次划分是最容易和标准答案对不上的地方因为不同教材的划分写法不同。下面这种挖坑法枢轴取第一个元素def partition_trace(a, lo, hi, out): pivot a[lo] i, j lo, hi while i j: while i j and a[j] pivot: j - 1 a[i] a[j] while i j and a[i] pivot: i 1 a[j] a[i] a[i] pivot out.append((lo, hi, i, a[:])) # 记录区间、枢轴落点、当前数组 return i def quick_trace(a, lo0, hiNone): a a[:]; hi len(a) - 1 if hi is None else hi out [] def go(lo, hi): if lo hi: p partition_trace(a, lo, hi, out) go(lo, p - 1); go(p 1, hi) go(lo, hi) for lo, hi, p, snap in out: print(f区间[{lo},{hi}] 枢轴落位 {p}: {snap}) return aout里存的是每次划分完成时的数组快照卷子上要求「写出第一趟快速排序后的结果」就是out[0][3]。注意这里的「一趟」有两种理解一种是一次划分一种是一整层递归全部划分完。题干里如果写「以第一个元素为枢轴写出一次划分后的序列」按一次划分理解写「写出第一趟排序结果」多数教材指的是一层递归做完。5. 避坑批过几百份卷子后反复出现的错误下面这些不是知识点没掌握而是掌握了的同学照样会犯。每条按「现象 → 原因 → 解决」写考场上遇到对应的情形直接照做。5.1 下标基准不统一思路对结果差一位现象next 数组、KMP 的失配位置、树的孩子编号明明推导过程没问题跟标准答案一比全部错一位。原因不同教材对同一结构的编号起点不同。字符串有的按 0 起存、next[0] -1有的按 1 起存、next[1] 0堆的孩子结点有的用2i和2i1有的用2i1和2i2。题干里往往只在第一行小字里标了一下存储位置一眼扫过去就漏了。解决动笔之前先看题干有没有给出数组下标标注或者存储示意图没有就在草稿纸左上角写下「数组从 X 开始」并圈出来。写完第一趟结果后立刻用前两个元素反推验证如果字符串首字符的 next 值是 0说明是从 1 起编号后面全部按这个基准写。这一步只花二十秒能避免整道题归零。5.2 快速排序的划分写法和教材不一致现象一次划分后的序列跟标准答案不同但自己检查每一步都对。原因划分策略至少有三种常见写法——挖坑法、左右交换法、双指针扫描法枢轴选取也有取首元素、取中间元素、三数取中几种。同一组数据不同策略划分完的中间序列可以完全不同最终有序结果却一样。解决考前确认这门课用的教材版本按教材上的伪代码原样模拟别用自己习惯的写法。考试时如果实在记不清题干通常会提示「按教材算法」那就老实按教材的来。写过程时把枢轴值和每一轮交换的两个位置标出来即使最终序列和答案不同过程分也能拿到。5.3 算法设计题只写代码不写思路和复杂度现象代码逻辑完全正确20 分的题只拿到 12 分左右。原因算法设计题的评分细则基本是三段式——思路、伪代码、复杂度。代码写对了只覆盖中间一段思路和复杂度两段的分数直接丢掉。更亏的是代码有小 bug 的时候没有思路说明做兜底阅卷人无法判断你是思路错还是笔误。解决每题固定写三块用「思路」「伪代码」「复杂度」三个小标题分开。思路部分写三五句说清用什么数据结构、为什么选它、关键步骤是什么。复杂度部分时间和空间都写空间别忘了把辅助数组和递归栈都算进去。这三行标题本身就是给阅卷人的路标写上去就有分。5.4 递归算法的空间复杂度漏算调用栈现象写「空间复杂度 O(1)」实际是 O(logn) 或 O(n)。原因只数了代码里显式申请的数组忽略了递归调用栈的深度。快排的空间复杂度 O(logn) 来自递归深度归并排序的 O(n) 来自辅助数组树的遍历 O(h) 来自栈深度这三类是一回事。解决凡是代码里出现递归立刻在心里问一句「最深会递归多少层」把这个层数乘上每层的常数空间就是空间复杂度的主项。快排平均 O(logn) 最坏 O(n)归并稳定 O(n)二叉树遍历 O(h)这三条记住就行。同时注意空间复杂度的「最坏」和「平均」有时不同快排就是典型题目问哪个就答哪个。5.5 Dijkstra 手算表漏更新前驱现象距离数组全对前驱数组某些项是空的或者跟答案对不上最后要求写最短路径的那一小问丢分。原因松弛成功时只更新了dist忘了同步写prev。手算时更容易犯因为注意力都在比较距离大小上。解决手算表上多加一列前驱每一轮只要某个顶点的距离被改小就在前驱列写上当前选中的顶点。养成「改距离必改前驱」的肌肉记忆代码里这两行永远挨着写。最后还原路径时从终点沿前驱往回倒推倒到源点为止再反转。6. 用对拍脚本把整份卷子跑成自测用例最后一步是把前面写的所有代码串成一套自测。手写模拟最大的风险是「自己检查自己」你按自己的理解推一遍再用同样的理解检查一遍错了也看不出来。对拍就是拿一个绝对可靠的参考实现跟你的实现比结果随机生成几百组数据只要有一组不一致就打印出来。import random def check_sort(fn, n200, rounds500): fn 接收列表返回新列表与内置 sorted 对拍 for r in range(rounds): a [random.randint(-50, 50) for _ in range(random.randint(0, n))] got fn(a[:]) if got ! sorted(a): print(翻车样本:, a, 你的结果:, got) return False print(f排序对拍通过 {rounds} 轮) return True def floyd(adj): 最短路参考实现用来校验 Dijkstra 的结果 n len(adj) d [row[:] for row in adj] for k in range(n): for i in range(n): for j in range(n): if d[i][k] d[k][j] d[i][j]: d[i][j] d[i][k] d[k][j] return d def check_dijkstra(dij_fn, n7, rounds200): for _ in range(rounds): adj [[INF] * n for _ in range(n)] for i in range(n): adj[i][i] 0 for i in range(n): for j in range(i 1, n): if random.random() 0.5: w random.randint(1, 20) # 只生成正权Dijkstra 才有效 adj[i][j] adj[j][i] w ref floyd([row[:] for row in adj]) for src in range(n): got, _ dij_fn([row[:] for row in adj], src) if [round(x, 6) for x in got] ! [round(x, 6) for x in ref[src]]: print(翻车:, src, adj, got, ref[src]); return False print(f最短路对拍通过 {rounds} 轮) return Truecheck_sort的rounds给 500 就够n给 200 能覆盖大多数边界包括空数组和全相同元素。check_dijkstra里w必须取正数负权边会让 Dijkstra 失效这时候对拍不过不是你的代码错是算法前提不成立。round到小数点后 6 位是为了避免浮点误差误报用整数权值的话其实可以去掉。把这套自测跑一遍覆盖面大致如下表模块对拍对象建议轮数覆盖的边界排序内置sorted500空、单元素、全相同、已逆序最短路Floyd200不连通、单点、含重边链表Pythonlist模拟300头插、尾插、越界删除二叉树重建重建后再遍历回原序列200单支树、满二叉树链表和二叉树的对拍稍微改一下思路链表操作后把值 dump 成列表跟list的对应操作比二叉树重建后把前序和中序重新遍历出来跟输入的前序中序比对能对上说明结构没建歪。这两块的代码量不大照着前面的框架改二十分钟就能写出来。我自己带课时的一个习惯是每份模拟卷出完之后必须跑一遍对拍只要有一轮不过就说明题目数据或者标准答案有问题。这个习惯救过好几次——有次手工出的排序题标准答案是我自己心算的跑完发现第三趟写错了要是直接发下去就是几十个人跟着错。数据结构这门课凡是能被代码验证的东西就别靠脑子验证。希望帮到你。本文还有配套的精品资源点击获取