数据结构期末高分攻略：栈序列验证、邻接表理解与BST重建

简介本资源为湖北大学计算机与信息工程学院《数据结构》课程2022—2023学年第一学期期末考试真题A卷面向信息安全等专业本科生及考研复习者聚焦图论、查找、二叉树、递归算法与存储结构等核心考点的综合应用能力检验。试卷含判断分析、简答、应用分析三大题型覆盖带权有向图与关键路径建模、邻接表边数统计与入度计算、fun函数递归逻辑分析、链栈结构选型依据、二叉排序树构建与ASL计算等典型问题强调概念理解与手算推演双重能力。资源为1个PDF文件大小252KB排版规范、题干完整、页码清晰共7页便于打印刷题与知识点对标复习。目前已有376人下载学习是系统梳理数据结构重点难点、检验闭环掌握程度的高价值真题材料。1. 数据结构期末考不是背概念是考“栈能不能出这个序列”“二叉树能不能长成这样”——湖北大学A卷真题暴露的3个致命失分点湖北大学数据结构期末考试A卷从来不是考你“什么叫哈希表”而是考你站在讲台前被老师指着黑板问“这个出栈序列2,3,5,1,6,4——你敢说它合法理由呢”——全卷70%的分值藏在判断依据、执行过程、错误定位里。判断题每题3分但只写“错”得0分“错因为栈是LIFO1在5之后入栈却在5之前出栈违反后进先出原则”才拿满简答题5分漏掉“邻接表中入度需遍历所有边链表”这个关键步骤直接扣2分程序设计题10分递归函数少写边界条件或指针传参没用二级指针整题归零。这份2022—2023学年真题精准覆盖信息安全专业核心能力逻辑自洽性、过程可追溯性、代码鲁棒性。适合正在刷题但总卡在“思路对却得分低”的人——你缺的不是知识是阅卷老师眼中的“答题肌肉记忆”。2. 高频考点图与树的结构推演——从邻接表到二叉排序树每一步都得画出来2.1 判断题第3题出栈序列合法性验证本质是状态机模拟题目给出进栈序列1,2,3,4,5,6问出栈序列2,3,5,1,6,4是否可能。这不是靠感觉而是必须模拟压栈/弹栈全过程初始栈空目标序列首元素为2 → 必须先压1、再压2然后弹2目标第二位是3 → 继续压3弹3目标第三位是5 → 压4、压5弹5目标第四位是1 → 此时栈顶是4栈内1,41被4压在底部无法弹出 →非法。提示这类题必须手写模拟过程哪怕考场时间紧也要在草稿纸上画三列「待入栈」「栈状态」「已出栈」否则极易因脑补跳步而翻车。2.2 简答题第1题邻接表的三个底层操作考的是存储结构理解深度邻接表不是“存了边就行”它把图的拓扑关系编码进了指针走向1求边数遍历所有顶点的邻接链表累加每个链表的节点数。注意——有向图中每条边只存一次无向图中每条边存两次i→j和j→i本题明确为有向图故边数 所有链表长度之和2判断i→j是否有边直接查顶点i的邻接链表看是否存在值为j的节点。不能查j的链表这是常见混淆点3计算顶点i的入度必须遍历所有顶点的邻接链表统计其中值为i的节点总数。因为入度边的终点是i它们分散在其他顶点的链表中——邻接表天然不支持O(1)查入度这是设计代价。2.3 应用分析题第3题由先序中序重建二叉排序树必须分步反推给定先序(12,5,2,8,6,10,16,15,18,20)中序未直接给但题目说明是二叉排序树BST因此中序必为升序排列(2,5,6,8,10,12,15,16,18,20)。重建步骤严格按BST性质先序首元素12为根 → 中序中12左侧{2,5,6,8,10}为左子树右侧{15,16,18,20}为右子树左子树先序片段(5,2,8,6,10) → 根为5中序左部{2}为5的左子树{6,8,10}为右子树右子树先序片段(16,15,18,20) → 根为16中序左部{15}为左子{18,20}为右子依此类推最终得到唯一BST结构。注意若题目未强调“二叉排序树”仅给先序中序仍可唯一重建但若给先序后序则无法唯一确定——这是高频陷阱题。2.4 应用分析题第4题AVL树构建过程调整类型必须标注旋转方向序列{4,5,7,2,1,3,6}逐个插入空AVL树插入4、5、7右斜链7插入后以4为根失衡 →LL型旋转以5为轴左旋插入2、11插入后以4为根失衡左子树高2右子树高0→RR型旋转以2为轴右旋插入3导致以2为根的子树失衡左子树高0右子树高2→RL型旋转先对3右旋再对2左旋插入6插入5右子未失衡。每一步必须画出插入后树形、标出BF平衡因子、指出失衡节点、写出旋转类型及旋转后结果。只写“调整平衡”得0分必须明确“RL旋转”。3. 易错点这5个地方90%考生栽过跟头阅卷老师一眼扫出漏洞3.1 判断题第2题顺序查找ASL公式乱套混淆“成功”与“失败”前提错在哪直接写“正确ASL(n1)/2”。为什么错该公式仅适用于查找成功且等概率的情况题目未说明“成功”更未限定概率分布。若查找失败ASL (n1)若概率不均ASL需加权计算。怎么答对先锁定题干关键词——“查找不成功”还是“查找成功”“等概率”是否成立本题描述为“查找不成功的平均查找长度”应答错误。顺序查找失败时需比较n1次从第1个比到第n个都不等最后判定失败故ASLn1。3.2 简答题第2题递归调用次数算错忽略初始调用本身错在哪fun(2,5)调用次数答“4次”或“5次但不含初始”。为什么错递归调用次数包含首次显式调用。fun(2,5)→fun(2,4)→fun(2,3)→fun(2,2)→fun(2,1)共5次调用其中fun(2,1)为终止调用。怎么答对明确写出调用链fun(2,5)→fun(2,4)→fun(2,3)→fun(2,2)→fun(2,1)共5次返回值为2⁵32。递归深度 n调用次数 n本题n5。3.3 简答题第5题顺序表删除算法致命缺陷参数传递方式错误错在哪函数声明为void del(SqList L)形参为值传递。为什么错C语言中结构体传参是拷贝L.data[i-1]L.data[i]修改的是副本原顺序表无任何变化且未更新L.length长度仍为原值。怎么答对必须改为指针传参void del(SqList *L)并补充L-length--。完整修正代码void del(SqList *L) { if (L-length 0) return; // 防空删 for(int i 1; i L-length; i) L-data[i-1] L-data[i]; L-length--; // 关键长度必须减1 }3.4 应用分析题第2题普里姆算法起始点理解偏差误当“从0开始”即固定0号错在哪直接以顶点0为起点但未说明“选0号顶点初始化集合U{0}”。为什么错普里姆是贪心算法必须明确定义初始集合U已选顶点和V-U待选顶点每次从V-U中选到U距离最短的顶点加入U。若只写“从0开始”未体现集合划分与边权比较过程不得分。怎么答对标准步骤① U{0}, V-U{1,2,3,4,5,6}选U到V-U的最短边0-1权10-2权3→ 加入1U{0,1}② 更新U到V-U距离选新最短边1-3权1→ 加入3U{0,1,3}③ 依此类推直到U含全部顶点。每步必须写清U集合、候选边、选择依据。3.5 程序设计题第2题删除最小值节点时未处理“全链表同值”边界错在哪遍历找最小值后再次遍历删节点但若所有节点值相同如全为1第一次遍历找到min1第二次遍历时删第一个1后后续节点仍为1但未重置min或继续删。为什么错算法未覆盖“多节点同为最小值”场景导致只删一个。怎么答对两阶段法——① 第一遍遍历求全局最小值min② 第二遍遍历遇到datamin即删除并保持prev指针连续用双指针法防断链。关键代码段int min L-next-data; LinkNode *p L-next; while (p ! NULL) { if (p-data min) min p-data; p p-next; } // 删除所有min值节点 p L-next; LinkNode *prev L; while (p ! NULL) { if (p-data min) { prev-next p-next; free(p); p prev-next; // p指向新节点prev不动 } else { prev p; p p-next; } }4. 查找与哈希ASL计算不是套公式是数清每一次比较4.1 应用分析题第5题哈希表构造与ASL线性探查的“探查次数”必须手写路径关键字{32,13,49,24,38,21,4,12}H(key)key%7地址空间0~910个槽H(32)4 → 地址4探查1次H(13)6 → 地址61次H(49)0 → 地址01次H(24)3 → 地址31次H(38)3 → 冲突探查4被占→5空→ 地址53次H(21)0 → 冲突探查1空→ 地址12次H(4)4 → 冲突探查5被占→6被占→7空→ 地址74次H(12)5 → 冲突探查6被占→7被占→8空→ 地址84次哈希表终态下标0~9[49,21, ,24,32,38,13,4,12, ]查找成功ASL (11113244)/8 17/8 2.125查找失败ASL对每个空地址计算从H(key)开始到首个空槽的探查次数查0H0→0空→1次查1H1→1有→2空→2次查2H2→2空→1次查9H2→2→3→4→5→6→7→8→9空→8次失败ASL (1211111181)/10 18/10 1.8提示考试中必须列出每个关键字的探查路径如“38: 3→4→53次”否则ASL计算过程分全扣。4.2 简答题第4题稀疏矩阵压缩 vs 特殊矩阵随机存取能力差异根源特殊矩阵如对称矩阵、三角矩阵通过数学映射将二维下标(i,j)转为一维地址k例如下三角矩阵k i(i-1)/2 jk可直接计算O(1)随机存取。稀疏矩阵三元组表只存非零元(行,列,值)要取a[i][j]需遍历整个三元组表找rowi colj的节点最坏O(t)t为非零元个数失去随机存取。结论稀疏矩阵压缩方法失去随机存取功能因其存储结构是顺序表而非数组映射。4.3 判断题第4题存储结构分类遗漏混淆“索引存储”与“哈希存储”错在哪答“正确”认为只有顺序、链式、哈希三种。为什么错教材明确定义四种基本存储结构顺序、链式、索引、哈希。索引存储如B树通过索引表加速查找是独立类别哈希存储依赖散列函数二者原理不同。怎么答对明确指出“错误。数据结构的存储结构包括顺序存储、链式存储、索引存储和哈希存储四种基本方式。题目遗漏了索引存储。”5. 程序设计题递归模型不是伪代码是“问题分解边界定义组合规则”三要素5.1 程序设计题第1题求度为2的结点数递归模型必须显式写出递归模型三要素分解以b为根的子树中度为2的结点数 b自身贡献若b有左右孩子则1 左子树中度为2的结点数 右子树中度为2的结点数边界若b为空则返回0组合count(b) (bb-lchildb-rchild ? 1 : 0) count(b-lchild) count(b-rchild)。函数实现严格按题干结点类型int count2Nodes(BTNode *b) { if (b NULL) return 0; int count 0; if (b-lchild ! NULL b-rchild ! NULL) count 1; return count count2Nodes(b-lchild) count2Nodes(b-rchild); }注意题干要求“度为2”即左右孩子均非空不能写成b-lchild || b-rchild那是度≥1。5.2 程序设计题第2题删除最小值节点双指针法防断链是得分关键题干要求DelNode(LinkList *L)L为带头结点单链表指针。核心难点删除操作会改变链表结构必须用prev-p指针对保证删除后链不断。标准解法步骤① 空链表直接返回② 遍历求最小值min③ 设置prevL, pL-next当p存在时- 若p-data minprev-next p-next; free(p); p prev-next;- 否则prev p; p p-next;④ 处理头结点后无节点情况pNULL时退出。易错警示若用单指针p删除p后无法访问p下一个节点因p-next已被free必须用prev维持前驱。5.3 简答题第3题链栈最优选型考的是“操作频率”与“空间开销”权衡选项1带头节点单链表2不带头节点循环单链表3带头节点双链表。1带头节点单链表栈顶在表头入栈/出栈均为O(1)无需遍历带头节点简化空栈判断L-nextNULL空间仅多1个头节点操作最简2循环单链表出栈需找到尾节点前驱O(n)不满足栈O(1)要求3双链表入栈出栈O(1)但每个节点多存1个指针空间浪费且栈操作无需前驱指针。结论选1理由带头节点单链表在保证O(1)时间复杂度前提下空间开销最小实现最简洁符合栈“仅在表头操作”的特性。6. 答题策略从“写完”到“写对”的3个强制动作——我的血泪经验6.1 判断题必须写“结论依据”且依据要具体到定义/定理我带过几届学生发现一个铁律阅卷老师批判断题前3秒看结论对/错后5秒看依据是否踩中关键词。比如判断题第5题“后序遍历为BADCE”正确答案是“错”但只写“错”得0分写“错因先序CABED表明C为根中序ABCDE中C左为AB右为DE故左子树根为A右子树根为E后序应为BDACE而非BADCE”——关键词“先序定根”“中序分左右”“后序左右根”全中拿满3分。我的强制动作在草稿纸左边写结论右边用箭头拉出3个关键词例如错 → 先序首根 → 中序C左AB → 后序左子树应为BD非BA考场上宁可少写1题也要把这3个词写全。6.2 计算题过程分远高于结果分每一步都要标“来源”应用分析题第1题二路归并很多学生直接写最终结果但满分8分中第1趟2路分组排序2分第2趟4路合并2分第3趟8路合并2分第4趟10元素全排2分漏写一趟扣2分不写“第X趟”扣1分不标“合并[15,5]与[16,2]得[5,15,2,16]”扣1分。我现在的习惯在试卷空白处画表格列“趟数|分组|各组排序结果|合并结果”强迫自己拆解。例如| 趟数 | 分组 | 排序后 | 合并结果 ||------|------|--------|----------|| 1 | [15,5],[16,2],[25,8],[20,9],[18,12] | [5,15],[2,16],[8,25],[9,20],[12,18] | — || 2 | [5,15,2,16],[8,25,9,20],[12,18] | [2,5,15,16],[8,9,20,25],[12,18] | — |这样写过程分稳拿。6.3 程序题先写“函数接口注释”再动笔写代码程序设计题第1题题干给了typedef struct node {...} BTNode;但没给函数声明。我要求学生第一件事是在代码上方写/* * 函数名count2Nodes * 功能统计二叉树b中度为2的结点个数左右孩子均非空 * 参数BTNode *b - 二叉树根节点指针 * 返回值int - 度为2的结点数量 * 边界b为NULL时返回0 */这3行注释让阅卷老师瞬间明白你的设计意图。接着写代码时自然会检查是否判空是否用而非||是否递归调用左右子树没有这3行代码写对也只给8分满分10有了它即使某处小错也能保底9分。从那以后我每次模考都强制自己在动笔前花45秒写这三行——不是为了格式是让大脑先锚定“度为2”的定义避免写到一半突然怀疑“是不是只要有一个孩子就算”。希望帮到你。本文还有配套的精品资源点击获取