简介湖北大学《数据结构》2022—2023学年第一学期期末试卷A卷面向计算机相关专业本科生适合期末复习、考研自测及教学参考。试卷为闭卷考试覆盖判断分析题、简答题与应用分析题重点涉及带权有向图与关键路径、邻接表存储、出栈序列、平均查找长度、二叉树遍历、递归函数、链栈选择、矩阵压缩、归并排序、最小生成树、二叉排序树、平衡二叉树及哈希表等核心章节既有概念辨析也有算法设计与计算推导能系统检验学生对数据结构知识点的掌握程度。资源共1个PDF文件压缩包大小约252KB内容为完整试题纸共7页已有375人浏览学习。对准备湖北大学数据结构考试或希望强化图、树、查找与排序基础的读者来说是一份高性价比的真题练习材料。1. 某高校数据结构期末试卷这门课期末到底考什么某高校的数据结构期末试卷考的不是背诵是手写。整张卷子七成以上的分落在“能不能在白纸上把链表倒置、二叉树遍历、排序过程完整写出来”这和考研408那种以选择题为主、机读卡打天下的风格完全不同。它的题型结构更接近经典工科做法基础概念占三成应用题占三成手写算法题占三成剩下的零碎分数分布在判断题和读程序题里。准备这门考试最忌讳的是打开教材从头翻到尾因为树、图、排序、查找四个大章内容极多平均用力等于没复习。常见做法是先摸清近几年试卷的题型分布与高频考点再按分值权重反向决定复习顺序。这篇就把某高校这套试卷的拆解方法、考点优先级、手写代码的应试策略和容易翻车的细节一次讲清楚适合考前一个月开始最晚也要留出两周来执行。如果你手头还没有拿到完整答案问题也不大完全可以按题型清单自己整理历年题目分类归档后按下面章节给出的顺序逐个击破。这是一条被验证过多次的复习路径照着做比漫无目的刷题稳得多。2. 按期末真题拆题型选择、判断与应用题的分值逻辑拿到一份某高校最近几年的数据结构期末试卷先不要急着做题而是把卷子从头到尾翻一遍按题型统计分值。这一步决定了你后面每一章投入多少时间也直接决定了复习的天平该往哪边倾斜。2.1 选择题考点覆盖广但深度浅目标就是全拿分选择题通常15到20道每题1到2分占比在15%到25%之间。题目覆盖绪论、线性表、栈和队列、串、树、图、查找、排序全部章节但每道题都考得很浅基本是“某个概念记没记住”的程度。高频考点非常集中时间复杂度大小比较、栈的后进先出特性、循环队列判空和判满条件、二叉树叶子节点数与度为2节点数的关系、图的最小生成树边数、拓扑序列判断、哈希表平均查找长度计算。真正容易错的是那些“看起来都对”的选项比如循环队列判满教材里给了牺牲一个存储单元、设计数器、设标志位三种写法试卷通常默认第一种读题不仔细就会按第二种思路选错。判断题则更直白一点主要是概念性辨析比如“二叉树就是度不超过2的树”这种话术。复习时只需要把每一章的概念定义列表过一遍判断题基本送分不值得单独投入时间。2.2 应用题树和图是绝对主角写过程比写答案重要应用题一般4到6道大题合起来分值30到40分是全卷拿分的核心区。题型非常固定翻几套卷子就能归纳出题库给一个关键字序列构造二叉排序树或平衡二叉树并写出调整过程给图的邻接矩阵用Prim或Kruskal求最小生成树写出边的加入顺序给AOE网求关键路径、关键活动以及最早最迟发生时间给一组关键字和散列表长度用线性探测或链地址法写出插入过程与查找成功时的平均查找长度给一组关键字写出快速排序每一趟结束后的序列状态或归并排序每两两合并的过程。这类题的阅卷逻辑是“过程分”而不是“结果分”答案全对但中间过程写得像天书照样拿不到满分。比如构建二叉排序树必须画出每次插入后树的形态求最短路径必须写出每一轮dist数组或path数组的更新过程。平时练习就要养成把每一步都落在纸上的习惯而不是只在草稿纸上算一个最终结果。2.3 算法设计题两到三题考的是手写而不是运行算法设计题一般2到3道每题8到15分合起来占20%到30%是整张卷子拉开差距的板块也是“背了模板不一定得分、不背模板一定没分”的板块。高频题目集中在三块链表的原地逆置或有序链表合并、二叉树的递归与非递归遍历、基于快排partition的快速选择或第k小元素。评分细则大致是函数签名正确给2分核心逻辑正确给一半分边界条件空链表、空树、递归终止、循环结束占3到4分最后要求写时间复杂度和空间复杂度分析占1到2分。这意味着只写一段“主循环”是不及格的因为边界条件和复杂度分析在评分表里各占一格。平时练题时就要按这个评分结构反过来约束自己先写签名再写空判断再写主逻辑最后补一句复杂度四个动作缺一不可。下表是这套试卷最常见的题型结构每年会有小幅调整但分值比例基本稳定可以放心按这个来排复习优先级题型题量分值占比高频内容单选题15~20道15%~25%复杂度、栈队列、二叉树性质、哈希判断题8~10道8%~10%概念辨析、存储结构、算法特性应用题4~6道30%~40%树与图的构造过程、排序过程算法设计题2~3道20%~30%链表、二叉树、快排相关手写3. 必考考点复习优先级哪些知识点不复习就白丢分数据结构的章节多、术语多但某高校试卷的高频考点集中在少数几个知识块里。复习时按下面的优先级排序先吃掉最常考的再考虑边角内容。时间不够时宁可放弃串的KMP和B树的删除细节也不能放弃树与图的过程题。3.1 树和二叉树遍历序列互推与重建是最高频考点二叉树几乎是每年必考且分值最重的一块。选择题常考的性质有两个叶子节点数等于度为2节点数加1n个节点的完全二叉树深度为floor(log2 n)1。这两个性质要能闭着眼写出来因为后面所有树相关的计算题都要用到。应用题的明珠是“由两种遍历序列重建二叉树”给前序中序推后序给中序后序推前序给层序中序重建二叉树。这类题没有难度只有熟练度练法就是找十几道不同序列的题按同样的递归分割思路反复画图一直画到不用动脑就能推出递归区间。算法题则是二叉树的高度、叶子计数、左右子树交换三种递归模板代码量都在十行以内属于压箱底的保分题。3.2 图的算法过程最短路径、最小生成树、拓扑排序图的应用题是全卷最“套路化”的板块只要格式对分就稳了。Dijkstra要求写出每轮dist数组的变化Prim要求写出每次选中的边和当前生成树顶点集Kruskal要求按边权排序后逐条选边并说明是否成环。这三类题建议每天各练一题连续练一周把固定表格格式背下来。还有一个几乎必考的隐藏点拓扑排序。题目常给一个有向图的邻接表或邻接矩阵要求写出拓扑序列并判断图中是否存在环。注意拓扑排序的结果可能不唯一阅卷时按“任意合法序列”给分只要满足每条边的起点都在终点前面就算对不需要和标准答案完全一致。3.3 排序算法快速排序和堆排序是手写与过程的双重重点排序板块考两种东西排序过程和手写代码。快速排序要求写出每一趟结束后的序列状态注意不是每一趟的“中间状态”堆排序要求先建初始大顶堆再写出每次堆顶与末尾交换后的调整过程。这两类题每年至少出一题建议把“一趟”的定义搞清楚一趟快排是指一个partition结束而不是一次元素交换。手写代码则集中在快排的partition函数和堆的siftDown调整函数。前者本质上是一个双指针向中间逼近的填坑过程后者是一个父节点与两个孩子比较后下沉的过程。这两个函数加起来不过三十行吃透逻辑后所有衍生题都能解开。3.4 链表的操作作为算法设计题的“安全题”链表从头到尾只围绕一个核心动作指针重连。期末考试不会考特别复杂的链表题高频就两个单链表原地逆置、两个有序链表合并成一个有序链表。这类题代码短、边界少、思路直观是全卷最稳定的拿分点也是复习时最先应该上手的模块。刷链表题时注意一个细节某高校试卷里的大多数链表题默认“带头节点”或者明确写“无头节点”这两种情况下代码写法不一样尤其是逆置后的头节点返回逻辑。读题时先花十秒钟确认头节点形式否则按错思路写完整段代码就太亏了。4. 手写代码题从读懂题意到默写模板的实战路径手写代码是某高校试卷最独特的考察方式。这里说的“手写”不是让填一个空或补一行循环而是给你一道完整的题目从函数签名到函数体全部自己写。平时用惯了IDE自动补全的人第一次在答题纸上手写代码会非常不适。这一章讲清楚怎么练、怎么写、写不到满分时怎么捡分。4.1 读题先看限制条件再决定用什么思路很多同学拿到算法题就开始默写背过的模板结果题目里的限制条件没看写了半页纸全是无效代码。比如同样一道链表逆置题目可能写“在O(1)额外空间内完成”也可能写“不新建头节点”还可能写“用递归方式实现”。这三种限制对应三种不同写法。我的答题习惯是先圈出题面里的三个要素——数据结构形态带头节点/不带头节点、数组/链表、算法要求递归/非递归、空间复杂度限制、输出形式返回值/参数引用。然后才在草稿纸上把函数签名写出来。签名本身就是2分很多人因为少写一个返回值类型就丢分这点非常亏。另一个常见问题是盲目使用C语法。某高校的期末算法题默认用C语言描述数据结构链表节点定义、栈和队列的声明都要用结构体加typedef的写法。用vector、map这类STL容器答题即使逻辑完全正确也可能因为不符合评分预期而拿不到分这一点后面避坑章还会再展开。4.2 三个高频手写模板链表逆置、二叉树非递归遍历、快排partition下面三个模板是我认为最高频、性价比最高的手写代码也是某高校算法设计题里最常出现的底子。先看第一个单链表原地逆置。/* 单链表原地逆置不新建头节点只改指针方向 */ ListNode* reverseList(ListNode* head) { ListNode *prev NULL, *cur head; while (cur ! NULL) { ListNode *next cur-next; // 先存后继防止断链 cur-next prev; // 反转当前节点的指针 prev cur; // prev 前移一步 cur next; // cur 前移一步 } return prev; // 原尾节点成为新头 }这段代码的逻辑是三个指针prev、cur、next分别指向前驱节点、当前节点、后继节点每轮循环做三步保存后继、反转当前指针、两个游标前移。循环终止条件是cur为空此时prev恰好指向原链表的尾节点也就是新链表的头节点。参数与边界说明head是原链表头节点指针返回类型为ListNode*调用时需要用新变量接收返回值因为原head变量在逆置后仍然指向旧头此时它已经是尾节点直接使用会出现逻辑错误。空链表和单节点链表的处理由代码天然覆盖前者循环不执行直接返回NULL后者返回自身。这道题如果题目要求“带头节点”只需要把传入的head替换为head-next并在返回前补回头节点属于该模板的唯一变体。第二个模板二叉树的非递归中序遍历。某高校爱考这个是因为它区分了“会不会背递归代码”和“真懂栈这个数据结构”。/* 非递归中序遍历用栈模拟系统递归栈 */ void inorderTraversal(BiTree root) { if (root NULL) return; // 空树直接返回 Stack S; initStack(S); // 初始化顺序栈 BiTree p root; while (p ! NULL || !isEmpty(S)) { while (p ! NULL) { push(S, p); // 一路向左把根节点入栈 p p-lchild; } if (!isEmpty(S)) { p pop(S); // 出栈的节点就是当前该访问的节点 visit(p); p p-rchild; // 处理左子树完毕后转到右子树 } } }逻辑说明这个模板的核心是“先把左子树全部入栈弹出一个处理一个然后转向右子树”。visit(p)是访问节点的动作考试时通常写成printf节点数据不算复杂。每个节点会经历入栈、出栈、访问、转向右子树四步。参数与边界说明root是二叉树根节点指针Stack是需要自己实现的顺序栈initStack、push、pop、isEmpty四个函数都要提前准备好模板。最容易丢分的位置有两个一是外层循环条件漏写p ! NULL导致右子树为空时循环提前退出二是pop之后忘记把指针移动到右子树造成同一棵左子树被重复访问。这两个错误在阅卷时恰好是评分细则里“循环结束条件”和“逻辑完整性”两格各扣2到3分。第三个模板基于快排partition的快速选择算法这是算法设计题里的深度题。/* partition以第一个元素为基准挖坑填数 */ int partition(int a[], int low, int high) { int pivot a[low]; // 基准元素low位置成为初始坑 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; // 从右向左找到比基准小的填入左边坑 while (low high a[low] pivot) low; a[high] a[low]; // 从左向右找到比基准大的填入右边坑 } a[low] pivot; // 基准归位 return low; // 返回基准最终位置 } /* 利用partition查找第k小元素k从1开始计数 */ int quickSelect(int a[], int low, int high, int k) { int pos partition(a, low, high); if (pos k - 1) return a[pos]; // 基准恰好落在第k个位置 else if (pos k - 1) return quickSelect(a, low, pos - 1, k); else return quickSelect(a, pos 1, high, k); // 只递归一侧 }逻辑说明partition内部是挖坑填数过程先用基准元素挖坑从右往左找比基准小的数填进来再从左往右找比基准大的数填到右边空位最后low和high相遇时把基准放回去。返回值是基准元素的最终下标。quickSelect利用这个下标与k比较只递归地搜索第k小元素所在的半边。参数与边界说明a为待查找数组low和high为闭区间下标k从1开始计数。函数返回第k小的值本身。与完整快排相比这里少递归了一半区间所以平均时间复杂度是O(n)。边界条件在使用时必须保证lowhigh且数组长度不小于k否则会出现越界。我在练习时会在函数第一行加一个if (low high) return -1的空判断虽然阅卷不一定扣但能防止自己的思维漏洞。这三个模板建议每天默写一遍连续练五天。默写不是背字母序列而是边写边在心里过逻辑写完之后对着上面的解释检查每一个循环条件和返回值。4.3 不会写时怎么捡分思路、签名和递归出口总有两三道题是你没练过的。遇到完全不会的算法题时最差的策略是空着不写其次是把背过但和题目无关的模板硬抄上去。这两件事在阅卷时都是零分处理。正确做法是至少争取4到5分的步骤分。第一步把函数签名写对包括返回值类型、函数名、参数列表这本身就值1到2分。第二步写出你打算采用的数据结构定义比如题目表面是在处理数组但你知道转成链表更简单就把链表结构体定义写出来这也是1分。第三步只写递归出口或边界判断比如空指针return、n1时直接返回这是评分细则里独立的一格。第四步用一两句话写下你的算法思路比如“先把数组分成三个区间再递归处理中间区间”即使代码没写出来阅卷者也经常会按“思路正确”给一半分。这套“捡分策略”不是玄学而是因为在评分表里函数签名、边界条件、算法描述本来就是独立的给分项。写在答题纸上就有机会拿到空着一定没有。5. 期末备考避坑五个最容易翻车的答题习惯每年总有一些学生复习得很努力题库刷了好几遍上了考场却因为几个坏习惯大面积丢分。下面五条是我观察到的翻车重灾区全部按“现象→原因→解决”来讲。5.1 用C STL代替手写整道算法题零分现象是算法设计题直接写“vector v; reverse(v.begin(), v.end());”逻辑上完全正确但最终这道题得了0分。原因在于某高校这套试卷的评分标准是在“数据结构课程要求学生掌握手写实现”这一前提下制定的代码必须体现链表、栈、队列的底层操作STL封装的容器不在给分范围内。解决方法是平时练习时就禁用STL容器。链表、顺序栈、循环队列全部用结构体和数组手工实现考试时也坚持用C风格的代码答题。如果你实在习惯了C可以保留cin和printf这类输入输出但容器和算法库必须全部手写。5.2 只写主循环边界条件全丢现象是快排partition写得完整但函数第一行没有判断数组为空或区间不合法非递归遍历时栈初始化和空树判断缺失。原因是在IDE里调试时编译器不会提示这些逻辑问题代码能跑出正确结果就不自觉忽略了。但阅卷评分表里边界条件是一整块分值通常占3到4分。解决方法是把每个模板固定两行开头一行是“if (入参为NULL或区间非法) return 空值”另一行是初始化数据结构。这两行写成条件反射即使题目没强调边界也要写上去保证评分表那一格不空。5.3 排序应用题只写最终序列过程分全丢现象是堆排序的题目要求写出“建初始堆及每趟排序后的序列”很多同学直接写了最终有序序列得一半分都没有。原因是对“过程分”理解不足觉得结果对了就万事大吉。实际上阅卷是按趟数给分堆排序通常要写出每一趟堆顶与末尾交换后的调整结果每一趟是独立的给分点。解决方法是平时练习任何排序过程题都用“分趟书写”的格式第一趟写初始状态第二趟写第一次交换后的状态每写一趟都标上行号。虽然费时间但每一行都能换来分值这是整套试卷里性价比最高的答题动作。5.4 忽略“请写出时间复杂度分析”这半行字现象是算法题写完了代码逻辑完整但最后一句“请分析其时间复杂度和空间复杂度”完全没答被扣1到2分。原因不是不会而是答完代码后有一种“题目做完了”的放松感惯性忽略题面最后半行字。解决方法是把复杂度分析变成算法题的固定收尾动作。递归算法就写递归式比如T(n)T(n/2)O(n)最后给出O(n)或O(log n)循环算法就数循环层数写“最内层循环执行n次总复杂度O(n^2)”空间就看有没有开辅助数组或栈。熟练之后这半行字只需要30秒白拿的分不要丢。5.5 背模板不理解过程换一个问法就翻车现象是背了“由前序和中序重建二叉树”的代码题目换成“由中序和后序重建二叉树”就不知道递归参数从哪传了。原因是没有自己画过递归过程的推进图只是记住了前序版本的代码形态换个序列类型就失去参照。解决方法是每背一个代码模板都拿一个5个节点的小例子把递归过程完整画出标出每轮递归的区间、分割点、左右子树范围。这个画图练习只需要十分钟但它把“背代码”变成了“理解逻辑”之后不管题目怎么换都能按同样的区间推导写出新代码。6. 考前一周的复习节奏与试卷使用技巧最后一周不需要再学新知识也不需要刷陌生题。这个时候的复习目标是稳住手感和查漏补缺时间分配可以完全按题型分值比例来。第1天到第2天把过去三年的试卷重新做一遍。做的时候严格限时150分钟用答题纸完整书写过程特别是应用题和算法题每个中间状态都要落在纸上。做完后不要急着对标准答案而是先对照自己当时写的过程找漏洞再翻答案。第3天到第4天进入“默写模板日”。每天上午默写链表逆置、二叉树中序非递归遍历、快排partition三个核心模板下午默写Prim和Kruskal的书写表格格式。默写的标准是从空白页开始到最后一行代码结束中间不卡壳、不涂改。第5天专门处理错题清单。把做题过程中反复错的题型列出来比如“平衡二叉树调整总是少写一次旋转”然后只针对这类题型集中练习不碰其他内容。第6天做一套完整模拟卷仍然限时150分钟。这次要特别注意时间分配应用题每道控制在10分钟以内超过就跳过宁可最后回来补不能卡在一道题上。第7天不用再做新题。只做两件事把默写过的模板再滚一遍把错题清单从头到尾看一遍。晚上早点休息保证考试时脑子清醒。往年试卷的正确用法不是背答案而是“先自测、后对照、再复盘”。直接背标准答案会让你误以为自己会了实际上考场换一个序列、换一个图的拓扑结构就会露馅。只有限时手写过才会暴露出真实水平。我当年考这门课最吃亏的一件事就是一直用IDE写代码从没尝试过在纸上完整写一遍。上了考场才发现手写代码时对缩进、括号匹配和变量命名的控制感和编译器面前完全不是一回事。从那以后我给所有备考的人一个建议从复习第一天起就准备一沓白纸所有算法题都在纸上写写完再敲进电脑验证。这个习惯保持了几年后来帮学生备考时凡是用这个办法练过的人算法设计题的平均得分都明显高于直接刷题库的人。希望这个习惯也能帮到你。本文还有配套的精品资源点击获取