简介这份湖北大学数据结构期末试卷面向准备课程复习与自测的计算机相关专业学生内容为2022—2023学年度第一学期A卷试题包含判断分析、简答与应用分析等题型。试卷覆盖带权有向图与关键路径、邻接表存储、出栈序列判断、顺序查找平均查找长度、二叉树遍历与构造、递归函数fun(x,n)、链栈选择、矩阵压缩、二路归并排序、Prim与Kruskal算法、二叉排序树、平衡二叉树及哈希线性探查等章节既能帮助梳理概念也便于训练计算与算法分析过程。资源包共1个PDF文件大小约252KB结构紧凑适合打印或平板阅读。已有376人学习可用于期末查漏补缺和检验复习效果。1. 分数分布判断15、简答25、应用40、程序20分值主要丢在哪翻开一份数据结构期末试卷多数人先盯最后两道程序设计题但真正拉开差距的是开头的判断分析题——这套卷子五道判断题逐条验证下来结论全落在「错」上连打五个叉考场上没几个人敢这么写。整张卷子的结构很清楚判断分析15分、简答25分、应用分析40分、程序设计20分应用分析独占四成说明这场考试的重心是手算和过程书写而不是背概念。判断题考你能不能找到反例简答题考你能不能把操作说清楚应用分析考每一步能不能老老实实写在纸上程序设计考递归模型立不立得起来。适合已经过完一遍教材、一做题就卡在「知道概念却写不出过程」的人。2. 判断与简答40分文字题的逐题答案骨架2.1 判断分析题五道命题的陷阱与说理模板五道判断题分值不高但每题3分里有1分是判断、2分是理由很多人判断对了、理由写崩了只拿1分。这类题通常的写法是「判断 指出错在哪 给出正确结论或反例」三句话不是把课本定义默一遍。第1题「用带权有向图描述工程进度缩短关键路径上某个活动的时间一定能缩短整个工程工期」结论是错。破在「一定」两个字上关键路径可能不唯一你缩短的那条只是其中一条另一条关键路径还在原地卡着工期不变其次是缩短到一定程度后关键路径会转移原本的非关键路径变成新的瓶颈再者活动时间不能无限压缩受资源和工艺下限约束。答这类题的得分点在于点明「关键路径不唯一」和「关键路径会转移」只写「错不一定」拿不到2分。第2题「顺序查找不成功的平均查找长度为 (n1)/2」错在把成功和不成功混为一谈。(n1)/2 是等概率下查找成功的 ASL查找不成功时要一直比到表尾无哨兵是 n 次带哨兵是 n1 次。这题的教训是凡是看到 ASL 公式先确认它说的是成功还是不成功分母是什么。第3题进栈 1~6、判断出栈序列 2,3,5,1,6,4 是否可能出现答案是不可能。推的过程要写出来出2时1、2入栈出2出3时3入栈即出出5时4、5入栈出5此刻栈内自底向上是1、4栈顶是4要出1必须先出4而序列下一个要的正是1矛盾。理由写到「栈内元素次序被锁定」这一层才算把分拿稳。第4题「存储结构包括顺序存储、链式存储、哈希存储三种」错在漏项。物理结构分为顺序、链式、索引、散列四种命题少列了索引存储而且「哈希存储」的规范叫法是散列存储。这类概念题只要动一个词就能判错别急着打勾。第5题给中序 ABCDE、先序 CABED 求后序命题给 BADCE错。还原过程先序首字符 C 是根中序里 C 左边 AB 是左子树、右边 DE 是右子树左子树先序 AB根 AB 为 A 的右孩子右子树先序 ED根 ED 为 E 的左孩子。后序为 B、A、D、E、C即 BADEC。命题把 D 和 E 的顺序对调了。提示判断分析题不要只写结论。3分题里结论1分、理由2分理由必须落到具体的反例、公式适用条件或次序矛盾上。2.2 邻接表三问边数、判边、入度的标准答法第一问求边数。思路是遍历顶点数组对每个顶点 i 沿着它的出边链表走一遍每访问一个边结点计数加一走完全部顶点后累加值就是有向图的边数 e。复杂度 O(ne)。如果换成无向图每条边在邻接表里被存两次累加结果要除以2这一点必须写出来是个常见扣分点。第二问判断顶点 i 和 j 之间是否有边。在有向图里只需遍历 i 的出边链表逐个比较边结点的邻接点域是否等于 j找到即有弧 i,j找不到说明 i 到 j 没有直接弧。如果题目要判无向边 (i,j)同样只查 i 的链表就够因为无向图一条边存两份。有人答「两个链表都要查」在有向图上就错了因为 j 的链表里存在的是 j 的出边不能反推 i 到 j 的弧。第三问求顶点 i 的入度。邻接表的出度好办直接数 i 的边链表长度入度必须扫全场遍历所有顶点的出边链表统计邻接点域等于 i 的边结点个数时间 O(ne)。更快的做法是额外建一张逆邻接表把每条弧 u,v 挂到 v 的链表上这样入度等于逆邻接表里 i 的链表长度查询 O(1)代价是多一份存储、建表多一遍扫描。答题时把「直接扫描」和「逆邻接表」两种都写出来并各给复杂度比只写一种更稳。2.3 递归函数 fun(x,n)功能、结果、调用次数原函数是if (n1) return x; return x*fun(x,n-1);。这个递归模型只有一条递归出口和一条递归体属于最朴素的线性递归。double fun(double x, int n) { if (n 1) return x; // 递归出口x 的 1 次幂 return x * fun(x, n - 1); // 递归体少乘一次结果乘回 x }功能是求 x 的 n 次幂n 为正整数。fun(2,5) 的结果是 32调用链是 fun(2,5)→fun(2,4)→fun(2,3)→fun(2,2)→fun(2,1)一共发生5次函数调用如果不算最外层这一次递归调用是4次。考场上一定要写清口径写「含首次共5次其中递归调用4次」最保险只写一个数字容易被判含糊。递归深度为 n时间 O(n)、空间 O(n)因为乘法在递归返回之后做属于线性递归而不是尾递归栈帧无法省。2.4 链栈为什么选带头结点的单链表题干给三个候选带头结点的单链表、不带头结点的循环单链表、带头结点的双链表。答案是带头结点的单链表。理由是栈只在栈顶一端插入和删除链表头部天然对应栈顶进栈就是头插、出栈就是删首元结点都是 O(1)。带头结点之后空栈和非空栈的插入删除代码完全统一不用每次判断「是不是第一个结点、要不要改头指针」这是它压过不带头结点版本的关键。循环单链表虽然也能用头插但循环结构在栈这个场景里没有收益判空和遍历还要多绕一步。双链表每个结点多一个前驱指针栈操作永远只朝一个方向走多出来的指针纯属浪费空间。存储结构栈顶操作空栈处理空间开销结论带头结点单链表头插/删首元O(1)统一无需特判每结点1个指针最合适不带头结点循环单链表头插/删首元O(1)需特判空栈改指针每结点1个指针环路可用但绕带头结点双链表头插/删首元O(1)统一每结点2个指针空间浪费2.5 特殊矩阵与稀疏矩阵谁丢了随机存取结论是稀疏矩阵的压缩存储三元组顺序表失去随机存取功能特殊矩阵没有。特殊矩阵指对称矩阵、三角矩阵、对角矩阵这类非零元分布有规律的矩阵压缩后虽然从二维降到一维但下标之间仍有确定的映射公式。比如 n 阶对称矩阵只存下三角元素 a[i][j]i≥j从0开始在一维数组里的位置是 k i(i1)/2 j给任意一组 (i,j) 都能算出地址一步到位随机存取特性保住了。稀疏矩阵的非零元分布没有规律三元组表按行序把 (行号,列号,值) 依次排下去想找 a[i][j] 只能从表头开始顺序扫描比较行号列号最坏要把整张表走一遍O(t) 而不是 O(1)。要恢复随机存取就得加辅助结构比如给每行建一个行链表头指针行逻辑链接顺序表或者改用十字链表但那是用额外空间换时间不是压缩本身带来的。这题的得分点就是「稀疏矩阵 三元组 无法由下标直接算出地址」三件套缺一个都容易被扣。2.6 顺序表删除第一个元素那段代码错在哪原函数是值传递、循环移位、不更新长度void del(SqList L) { // 值传递形参是实参的副本 int i; for (i 1; i L.length; i) L.data[i-1] L.data[i]; // 前移覆盖看似删了首元 }错误至少有四处。一是参数按值传递函数里改的是副本调用者的顺序表一点没变必须改成SqList *L或者引用SqList L。二是没有执行L.length--元素前移了但表长没变最后一个元素 data[length-1] 变成重复值逻辑上表里多出一个脏数据。三是没有处理空表length 为 0 时循环不执行函数悄悄返回调用方无从知道删除失败。四是题目要求删除第一个元素函数没有把被删元素带出来一般应返回状态或值。改法int delFirst(SqList *L, ElemType *e) { if (L-length 0) return 0; // 空表删除失败 *e L-data[0]; // 保存被删元素 for (int i 1; i L-length; i) L-data[i-1] L-data[i]; // 从第二个元素起整体前移一位 L-length--; // 表长减一这一步不能漏 return 1; }移动次数是 n-1时间复杂度 O(n)空间 O(1)。考场上如果只写「应该传指针」最多拿一半分四处错误要逐条列。3. 应用分析五道手算大题的步骤模板与中间结果3.1 二路归并排序每一趟写到什么颗粒度初看是 {15,5,16,2,25,8,20,9,18,12}n10归并趟数是 ⌈log₂10⌉4 趟。手算时必须把每一趟的完整序列写出来不能跳步跳一趟就少一半分。趟次归并段长结果第1趟1→2[5,15] [2,16] [8,25] [9,20] [12,18]第2趟2→4[2,5,15,16] [8,9,20,25] [12,18]第3趟4→8[2,5,8,9,15,16,20,25] [12,18]第4趟8→16[2,5,8,9,12,15,16,18,20,25]写法上每一步都要体现「两两合并、不足两段照抄」。第2趟里最后一组只剩 [12,18] 一段直接下移第3趟同理。很多人在第1趟就把整表排完了那是把归并当成插入排序在做。空间代价 O(n) 的辅助数组也要在答案里点一句时间复杂度 O(nlog₂n)。3.2 Prim 与 Kruskal过程怎么写才不丢步骤分这两种算法在同一张带权无向图上分别构造最小生成树卷面给的图边权各不相同这里不重复抄图重点讲过程怎么在纸上写全。Prim 以顶点0为起点答题要维护两个东西已选顶点集合 U和候选边集合一端在 U、一端不在 U 的所有边。每一步做三件事——在候选边里挑权值最小的一条、把它连的顶点并入 U、更新候选边。重复 n-1 次。卷面上建议画一张小表列出「步骤、选中的边、权值、U 集合」n 个顶点的图就是 n-1 行阅卷时一眼能对上。Kruskal 从空图开始把所有边按权值升序排成一张表依次取边用并查集判断这条边两端是否已连通不连通就加入连通就丢弃直到选够 n-1 条。答题时的标准格式是「边(权值) → 加入/丢弃 → 理由」丢弃的边必须写理由比如「两端已同属一个连通分量加入会成环」。只写加入的边不写丢弃的边过程分会被砍。对比项PrimKruskal扩展方式从一个顶点向外长树按边权从小到大选边判环手段无需判环只选跨集合边并查集判连通时间复杂度O(n²)堆优化后 O(e log n)O(e log e)适用图稠密图稀疏图两种算法结果不唯一时存在等权边只要总权值相同、边数 n-1、无环都算对这一点不用纠结。3.3 二叉排序树由先序序列还原、中序验证、两个 ASL给先序 (12,5,2,8,6,10,16,15,18,20)按先序顺序依次插入空树即可因为先序序列的第一个永远是当前子树的根。得到12 为根5、16 分别是左右孩子5 下挂 2左和 8右8 下挂 6左和 10右16 下挂 15左和 18右18 右挂 20。中序遍历一遍验证2,5,6,8,10,12,15,16,18,20严格递增说明构造正确。这一步别省它是自查手段。查找成功的 ASL 按结点所在层数算比较次数第1层 12 是1次第2层 5、16 各2次第3层 2、8、15、18 各3次第4层 6、10、20 各4次。总和 14121229ASL成功 29/10 2.9。查找不成功要数外部结点也就是 11 个空指针域n1 个。每个空指针的比较次数等于它父结点所在层数结点2的两个空各3次6、10、20 各两个空各4次15 两个空各3次18 的左空3次。合计 3×24×24×23×234×239ASL不成功 39/11 ≈ 3.55。注意不同教材对「不成功 ASL」的分母口径不一有的按空指针数 n1有的按失败区间数。答题时把分母写清楚比只写一个数字安全。3.4 平衡二叉树四种旋转的判定与每步记录序列 {4,5,7,2,1,3,6}逐个插入并记录平衡因子。插4单结点。插5作4的右孩子4 的 BF-1平衡。插74 的 BF-2右孩子的右边过高属 RR 型对4左旋根变5左4右7。插2挂4左。插1挂2左此时4 的左子树高2、右0BF2属 LL 型对4右旋结构变为 5(左2(左1,右4), 右7)各结点 BF 恢复在 -1~1。插3挂4左5 的 BF2 失衡5 的左孩子2 的右子树偏高属 LR 型先对2左旋、再对5右旋得到 4(左2(左1,右3), 右5(右7))。插6经4、5 到7 的左5 的 BF-25 的右孩子7 的左子树偏高属 RL 型先对7右旋、再对5左旋最终 4(左2(左1,右3), 右6(左5,右7))。失衡结点失衡方向插入位置旋转类型处理4左重左孩子的左子树LL对4右旋5左重左孩子的右子树LR先左旋2再右旋55右重右孩子的左子树RL先右旋7再左旋5答题时每插一个结点就画一次树并在结点旁标 BF遇到调整就注明类型和旋转对象最后再中序扫一遍确认递增这套动作做全8分基本拿满。判断 LL/RR/LR/RL 不能只看插入结点落在哪一侧要看失衡结点较重的那棵子树的「内侧还是外侧」这是最容易翻车的地方。3.5 哈希表线性探查构造表与两个 ASL关键字 {32,13,49,24,38,21,4,12}H(key)key%7地址空间 0~9线性探查。32%74落413%76落649%70落024%73落338%73 冲突顺延到521%70 冲突顺延到14%74 冲突4、5、6 都占落712%75 冲突5、6、7 都占落8。| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | --- | --- | --- | --- |本文还有配套的精品资源点击获取