简介这是一份湖北大学数据结构课程期末试卷2022-2023学年A卷面向计算机类相关专业的学生可用于期末复习、考研自测或教师出题参考。试卷以闭卷形式呈现包含判断分析题、简答题与应用分析题覆盖带权有向图与关键路径、邻接表存储、栈序列判断、平均查找长度、二叉树遍历还原、递归函数与链栈选用等核心知识点能帮助学生系统检验图论、查找、二叉树及存储结构等章节的掌握程度。压缩包内为单个PDF文件共252KB内容为原版试卷扫描或电子版排版清晰可直接打印练习。已有374人学习下载是该校数据结构期末备考的高频参考资料。借助这份原卷读者可熟悉湖北大学出题风格与常见题型梳理各章核心考点并查漏补缺提升应试效率。1. 期末试卷不是拿来背的先看它到底在考什么如果你搜到《湖北大学数据结构期末试卷》这个标题多半是想找原题或标准答案。我的建议恰恰相反期末试卷最有价值的不是那套题本身而是它背后的题型结构。选择题在考概念边界应用题在考手推过程算法设计题在考代码熟练度三个板块分别对应“懂没懂、会不会推、能不能写”。把这三个层面逐一拆开练比背十份答案都管用。这篇笔记不需要某个具体的年份卷按我拆期末试卷的习惯带你过一遍题型分布、复习主线、算法模板、易错点最后是一周自测方案。2. 拆解数据结构期末复习的题型构成选择题、应用题与算法题2.1 选择题与判断题30 分里藏着的概念边界结构期末卷的第一大题基本都是选择或判断题量在 10 到 15 题之间单题分不高但覆盖极广。常见做法是考那些“看起来像、实际上不是”的概念边界逻辑结构和存储结构谁决定谁、队列和栈的出队出栈顺序、顺序表和链表各自适用什么场景、二叉树的第 i 层最多几个结点、连通图和强连通图的区别、哈希冲突的线性探测与链地址法。真正的难点不是背定义而是识别题目里的陷阱描述。比如“栈顶元素永远不能访问”这种说法一眼假但“循环队列的队满条件是 rear front”就有迷惑性因为很多教材用牺牲一个存储单元来区分队满与队空这时 rear front 反而表示队空。备考这类题最好的办法是把教材每章结尾的概念题扫一遍边做边把“容易混淆的两句话”记在同一行。你会发现选择题本质上是在考你对定义边界的敏感性。这里有一个复习小技巧把每章的关键定义抄成“A 是 B但 B 不一定是 A”的句式。例如“二叉排序树的中序遍历是有序的但中序遍历有序的二叉树不一定是二叉排序树”——这里涉及二叉排序树定义其实是错的应该说“中序遍历有序的二叉树就是二叉排序树”因为二叉排序树就是中序有序的判定标准。这种句式的辨析能力直接决定选择题正确率。2.2 应用题与画图题手推过程是隐性得分点应用题是结构卷里最容易被低估的部分它通常包括给定遍历序列还原二叉树、构造哈夫曼树并计算带权路径长度、对给定图写出深度优先和广度优先遍历序列、用 Prim 或 Kruskal 算法画最小生成树、用 Dijkstra 算法填最短路径表格、给定哈希函数和冲突处理方法构造哈希表并求平均查找长度。这些题目的共同特点是结果对还不够判卷时会看你推导过程是否完整。以 Dijkstra 为例正确的答题过程必须在每一步标明“当前选定顶点、更新了哪些 dist 值、已确定的最短路径集合”只写最终结果通常会被扣过程分。哈夫曼树则要求新结点合并的顺序有迹可循WPL 的计算式要么写成叶子权值乘以路径长度的连加要么写成每次合并代价之和。如果你是期末复习我建议找一张 A4 纸专门练手推每次把步骤写到不用回看题目也能明白你在算什么这样在考场上的得分率会明显提高。这类题还有一个隐性考点数组存储的二叉树还原。给定一个顺序存储的完全二叉树数组让你画出逻辑结构并写出前序遍历。很多人在这一步翻车原因是不记得“下标为 i 的结点左孩子在 2i1右孩子在 2i2”这个地址映射。把它当成应用题里的计算题对待练两轮就能拿满。2.3 算法设计题占分最重也是拉开差距的地方算法设计题在结构期末卷里通常是最后一两道大题分值占比相当可观。根据这类高校常见试卷的配比选择题约 20 分判断题约 10 分应用题约 35 分算法设计题约 25 分其余为填空或简答。下面是这类试卷的典型题型分布表。题型常见题量大致分值考察目标选择题10~15 题20~30 分概念边界与复杂度判断判断题5~10 题8~10 分定义准确性应用题3~5 题30~40 分手推过程与结构认知算法设计题2~3 题20~30 分C 代码实现能力算法设计题的常见出题方向非常集中单链表反转或删除指定元素、二叉树先序或中序的非递归遍历、二叉树层序遍历、图的深度优先或广度优先遍历、折半查找的递归实现、快速排序的 partition 过程。你会发现这些题看起来都是教材习题但考试时要求在限定时间内手写完整 C 代码很多人不是不会思路而是写出来的代码边界处理不完整。第四章我会把高频算法模板逐一拆开讲。我在帮助一届又一届的学生复习过程中发现一个规律能把算法设计题写对的人都有一个共同的习惯——先在草稿纸上画一个最小规模的测试用例再对着用例写代码。比如写单链表反转前先画一个 1→2→3 的链表标出每一步指针的移动。这个习惯是千万不能省的尤其在考场上很紧张的时候。3. 按数据结构 C 语言版主线过复习路径从线性表到排序算法3.1 线性表与链表头指针、头结点、尾插法的细节线性表这一章看着简单却是算法设计题的题源之一。顺序表要掌握插入和删除时元素移动次数的计算最好情况、最坏情况、平均情况分别是 O(n)、O(1)、O(n) 这种复杂度推导要会自己列式子算。链表部分要区分头指针和头结点头指针是链表的起点标识头结点是首元结点前附加的一个节点。不带头结点的链表在删除首元结点时会有特判这往往是手写代码时最容易漏掉的分支。复习线性表时我常用一个自检办法给你一个带头结点的单向链表写出在值为 x 的结点前插入新结点的实现。这个操作需要同时维护前驱指针考的是对链表指针操作的综合能力。如果你能一次写对线性表这一章的概念题和算法题基本就稳了。注意顺序表和链表的选择题常从“按位查找、插入删除、内存利用率”三个维度出题把这三项的对比结论背下来即可。3.2 栈、队列与递归函数调用栈怎么考栈和队列这一章考试的重心集中在入栈出栈序列、循环队列判空判满、递归工作机制三块。入栈序列题不能靠枚举要从“后进先出”的性质推给定入栈序列 1,2,3问出栈序列能否为 3,1,2答案是“不能”因为 3 出栈时 2 已在栈顶2 必须先出。这类题用一个小栈在草稿纸上模拟是最快的。循环队列的判空判满有两个常见实现牺牲一个存储单元此时队空条件为 front rear队满条件为 (rear1) % MaxSize front另一种方案是设 size 或 tag 计数队满条件就变成 size MaxSize。答题时先看题目有没有说明“少用一个元素空间”再做判断不要默认一种方案。递归部分常考的是“递归函数改成循环需要用什么结构”——答案是栈因为递归本质是系统栈保存现场的过程。能把这个道理讲明白选择题基本不会错。3.3 树和二叉树遍历序列互求与线索化二叉树是期末卷的分值大户。其性质题包括第 i 层最多 2^(i-1) 个结点、深度为 h 的二叉树最多 2^h - 1 个结点、叶子结点数与度为 2 结点数的关系 n0 n2 1。满二叉树和完全二叉树的区别也是高频考点完全二叉树可以用数组作顺序存储这是由它的编号规则决定的。遍历部分的核心能力是“由两种遍历序列唯一确定一棵二叉树”前提是其中必须有中序序列。只给先序和后序无法唯一确定二叉树这个结论可以直接记。中序线索化的意义在于找到某结点的前驱或后继时不需要重新遍历整棵树线索指向的是遍历序列中的前驱与后继。这里有个容易记反的点ltag 为 0 表示 lchild 指向左孩子ltag 为 1 表示 lchild 指向前驱。复习时把“tag 为 0 看孩子tag 为 1 看线索”写在笔记本最显眼的位置。哈夫曼树部分要会构造并计算 WPL还会判别“哈夫曼树不存在度为 1 的结点”这个性质。3.4 图和数组存储结构、连通性与最短路径图和数组是数据结构里逻辑最重的一章也对应考研数据结构 408 的图和数组板块。图部分掌握三个层次存储结构要会画出邻接矩阵和邻接表能够从邻接矩阵判断边的存在性遍历算法要能写出 DFS 和 BFS 的序列还要知道连通图的遍历为什么只需要调用一次就可以访问所有顶点应用算法要掌握 Prim、Kruskal、Dijkstra、Floyd 的适用条件和手动推演。Dijkstra 不能求带负权边的最短路径Floyd 可以这是选择题的常见考点。数组部分考的是地址计算和稀疏矩阵存储。二维数组按行优先存储时元素 a[i][j] 的地址等于 base (i * 列数 j) * 每个元素大小下标是否从 0 开始要看题目说明。稀疏矩阵的三元组表压缩存储是容易出填空题的地方要能写出三元组的顺序行号、列号、值。这一章的复习目标不是把每个算法背下来而是能用手推一次完整流程。3.5 查找与排序算法一张表记住复杂度与稳定性查找与排序是最容易拿分也最容易失分的章节因为它的考点非常明确但需要记忆量大。查找部分掌握顺序查找、折半查找、二叉排序树、哈希查找四种重点能画出折半查找的判定树并计算等概率条件下的平均查找长度。哈希部分要会按题目给定冲突处理方法线性探测法或链地址法构造哈希表。删除哈希表中的元素时线性探测法不能直接置空否则会切断后面的探测路径这是个经典坑。排序部分是期末复习的重头戏也是数据结构排序算法考察的集中区域。下面这张表是按 C 语言版主流教材整理的建议自己再动手写一遍而不是直接背。排序算法平均时间最好时间最坏时间空间稳定性直接插入O(n²)O(n)O(n²)O(1)稳定希尔O(n^1.3) 左右O(n)O(n²)O(1)不稳定冒泡O(n²)O(n)O(n²)O(1)稳定快速O(n log n)O(n log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定归并O(n log n)O(n log n)O(n log n)O(n)稳定稳定性判断用三条结论能覆盖九成题目简单选择排序跨距离交换容易破坏相对顺序快速排序的 pivot 与远端元素交换也不稳定归并排序的合并过程只在左半边小于等于右半边时才取左元素所以能保持稳定。冒泡和直接插入排序在相邻交换的条件下都是稳定的。这个结论在选择题和判断题里至少值 2 分。4. 算法设计题复现练习把 C 代码写到可以上考场4.1 单链表反转头插法与三指针法的取舍链表反转是最常出现的算法设计题没有之一。它考察指针操作的熟练度还考察边界处理能力。我一般建议先写三指针法因为它不需要额外创建头结点代码直观。// 单链表反转三指针迭代法 struct ListNode *reverseList(struct ListNode *head) { struct ListNode *prev NULL; // 前驱指针初始为 NULL struct ListNode *curr head; // 当前指针 while (curr ! NULL) { struct ListNode *next curr-next; // 先存后继防止断链 curr-next prev; // 反转当前结点的 next prev curr; // 前驱后移 curr next; // 当前后移 } return prev; // prev 指向反转后的新头结点 }这个代码的关键点有三个一是进入循环前就要把后继结点存到 next否则把当前结点的 next 改成 prev 后就找不到原链表剩余部分了二是循环结束后 prev 指向原链表的尾结点而它就是反转后的新头结点三是空链表和单结点链表不需要特判因为空链表不进循环直接返回 NULL单结点链表进入一次循环后返回原结点边界被统一处理。如果你选择头插法实现需要新建一个空头结点每遍历一个结点就头插到新链表代码更简洁但多了分配空间的代价考场上用三指针法更稳妥。写完之后习惯性地在草稿纸上画出 1→2→3→NULL 的变化过程确认 prev、curr、next 三个指针每一步的位置这一遍推演能避免大部分笔误。4.2 二叉树层序遍历队列版本的最小实现层序遍历考察的是队列应用与二叉树结构理解的结合出题频率同样很高。要求输出每一层的结点值本质上就是广度优先遍历二叉树。// 二叉树层序遍历借助队列实现 void levelOrder(struct TreeNode *root) { if (root NULL) return; struct TreeNode *queue[1000]; // 用数组模拟队列容量可按题设调整 int front 0, rear 0; queue[rear] root; // 根结点入队 while (front rear) { // 队列不为空时循环 struct TreeNode *node queue[front]; // 出队 printf(%d , node-val); if (node-left ! NULL) queue[rear] node-left; if (node-right ! NULL) queue[rear] node-right; } }这里的队列用数组模拟rear 负责在队尾写入front 在队首读取二者相等表示队空。出队不需要真正把元素置空也没必要重置 node 指针因为 front 向后移动后该位置就不会再被访问。数组容量在考试环境中没有动态扩容的需求按题设给一个足够大的常数即可例如二叉树结点数不超过 1000 时就写 1000。一定要记得入队前判空把 NULL 入队虽然不报错但输出时会访问空指针。这道题如果要求按层输出且每层换行只需在每次循环前记录当前队列长度控制内层循环次数这是对队列先进先出特性的进一步运用。4.3 图的深度优先遍历邻接表与邻接矩阵两种写法图遍历题要求手写完整代码时正确率普遍偏低原因是很多人对图的存储结构定义不熟。期末卷通常会给现成的结构体定义你只需要写遍历函数。下面是邻接表版本的最简实现。// 邻接表图的深度优先遍历递归写法 #define MAXV 100 // 最大顶点数 int visited[MAXV]; // 访问标记数组 void DFS(AGraph *G, int v) { visited[v] 1; // 标记当前顶点已访问 printf(%d , v); // 访问顶点 ArcNode *p G-adjlist[v].firstarc; // 取出第一条边 while (p ! NULL) { if (visited[p-adjvex] 0) { DFS(G, p-adjvex); // 未访问则递归深入 } p p-nextarc; // 移动到下一条边 } }这版代码最需要注意的细节是递归的时机只有在邻接点未访问时才递归进入否则会死循环。visited 数组必须定义成全局或静态数组因为递归调用会反复用到。如果你用邻接矩阵实现区别在于找邻接点时不再使用 p 指针而是用一个 for 循环遍历整行查找 adj[i][j] 是否为 1。遍历完整个连通分量后主函数里要再遍历一次顶点数组对所有 visited 为 0 的顶点再调用 DFS才能处理非连通图。这个“非连通图需要多次调用遍历函数”的细节是应用题和算法题都爱挖的坑。4.4 快排 partition 与折半查找出题频率最高的两个模板快速排序和折半查找是查找排序部分最可能直接出成算法设计题的模板。折半查找代码短边界条件多几乎每年都有学生因为写错 while 的终止条件丢分。// 折半查找在有序数组中查找 key返回下标找不到返回 -1 int binarySearch(int arr[], int n, int key) { int low 0, high n - 1; while (low high) { // 注意是 不是 int mid (low high) / 2; if (arr[mid] key) return mid; else if (arr[mid] key) low mid 1; // 值太大往右半区找 else high mid - 1; // 值太小往左半区找 } return -1; }这个模板里最容易写错的是 while 条件写成 low high 会导致单元素数组或目标在最右端时找不到结果因为 lowhigh 时还需要最后一次比较。mid 的计算用 (low high) / 2 在考试环境中没问题大规模数据下用 low (high - low) / 2 防止溢出但期末笔试不会要求到这个层面如果你写出来了反而会被认为是基本功扎实的正常写法。快排的 partition 只需要记住“从右往左找小从左往右找大挖坑填数”的口诀边界处理的两处判断均取等号i j 作为外层终止条件。写完模板后要能说出它的平均时间复杂度和最坏情况发生条件这两问经常出现在同一道题里。5. 避坑指南数据结构考试最容易翻车的五个细节5.1 指针传参不生效链表的修改为什么带不出来现象在函数里对链表头结点做修改返回后主程序里链表没有变化。原因C 语言函数的形参是值传递。当你把 head 指针传给函数时函数内部的 head 是实参的一个副本修改这个副本的指向不会影响外部的指针变量。如果你在函数里写了 head head-next 这种代码外部的 head 纹丝不动。解决需要修改头指针本身时传二级指针 struct ListNode **pHead如果代码逻辑只修改链表结点内部的 next 域而不改变头指针的指向用一级指针就够了。判断标准只有一个——你的函数有没有让头指针变量本身指向一个新的结点。这个原则在考场上写代码前先问自己一遍能避免时间浪费。5.2 递归没有出口栈溢出不一定在考试时暴露现象手写二叉树求高度或 DFS 代码时没有判空直接进入递归逻辑推导看起来没问题但一旦运行就堆栈溢出。原因递归函数的出口条件不完整比如求二叉树高度时只写了 return 0 作为空树条件的出口但递归调用时传入的 root-left 为 NULL 后又进入了函数却没有对应的空指针判断。另一个场景是递归内修改了递归参数但参数没有收敛趋势比如二分查找时 mid 计算错误导致区间不再缩小。解决写任何递归函数前先在草稿纸上写下出口条件。求树高时先写 if (root NULL) return 0DFS 时先写 if (visited[v]) return。把出口写在前三行是一个非常值得养成的习惯它不需要你花额外时间只需要你有意识。5.3 排序稳定性记反快排和选择排序被写成“稳定”现象判断题问“简单选择排序是稳定的”你打了对号理由是它每次选最小的放前面不会交换相等的元素。原因简单选择排序在交换时如果当前最小元素与某个相等元素互换位置相等元素的相对顺序确实可能被改变。例如数组 [4a, 2, 4b]第一轮选出 2 与 4a 交换结果是 [2, 4b, 4a]4a 和 4b 的相对位置反了。快速排序同理pivot 的交换会跨越中间区域无法保证相对顺序。解决不要试图理解每个排序算法的稳定性证明直接采用“口诀 反例”的方式记忆。稳定的是直接插入、冒泡、归并、基数不稳定的是希尔、选择、快排、堆。考试时如果担心记反就在草稿纸上画上面那个 4a、4b 的小例子30 秒能验证一部分。但注意直观反例在考试中不能写进答卷它只是用来唤起记忆的保险丝。5.4 堆排序建堆边界从 n/2-1 开始下沉而不是从 n-1现象手写堆排序的向下调整函数时建堆循环写成了 for (int i n - 1; i 0; i--)结果排序结果不对。原因完全二叉树的最后一个非叶子结点下标是 n/2 - 1数组从 0 开始下标大于它的结点都是叶子叶子结点没有孩子自然不需要向下调整。从尾部开始对每个非叶子结点调整才是正确的建堆过程。解决记住这个常量计算建堆循环写成 for (int i n / 2 - 1; i 0; i--)。如果考试给出的是从 1 开始编号的堆数组则最后一个非叶子结点是 n/2调整循环从 n/2 开始。这个“数组下标从 0 还是从 1 开始”的差异是堆排序题的经典陷阱答题前通常需要在代码注释里先写清数组下标约定。5.5 哈希表删除元素线性探测不能直接置空现象用线性探测法处理冲突的哈希表删除一个元素后再查找某个本应存在的 key 时返回“不存在”。原因线性探测在冲突时会连续探测后续位置。如果某个槽位被删除后直接置空后续经过该位置才能到达的探测链就被切断了查找会提前终止。哈希表删除问题在数据结构实验报告中经常被忽略因为教材很少强调这一点。解决删除线性探测哈希表中的元素时用“标记删除”代替“物理删除”即在该位置放入一个特殊标记如 DELETED查找时遇到 DELETED 继续向后探测插入时遇到 DELETED 可以复用该位置。理解这个机制后相关的判断题和设计题就能拿稳不必背代码因为你已经知道为什么不能直接置空。6. 考前一周自测方法把做卷子变成一次真考训练期末复习最后一周我建议停止逐章翻书转而做三遍真题式自测。第一遍限时 120 分钟完整做一套旧卷包括手写算法题完全不看笔记。这里的关键是“限时”和“手写”缺一个都会让你对自己的掌握程度产生幻觉。第二遍把错题按知识点归类找到对应的教材章节重读并重做一次错题。第三遍只花半天扫概念清单重点看选择题和判断题里反复出现的边界定义。时间分配可以按这个比例来参考选择题和判断题 25 分钟应用题 45 分钟算法设计题 50 分钟留 10 分钟检查。算法设计题务必在卷面上先写“思路”再贴代码用三步策略第一行写算法思想第二行起写核心代码最后画关键边界注释。判卷老师看到思路清晰但代码有小错通常会给大部分过程分如果直接写残缺代码连思路都无从判断得分会低一个档次。我自己每次考前都会把一个错误清单默写在一张 A4 纸上折半查找的 while (low high)、链表反转的 next 暂存、哈希表 delete 不置空、堆排序建堆从 n/2-1 开始、递归先写出口。这个习惯帮我在期末卷和考研卷里至少挽回过好几道题的失误你也可以按自己的错题来定制这样一张纸。最后希望这篇拆解能帮到你祝复习顺利。本文还有配套的精品资源点击获取