简介：这份湖北大学数据结构期末试卷（2022—2023学年度第一学期A卷）面向计算机与信息工程学院信息安全等专业学生，用于期末复习与知识点自测。试卷覆盖图论、查找算法、二叉树遍历、递归函数与存储结构等核心章节，题型包含判断分析、简答与应用分析，涉及带权有向图关键路径、邻接表存储、顺序查找平均查找长度、先序中序推后序、递归求幂调用次数、链栈适用性、二路归并排序、普里姆与克鲁斯卡尔算法、二叉排序树构造及哈希线性探查等内容，兼顾理论分析与算法实现。资源为1个PDF文件，压缩包约252KB，完整呈现原卷试题纸与分值分布，便于打印练习。目前已有375人学习下载，适合需要系统梳理考点、检验复习效果的读者对照使用。
1. 一份期末卷子拆开看：数据结构到底考什么、怎么练
很多人复习数据结构，习惯把教材从头翻到尾，结果图论看了一半又回去翻链表，最后什么都没记住。我拿到这份试卷的第一反应不是“题难不难”，而是“它把考点分布得很清楚”——判断题、简答题、应用分析题、程序设计题四类，覆盖了图、树、查找、排序、递归、存储结构六个模块。换句话说，它本身就是一份现成的复习路线图。如果你正在准备数据结构期末，或者想用一套完整的题目检验自己的掌握程度，这份卷子的价值不在于“押题”，而在于它把每个知识点的考查方式都摆出来了：概念辨析考判断，原理理解考简答，过程推导考应用，代码能力考设计。下面我按题型拆开讲，每类题怎么下手、参数怎么算、哪里容易翻车。
2. 判断题与简答题：概念辨析的五个高频翻车点
2.1 关键路径缩短不等于工期缩短
判断题第一题问的是：缩短关键路径上某个活动的时间，是否一定能缩短整个工程工期。很多人凭直觉选“对”，因为关键路径决定最短工期，缩短它当然有用。但这里有个前提被忽略了——缩短之后，这条路径可能不再是关键路径，另一条路径变成了新的关键路径，总工期由新的关键路径决定。所以“一定”这个词就是陷阱。正确的分析思路是：缩短关键路径上的活动时间后，需要重新计算网络图，看是否有其他路径的时长超过了缩短后的原关键路径。如果没有，工期确实缩短；如果有，工期由新的最长路径决定，可能不变甚至变化幅度小于预期。
注意：这类题的通用套路是找“一定”“必然”“所有”这类绝对化表述，数据结构里绝大多数绝对化判断都是错的，除非是定义层面的陈述。
2.2 顺序查找ASL的适用条件
判断题第二题说顺序查找不成功的平均查找长度是(n+1)/2。这个结论本身没错，但它有一个隐含条件：查找每个元素的概率相等，且不成功查找发生在所有可能的查找位置等概率的情况下。如果题目没有明确这个前提，严格来说这个结论不能直接套用。实际考试中，这类题通常考的是“你是否知道公式的适用边界”。顺序查找成功时的ASL确实是(n+1)/2，不成功时是n+1（需要比较n+1次才能确定不在表中），这两个别搞混。
2.3 出栈序列的合法性判断
判断题第三题给出进栈序列1到6，问2,3,5,1,6,4是否可能是出栈序列。判断方法不复杂，但手工模拟容易乱。我一般用“栈模拟法”：按进栈序列依次压栈，每次压入后检查栈顶是否等于当前需要的出栈元素，如果是就弹出，继续检查下一个出栈元素。具体到这个序列：压1，压2，栈顶2匹配，弹出2；压3，栈顶3匹配，弹出3；压4，压5，栈顶5匹配，弹出5；此时栈内是1,4，下一个需要弹出1，但栈顶是4，不匹配，继续压6，栈顶6匹配，弹出6；此时栈内是1,4，需要弹出4，但栈顶是1，不匹配。最终无法完成，所以这个序列不合法。
2.4 二叉树遍历的反推
判断题第五题给了中序ABCDE和先序CABED，问后序是否是BADCE。反推方法是：先序的第一个C是根，在中序中找到C，左边AB是左子树，右边DE是右子树。左子树先序是AB，中序是AB，所以A是根，B是右孩子；右子树先序是ED，中序是DE，所以E是根，D是左孩子。整棵树的后序应该是B A D E C，不是BADCE。这类题的关键是每一步都要在两种序列中同步定位，不能只凭感觉画。
2.5 递归函数的调用次数
简答题第二题的函数fun(x,n)计算x的n次幂，递归终止条件是n==1。fun(2,5)的计算过程是2×fun(2,4)=2×2×fun(2,3)=…，总共发生4次递归调用（n从5降到1，每次减1，调用次数是n-1）。如果问“最多发生几次”，答案取决于n的初始值，递归深度是n-1。这里容易错的地方是把“递归调用次数”和“乘法次数”搞混，乘法确实做了n-1次，但递归调用也是n-1次，因为每次调用只做一次乘法然后返回。
3. 应用分析题：手算过程的标准化模板
3.1 二路归并排序的每趟结果
题目给的序列是{15,5,16,2,25,8,20,9,18,12}，要求写出二路归并每一趟的结果。二路归并的“一趟”指的是把当前所有长度为L的有序段两两合并成长度为2L的有序段。初始每个元素是长度1的有序段。
第一趟：两两合并相邻元素，得到{5,15},{2,16},{8,25},{9,20},{12,18}，写完整序列就是5,15,2,16,8,25,9,20,12,18。
第二趟：把长度2的有序段两两合并。{5,15}和{2,16}合并成{2,5,15,16}；{8,25}和{9,20}合并成{8,9,20,25}；{12,18}单独保留。序列变成2,5,15,16,8,9,20,25,12,18。
第三趟：{2,5,15,16}和{8,9,20,25}合并成{2,5,8,9,15,16,20,25}；{12,18}保留。序列变成2,5,8,9,15,16,20,25,12,18。
第四趟：最后两段合并，得到2,5,8,9,12,15,16,18,20,25。
提示：写归并每趟结果时，建议把每段用花括号标出来再合并，直接写最终序列容易漏掉中间步骤的分数。
3.2 普里姆算法与克鲁斯卡尔算法的执行过程
题目给了一个带权无向图，以顶点0为起点构造最小生成树。普里姆算法的核心是维护一个已选顶点集合，每次从连接已选集合和未选集合的边中选权值最小的。执行过程需要逐步写出每次选择的边和加入的顶点。克鲁斯卡尔算法则是把所有边按权值排序，从小到大依次选取，如果加入的边不构成环就保留，否则跳过。
这两种算法的执行过程在答题时要注意：普里姆算法必须从指定起点开始，每一步的选择依赖于当前已选集合；克鲁斯卡尔算法不依赖起点，全局按边权排序。考试中常见的失分点是普里姆算法没有从指定顶点开始，或者克鲁斯卡尔算法选边时没有检查环。
3.3 二叉排序树的构造与ASL计算
先序序列{12,5,2,8,6,10,16,15,18,20}构造二叉排序树，方法是按先序顺序依次插入。12是根，5比12小放左边，2比5小放左边，8比5大放右边，6比8小放左边，10比8大放右边，16比12大放右边，15比16小放左边，18比16大放右边，20比18大放右边。
中序遍历结果就是所有元素升序排列：2,5,6,8,10,12,15,16,18,20。
等概率下查找成功的ASL计算方法是：每个节点的查找长度等于它的层数，把所有节点的层数加起来除以节点总数。查找不成功的ASL需要统计所有外部空指针位置的查找长度，通常画图时在每个空指针处标出比较次数。
3.4 平衡二叉树的插入与调整
序列{4,5,7,2,1,3,6}构建平衡二叉树，关键是每次插入后检查平衡因子，如果不平衡就判断调整类型。插入4，根节点。插入5，4的右孩子。插入7，此时4的平衡因子变成-2，属于RR型，需要左旋，5变成根，4变成5的左孩子，7是5的右孩子。继续插入2，放在4的左边。插入1，4的平衡因子变成2，属于LL型，右旋，2变成根，1是2的左孩子，4是2的右孩子。插入3，放在4的左边。插入6，放在7的左边。每一步都要画出调整前后的树形，并标注调整类型（LL、RR、LR、RL）。
3.5 哈希表构造与ASL计算
关键字{32,13,49,24,38,21,4,12}，哈希函数H(key)=key%7，地址空间0到9，线性探查法解决冲突。
计算每个关键字的初始哈希地址：32%7=4，13%7=6，49%7=0，24%7=3，38%7=3（冲突，探查4，再探查5），21%7=0（冲突，探查1），4%7=4（冲突，探查5，再探查6，再探查7），12%7=5（冲突，探查6，再探查7，再探查8）。
最终哈希表：地址0放49，地址1放21，地址2空，地址3放24，地址4放32，地址5放38，地址6放13，地址7放4，地址8放12，地址9空。
查找成功的ASL：每个元素的比较次数分别是1,1,1,1,2,2,4,4，总和16，除以8得2。查找失败的ASL需要从每个地址出发探查到空地址的比较次数，通常按哈希函数可能映射到的地址计算。
4. 程序设计题：两道算法题的递归模型与链表操作
4.1 求二叉树度为2的结点个数
题目要求设计算法求二叉树中度为2的结点个数，结点类型已经给出。递归模型的设计思路是：如果当前结点为空，返回0；如果当前结点左右孩子都不为空，返回1加上左子树的结果加上右子树的结果；否则返回左子树结果加右子树结果。
typedef struct node { char data; struct node *lchild, *rchild; } BTNode; int countDegree2(BTNode *b) { if (b == NULL) return 0; // 空结点，度为2的结点数为0 if (b->lchild != NULL && b->rchild != NULL) return 1 + countDegree2(b->lchild) + countDegree2(b->rchild); else return countDegree2(b->lchild) + countDegree2(b->rchild); }递归模型的核心是：度为2的结点贡献1，度为1或0的结点贡献0，然后递归累加左右子树。参数b是当前子树根节点，返回值是这棵子树中度为2的结点总数。时间复杂度O(n)，空间复杂度O(h)，h是树高。
4.2 删除单链表中值最小的所有结点
题目要求删除带头结点单链表L中结点值最小的所有结点，可能有多个。思路是：先遍历一遍找到最小值，再遍历一遍删除所有等于最小值的结点。
typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; void DelNode(LinkList L) { if (L->next == NULL) return; // 空表直接返回 int min = L->next->data; LNode *p = L->next->next; while (p != NULL) { // 第一遍：找最小值 if (p->data < min) min = p->data; p = p->next; } LNode *pre = L, *q = L->next; while (q != NULL) { // 第二遍：删除所有最小值结点 if (q->data == min) { pre->next = q->next; free(q); q = pre->next; } else { pre = q; q = q->next; } } }第一遍遍历确定最小值，第二遍用pre指针维护前驱，遇到等于最小值的结点就跳过并释放。注意删除后q要更新为pre->next，不能直接q=q->next，因为q已经被释放了。这个算法的时间复杂度是O(n)，空间复杂度O(1)。
5. 从这份卷子反推复习策略：三个我踩过的坑
5.1 别把“看懂”当成“会写”
我刚开始复习数据结构的时候，看一遍教材觉得什么都懂了，一合上书手写归并排序的每趟结果就卡住。这份卷子里的应用分析题全是过程推导，不是选择题，你必须能一步一步写出来。我的建议是拿一张白纸，把每道题的推导过程完整写一遍，写完对照答案看哪一步跳了或者错了。特别是普里姆算法和克鲁斯卡尔算法，画图比写字更重要，边画边标序号。
5.2 递归题先写递归模型再写代码
程序设计题里的二叉树度为2结点个数，很多人直接写代码，结果边界条件漏了。正确的顺序是先写出递归模型：f(b) = 0 当b为空；f(b) = 1 + f(b->lchild) + f(b->rchild) 当左右孩子都存在；f(b) = f(b->lchild) + f(b->rchild) 其他情况。模型写清楚了，代码就是翻译。链表删除最小值那道题，关键是两遍遍历，第一遍找最小值，第二遍删。不要试图一遍搞定，容易出错。
5.3 哈希表的ASL计算要分清成功和不成功
哈希表那道题，查找成功的ASL是每个元素的比较次数之和除以元素个数，查找不成功的ASL是从每个哈希地址出发到第一个空地址的比较次数之和除以哈希地址总数（这里是10，不是7）。很多人把不成功的分母也写成元素个数，直接翻车。另外线性探查法删除元素时不能直接置空，否则会截断后续元素的查找路径，通常用标记法处理。
5.4 平衡二叉树的调整类型判断
平衡二叉树的四种调整类型LL、RR、LR、RL，判断方法是看插入位置相对于最小不平衡子树根节点的方向。LL是左孩子的左子树插入，RR是右孩子的右子树插入，LR是左孩子的右子树插入，RL是右孩子的左子树插入。我习惯在每次插入后从插入点往上找第一个平衡因子绝对值大于1的节点，然后判断类型。调整的时候注意旋转后子树的根节点要正确连接到原父节点上。
5.5 出栈序列的快速验证
出栈序列的合法性判断，除了栈模拟法，还有一个经验：如果出栈序列中某个元素后面出现了比它小且不是按降序排列的元素，基本可以判定不合法。但这个方法不是绝对可靠，考试时还是老老实实用栈模拟，一步一步压弹，别图快。
这份卷子的价值在于它把数据结构的核心考点都覆盖了，而且题型分布合理。如果你能把这七页纸上的每道题都独立做一遍，对照答案找到自己的薄弱环节，期末复习的效率会比翻教材高很多。我后来每次带人复习数据结构，都让他们先做一套完整的卷子，再针对错题回去补知识点，比从头看书快得多。希望帮到你。
本文还有配套的精品资源，点击获取
