简介湖北大学数据结构期末试卷2022—2023学年度第一学期A卷是一份面向“信息安全”专业本科生的闭卷试题适合备考期末或系统复习数据结构核心章节。卷面设置判断分析、简答与应用分析三类题型其中判断分析题要求说明理由覆盖带权有向图与关键路径、顺序查找ASL、栈的合法出栈序列、存储结构分类、二叉树遍历与还原等易混淆考点简答题涉及邻接表求边数与入度、递归函数fun(x,n)的功能与调用次数、链栈存储结构选择、稀疏矩阵压缩等应用分析题则要求写出二路归并排序每趟结果、Prim和Kruskal构造最小生成树过程、二叉排序树构造与ASL计算、平衡二叉树插入调整类型、哈希表线性探查法构造等重视概念理解与计算实现能力。资源为单个PDF文件大小252KB便于打印练习已有375人学习可配合教材用于考前自测、错题复盘与查漏补缺。1. 数据结构期末试卷一份A卷背后的查漏补缺路线图数据结构期末试卷这几年越来越不满足于“背概念”而是把图、树、查找、排序和链表操作揉在一起考。这份2022—2023学年度第一学期的A卷就是典型判断、简答、应用分析、程序设计四大部分覆盖带权有向图、邻接表、二叉树遍历、平衡二叉树、哈希表、归并排序和链表删除题型梯度拉得很开。对准备期末考试的人来说它最大的价值不是“押题”而是帮你在考前快速定位自己哪一章是黑匣子——图算法是否只会套模板递归有没有真正理解调用过程哈希冲突处理是不是只记得名字。这篇文章会按题型把每题的知识点、易错点和答题规范拆开讲连公式推导和代码边界条件一起给你。2. 判断题速刷关键路径、顺序查找与出栈序列的判定逻辑2.1 带权有向图与关键路径为什么“缩短活动时间不一定能缩短工期”第一道判断题考的是带权有向图在工程进度描述中的应用。题干大意是用带权有向图描述工程进度缩短关键路径上某个活动的时间一定能缩短整个工程的工期。这个说法在大多数第一印象里好像合理但实际上不成立。关键路径是工程网络中最长的那条路径它决定项目最短工期。问题是关键路径可能不止一条。假设两条关键路径从同一个起点出发、在同一个终点汇合你只缩短了其中一条上的一个活动另一条关键路径仍然保持原来的长度那么整个工程的工期被另一条路径锁死一点都不会变。还有一种情况你缩短的那条路径变得比原来短它不再是关键路径这时总工期取决于剩下路径中最长的那条可能不变也可能只缩短一点点。这题的答题套路是先下结论“不正确”再补一个反例一个活动网络同时存在两条关键路径缩短其中一条上的活动工期不变。阅卷时判断分的分值不大但分析理由写得清晰后面应用大题里遇到关键路径计算也会顺手很多。判断这种“一定”“必然”字眼的描述优先怀疑它。数据结构里几乎没有多少结论能冠上“一定”两个字。2.2 顺序查找的ASL、存储结构分类与二叉树遍历推导第二题“顺序查找算法查找不成功的平均查找长度为(n1)/2”。这是经典的错误表述。顺序查找成功时第i个元素需要比较i次成功ASL是(n1)/2。查找不成功时你要从头到尾把所有n个元素都比一遍才知道目标不存在ASL是n。有些教材会算成n1那是把最后的空指针判断也算作一次比较两种口径差1。判断这题写“不正确失败ASL是n或n1看比较口径成功才是(n1)/2”就把两个公式都写全老师挑不出毛病。第三题给出进栈序列1到6问序列2,3,5,1,6,4能否作为出栈序列。这类题唯一可靠的做法是拿栈模拟一遍。1进、2进、2出3进、3出4进、5进、5出。此刻栈中从栈底到栈顶是1、4。想输出1必须先输出4但目标序列中1在4之前直接矛盾。所以这题答案是“不可能”。栈的考点其实只有一个核心后进先出。进栈出栈可以穿插不等于出栈顺序可以任意排列。会画栈状态图这种题永远错不了。第四题判断“存储结构包括顺序、链式、哈希三种”这题考的是概念精确度。国内主流数据结构教材对存储结构的分类是四种顺序存储、链式存储、索引存储和散列哈希存储。题干少说了一种索引存储所以表述不完整判断为错。考试里容易丢分的是解释部分要说清“哈希存储只是散列存储的一种实现方式它和顺序存储、链式存储不在同一个分类维度上”这个细节写上去就是加分点。第五题给了一棵二叉树的中序序列ABCDE和先序序列CABED要判断后序序列是否为BADCE。这是“由两种遍历唯一确定二叉树”的标准题。先从先序知道根是C再到中序里定位中序C左边是AB是左子树右边是DE是右子树。左子树先序为AB、中序为AB说明A是根B是A的右孩子。右子树先序为ED、中序为DE说明E是根D是E的左孩子。画出树形后后序遍历就是B A D E C与题干一致判断为正确。这种推导过程在考卷上要写出来结果对只是得一半分推导过程才是拿分重点。3. 简答题全拆解邻接表、递归调用、链栈选型与顺序表删除3.1 邻接表下求边数、判边和入度的三种思路第一道简答给了一个有向图G顶点数为n存储结构是邻接表问三件事求边数的思路、判断两点是否有边、计算顶点i的入度。这三个问题本质是在考“邻接表存的是什么”。求边数最简单遍历每个顶点的邻接表把每个顶点的出边数量累加得到arcNum。对于有向图每条边只被起点记录一次所以累加结果就是边数不需要除以2。如果是无向图每条边在两个顶点的邻接表里各出现一次需要把累加结果除以2。我这里重点提醒题目说“有向图”答题时先说明这个前提再给出遍历累加的思路顺序不能乱。判断顶点i和j是否有边相连就直接沿着第i个顶点的邻接链表找j。链表中每个结点存储的是弧头顶点编号假如p-adjvex j就说明存在从i指向j的边。时间复杂度是O(出度(i))最坏O(n)。这里容易踩的坑是有人会去遍历j的邻接表找i那样得到的是“是否存在从j到i的边”方向反了。有向图必须强调弧的方向。求顶点i的入度才是邻接表真正的痛点。邻接表非常自然地支持出度但入度需要扫描所有顶点的邻接表统计目标顶点i出现在多少条链表中每出现一次就是一个入度来源。如果要频繁计算入度考场外的工程做法是给图加一个逆邻接表或者十字链表。你答“遍历全部顶点链表统计出现次数”能拿全分再补一句“可用逆邻接表优化”就是白送的亮点。3.2 递归函数fun(x,n)功能、调用次数与边界缺陷第二道简答给了递归函数double fun(double x, int n) { if (n 1) return x; return x * fun(x, n - 1); }三个小问分别是功能、fun(2,5)的结果和递归调用次数、最多递归调用次数。这是考递归最基础的一题但每年都有人数错调用次数。函数当n为1时返回x否则返回x乘上fun(x,n-1)展开就是x乘以x乘以x……一共乘n次功能是计算x的n次方。fun(2,5)就是2^5等于32。执行过程fun(2,5)调用fun(2,4)fun(2,4)调用fun(2,3)fun(2,3)调用fun(2,2)fun(2,2)调用fun(2,1)fun(2,1)直接返回2。中间发生了4次递归调用如果算上初始的fun(2,5)总调用次数是5。题目问的是“发生了多少次递归调用”答4次说明是除去第一层之外的调用。第三个问“最多发生几次递归调用”这是个文字陷阱。从代码看每次n减1递归深度是n-1所以最多有n-1次递归调用。但前提是n为正整数。函数没有对n0做任何保护如果传入n0或者负数会无限递归直到栈溢出。答题时把这个缺陷指出来顺便提出改进写法if(n0) return 1; if(n0) return 1.0/fun(x,-n);这题就从“能算”变成“算得完整”。3.3 链栈选型、稀疏矩阵压缩与顺序表删除错误定位第三题问带头节点的单链表、不带头节点的循环单链表、带头节点的双链表哪个最适合做链栈。栈的特点是只在一端插入和删除也就是栈顶操作。带头节点的单链表只需要O(1)时间在头节点后完成入栈出栈结构最简单没有多余指针空间开销最小。不带头节点的循环单链表虽然也能操作但删除栈顶元素时要找到最后一个节点的前驱需要遍历增加开销。带头节点的双链表冗余度太高除了额外的前驱指针还要维护两个方向的链接关系用在这里有点杀鸡用牛刀。所以选带头节点的单链表理由就两条操作集中在头节点、额外空间开销最小。第四题问特殊矩阵和稀疏矩阵两种压缩方法哪个失去随机存取功能。特殊矩阵是元素分布有规律的矩阵比如对称矩阵、三角矩阵、对角矩阵它能根据行列号用公式直接算出压缩存储后的一维下标随机访问O(1)。稀疏矩阵靠三元组表、十字链表来存储非零元素元素位置和行列号之间没有可计算的地址映射要找一个特定元素只能顺序扫描三元组或沿链表查找自然失去了随机存取功能。答案很明确稀疏矩阵压缩方法失去随机存取能力。解释的重点是“有规律”和“无规律”的区别以及三元组表按行顺序存储后只能二分或顺序查找。第五题是删除顺序表第一个元素的错误分析题。代码是这样的void del(SqList L) { int i; for (i 1; i L.length; i) L.data[i - 1] L.data[i]; }错误不止一个。最致命的是参数SqList L按值传递C语言里函数内对结构体的修改不会传回外部删除操作等于没做。正确写法是void del(SqList L)传引用。其次是循环结束后没有把L.length减1表长没变表尾还残留一个无效元素。最后缺少对空表的判断L.length为0时循环条件i0直接不执行还好但如果length等于1循环不执行但逻辑上也没问题真正危险的是判断为空表后继续访问data[1]这类越界行为。这题答题顺序建议先列“缺少引用传递”“未更新表长”“未判空”三个错误再给出完整修正代码。顺序表删除的时间复杂度本来就是O(n)这题考的是细节答得越全分越高。4. 应用大题归并排序、最小生成树、BST与哈希表的完整执行过程4.1 二路归并排序从相邻配对到完整有序的每一趟结果应用分析题直接甩出一个整数序列{15,5,16,2,25,8,20,9,18,12}要求写出二路归并排序每一趟的结果。二路归并的核心是“先拆到最小再两两合并”但考试时不会让你拆到单个元素而是直接按相邻子序列逐趟归并。第一趟把10个元素分成5个二元组每组内部排序得到{5,15}、{2,16}、{8,25}、{9,20}、{12,18}第二趟相邻两个有序段合并前四组合并成两个四元素段最后一段单着{2,5,15,16}、{8,9,20,25}、{12,18}第三趟把两个四元素段合并成一个八元素段{12,18}仍然单着{2,5,8,9,15,16,20,25}、{12,18}第四趟合并剩余两段{2,5,8,9,12,15,16,18,20,25}这里最容易写错的是第二趟二路归并的“二路”指的是每次合并两个相邻的有序序列不是严格把数组切成两段五五开。奇数个元素时最后落单的那一段不参与本趟归并直接照抄到下一趟这是标准答案的一部分。另外注意归并排序是稳定排序值相同时原序列靠前的元素在结果里仍在前面这题没有重复值但答题时可以顺手提一句。4.2 普里姆与克鲁斯卡尔最小生成树的两种执行过程写法第二题给了一个带权无向图起点是顶点0要求写出普里姆算法和克鲁斯卡尔算法的执行过程。这类题阅卷只看两样每一步选了哪条边、有没有成环。以起点的普里姆算法为例答题格式要清晰。过程中维护两个集合已选顶点集合U和未选顶点集合V-U。每一步扫描所有横跨两个集合的边挑权值最小的加入生成树把对应顶点并入U。我一般会把过程列成表格四列分别写当前U集合、当前候选边、选中的边、边权。第一行U{0}候选边是0连出去的所有边选权值最小的第二行U{0,某个顶点}候选边更新一直写到所有顶点都进U。如果存在权值相同的边选哪一条都算对最后生成树可能不唯一但总权重相同。克鲁斯卡尔算法的答题格式恰恰相反先做全局排序把图中所有边按权值从小到大列出然后从左到右逐条判断只要不构成环就选入生成树构成环就跳过。判断成环的朴素做法是看这条边两个端点是否已经通过之前选的边连通。手算时画一个并查集草图或者直接盯住生成树森林的连通分量变化比较直观。克鲁斯卡尔不要求指定起点这是它与普里姆最大的区别也是比较爱考的知识点。题目如果没说起点就用克鲁斯卡尔指定起点优先用普里姆。4.3 二叉排序树根据先序遍历构造并计算两种ASL第三题给一棵二叉排序树的先序序列(12,5,2,8,6,10,16,15,18,20)要求构造树、写中序序列、算查找成功和不成功的平均查找长度。二叉排序树的中序序列一定是递增序列所以第二问可以直接写2,5,6,8,10,12,15,16,18,20。这一问基本送分但能顺便验证你第一问构造的树对不对。构造的规则是逐个插入12是根5比12小放左子树2比5小放5的左子8比5大放5的右子6比8小放8的左子10比8大放8的右子16比12大放12的右子15比16小放16的左子18比16大放16的右子20比18大放18的右子。画出来是一棵不规则的树左深右浅这是直接插入序列的结果不是平衡树。查找成功ASL 每个结点的深度加1之和除以结点数。逐一算深度12在第1层5和16在第2层2、8、15、18在第3层6、10在第4层20在第4层不对18在第3层、20是18的右孩子在第4层。那么成功ASL(1223344334)/1029/102.9。我前面计算时有过一版3.3那个把16也算了第三层重新检查后正确值是2.9。查找不成功ASL要统计所有空指针的深度。对BST来说每个查找失败的位置对应一个外部结点共有n111个。把这11个区间画在树上分别深度为小于2的失败节点深度是32和5之间深度35和6之间深度46和8之间深度58和10之间深度510和12之间深度412和15之间深度315和16之间深度416和18之间深度318和20之间深度4大于20深度4。求和除以11(33455434344)/1142/11≈3.82。这部分是大多数人的丢分点因为失败节点的位置比成功节点更难画建议考前专门练几道同类题。4.4 平衡二叉树四种旋转调整的插入过程推演第四题给整数序列{4,5,7,2,1,3,6}要求构建空平衡二叉树写出每个元素插入过程并标注调整类型。AVL的调整类型只有四种LL型右旋、RR型左旋、LR型先左后右、RL型先右后左。判断依据是最小失衡子树的根、它的孩子、以及插入位置三者之间的方向关系。一步步推插入4根为4。插入54的右孩子平衡因子-1没问题。插入7此时4的右孩子55的右孩子74的平衡因子变成-2属于RR型对4做一次左旋。旋转后5成为根4在左7在右。插入25的左子树此时根5平衡因子1树没失衡。插入12的左孩子2的平衡因子1但5的平衡因子变为2失衡点其实是5的孩子2这条链属于LL型检查最小失衡子树根是22的左孩子1插入在左孩子的左子树对2做右旋。旋转后2升为5的左孩子1在2左4变为2的右孩子。插入33比4小放在4的左子树。此时根5平衡因子还是1但4的平衡因子是-1等等4的右子树为空左孩子为34的平衡因子是1树整体平衡。最后一颗树的结构我不再展开答题时每插入一个数都要画一次树形图重点标注失衡节点和旋转轴。实战中考卷只看最终树形和旋转类型是否正确。每次旋转后重新计算平衡因子这步不能省少算一次后面全错。另外要注意LR和RL是双旋第一次旋转后得到的中间状态也要画出来不要直接跳到最后结果。4.5 哈希表线性探查构造哈希表与查找ASL计算口径第五题是哈希表经典题一组关键字{32,13,49,24,38,21,4,12}哈希函数H(key)key%7用线性探查法处理冲突地址空间0到9求构造的表和查找成功、失败的ASL。逐个计算哈希地址。32%74放入413%76放入649%70放入024%73放入338%73冲突线性探查到44被32占用继续到5放入521%70冲突探查1为空放入14%74冲突探查5被38占用6被13占用7为空放入712%75冲突6被13占用7被4占用8为空放入8。最终表为下标0到9依次是49、21、空、24、32、38、13、4、12、空。查找成功ASL 每个关键字查找时的比较次数之和除以关键字个数。32比较1次13比较1次49比较1次24比较1次38比较3次21比较2次4比较4次12比较4次总和是17除以8等于2.125。这是标准口径直接算就行。查找失败ASL是容易翻车的地方。教材常见做法是对哈希地址0到6模数范围内从该地址开始遇到空位停比较次数为该位置到空位的距离加1。0号位置是49、1号是21、2号空所以0号的失败比较次数是31号是21、2号空失败为22号空失败为13号是24、4号32、5号38、6号13、7号4、8号12、9号空失败为74号到9号空为65号到9号空为56号到9号空为4。总次数是321765428除以7等于4。如果你们教材把失败查找范围定义为表长0到9那要取0到9每个位置扫到空位的次数再除以10口径完全不同。考试前先确认老师上课用的口径这个没有统一标准。5. 程序设计题与排查二叉树递归建模、链表删最小与五个易错点5.1 求度为2的结点个数递归模型与函数实现程序设计题第一题要求求二叉树中度为2的结点个数并给出了BTNode结构体。度为2就是左右孩子都存在。最简单可靠的写法是递归模型f(b) 0当b为空f(b) f(b-lchild) f(b-rchild) 1当b左右孩子都不为空否则f(b) f(b-lchild) f(b-rchild)。int Degree2(BTNode *b) { if (b NULL) { return 0; } int cnt 0; if (b-lchild ! NULL b-rchild ! NULL) { cnt 1; } return cnt Degree2(b-lchild) Degree2(b-rchild); }每次递归把自己这层是否度为2判断后再下探左右子树。注意这里return表达式里的cnt加在递归结果之前不影响求和顺序。递归出口是空节点返回0叶子节点进入函数后cnt为0返回左右子树的递归结果0加0自然统计不到它。度为2的节点统计的是“同时有左右孩子”的内部节点根节点如果左右都在也要算进去。这个写法的时间复杂度是O(n)每个节点访问一次。如果题目要求写模型设计还要给出函数实现最好先把递归模型用文字或公式写出来再上代码。阅卷时模型和代码各占一半分只写代码不写模型丢掉一半分的情况很常见。也可以考虑用全局变量计数每遇到一个双孩节点就加一但那样破坏封装性考场不推荐。5.2 删除单链表中所有最小结点两遍扫描与指针陷阱第二题要删除带头结点单链表L中所有值最小的结点函数声明是DelNode(LinkList *L)。这道题有两个考点找最小值和删除多个结点。我第一次写这道题的时候只删了一个最小值结点漏了“所有”两个字这是最常见的翻车点。先扫描一遍找最小值用min变量记录再扫描第二遍凡是值等于min的结点全部删除。删除时用pre指向当前结点的前驱cur指向当前结点找到目标后执行pre-nextcur-next并free(cur)注意free之后cur不能再往下走要让cur等于pre-next。void DelNode(LinkList *L) { if (L NULL || L-next NULL) { return; } LinkList *p L-next; int min p-data; while (p ! NULL) { if (p-data min) { min p-data; } p p-next; } LinkList *pre L; LinkList *cur L-next; while (cur ! NULL) { if (cur-data min) { pre-next cur-next; free(cur); cur pre-next; } else { pre cur; cur cur-next; } } }参数这里传的是LinkList *L因为带头结点头结点本身不用改改的是L-next所以传值指针够了。如果题目改成不带头结点那删除首结点时需要让头指针本身变化必须用LinkList **L或者返回新头指针。动手写之前先判断题目给的是带头结点还是无头结点别把两种写法弄混。遍历找最小值时p从L-next开始而删除时pre从L开始、cur从L-next开始这两个初始条件不一样是很多人写错指针位置的地方。删除后如果当前节点被free不能执行curcur-next因为cur已经失效必须用pre-next作为新的cur。5.3 排查清单五个高频错误与修正练这套卷子时最容易遇到下面五个问题每一条都是我实际改代码和批改作业时反复见过的。第一顺序表删除函数参数漏掉引用。现象是调用del(L)后打印L表内容纹丝不动。原因是C语言函数参数按值传递结构体副本被修改原件不受影响。解决方法是把参数改为SqList L或者在原函数中返回新的表长。从那以后我每次设计顺序表操作函数第一件事就是确认参数是否需要修改原结构体。第二归并排序的趟数写死。现象是“第一趟后就直接写最终结果”跳跃式作答。原因是没有处理奇数个元素时落单子序列的制度。解决方法是把每趟参与归并的分段边界写清楚落单段原样抄到下一趟。第三哈希查找失败ASL和老师的口径不一致。现象是算出来的值有4和3.28两种。原因是一个按模7范围算一个按表长10算。解决方法是提前翻教材例题搞清楚这门课用的是哪种约定。第四二叉排序树成功ASL把根节点深度写成0。现象是结果比标准答案少了1。原因是有些教材根节点深度为0有些为1。解决方法是看题目或课本中样例的深度定义一般考试会按深度从1开始算但算完校验一下单节点树的成功ASL应该是1不是0。第五删除链表最小值结点后循环里还执行curcur-next。现象是程序崩溃或漏删。原因是free(cur)之后又用cur访问next野指针。解决方法是看当前节点是否被删除被删除时cur已由pre-next更新不要再移指针。这些坑单独看都简单组合在同一张卷子里就很占时间。考前花一个下午把这些边界条件全部过一遍比闷头刷一百道选择题更划算。6. 复习验证法把试卷变成动态查漏工具资料拿到手别急着从头到尾做一遍就完事。我习惯把一份期末试卷当“诊断工具”用第一遍严格按考试时间闭卷做做完不对答案先给每道题标一个状态符号完全会的打勾、模棱两可的画半圆、完全没思路的打叉。打勾的题不用再看半圆和打叉的才是你真正的复习对象。第二步把所有半圆和打叉的题按知识点归类。比如发现“平衡二叉树旋转”打叉、“哈希失败ASL”半圆那就说明树和查找这两块需要重点回炉。回炉时不要只重做这道题而是去找同一知识点的变式平衡二叉树换成{10,20,30,5,15,25}再推一遍哈希表的装填因子换大一点再算一遍。同一个知识点连续做对三道变式题才算真正掌握。第三步在考前一天做“回溯演练”。把这份卷子的题目列表当成目录不看答案从头到尾口述每一题的解题步骤。口述到普里姆算法时必须能说出“每次选横跨已选集合和未选集合之间权值最小的边”口述到二叉排序树不成功ASL时必须能画出外部节点。卡壳的地方立刻翻笔记用红笔在旁边标注。这个过程的本质是强制提取记忆比再看一遍笔记有效得多。最后分享一个我自己的笨办法把每道错题的错误原因写在一张便签纸上压在键盘下。每次再看到同类题先回忆那张便签上写的是什么坑。从那以后我每次复习数据结构都强制走一遍“闭卷做题、标记状态、变式巩固、回溯演练”这套流程花费的时间只有闷头刷题的六成但考试时的稳定感高很多。希望帮到你。本文还有配套的精品资源点击获取