企业官网建设流程全解析

简介：湖北大学2022—2023学年度第一学期数据结构课程考试（A卷）PDF试卷，面向计算机与信息工程学院信息安全等专业学生及备考数据结构期末的读者，可用于考前自测、考点梳理与答题思路训练。试卷按判断分析、简答、应用分析等题型组织，内容涉及带权有向图与关键路径、邻接表存储、顺序查找平均查找长度、出栈序列判断、二叉树先中后序遍历、递归函数调用次数、链栈存储结构选择，以及二路归并排序、Prim与Kruskal最小生成树、二叉排序树、平衡二叉树调整和哈希表线性探查等典型题目。压缩包内共1个PDF文件，大小约252KB，版面完整、篇幅紧凑，便于打印成册或电子端翻阅。已有376人学习，适合作为期末复习阶段的限时模拟与查漏补缺材料，帮助读者按章节定位薄弱环节，熟悉综合应用题的推导与书写过程。

1. 知识地图：一份数据结构期末考试卷到底在考什么

拆开一份数据结构期末考试卷，你会发现它并不是把教材章节平均切一遍，而是沿着「存储结构 → 基本操作 → 典型算法 → 复杂度与正确性」这条线反复出题。判断分析题考的是概念边界，简答题考的是你能不能把结构讲清楚，应用分析题考的是手算过程，程序设计题考的是递归模型和链表指针操作。四类题型的难度是递进的，但底层知识点高度重合：图论、树与二叉树、查找、排序、存储结构选择。复习时如果只按章节翻书，很容易把「关键路径」和「最小生成树」混在一起，把「顺序查找成功 ASL」和「不成功 ASL」记反。更稳的做法是先画一张知识地图，把每个知识点挂到「它解决什么问题、手算步骤是什么、代码怎么写」三个钩子上，再逐块填细节。

2. 图论模块：关键路径、邻接表与最小生成树的复习重点

图论在这份卷子里占的分量不轻，判断题第一题就落在关键路径上，简答题第一题考邻接表的三连问，应用分析题第二题又要求手写 Prim 和 Kruskal 的执行过程。这三块看起来分散，其实共用同一个底层能力：你能不能把图的存储结构、遍历顺序和算法步骤对应起来。复习时不要一上来就背算法伪代码，先把「图怎么存」和「图怎么算」拆开，很多错误自然就暴露了。

2.1 关键路径：缩短活动时间不等于缩短工期

判断题里有一句「缩短关键路径上的某个活动时间，一定能缩短整个工程工期」，这句话是错的，而且错得很典型。关键路径是活动网络中最长的那条路径，它决定了工程的最短完成时间。但缩短关键路径上某个活动的时间之后，原来的关键路径可能不再是唯一的最长路径，另一条路径可能变成新的关键路径，工期并不会按你缩短的量线性减少。更严谨的说法是：只有缩短之后原关键路径仍然是最长路径，工期才会缩短；如果出现多条关键路径，必须同时缩短每条关键路径上的活动，否则工期不变。

手算关键路径的步骤可以固定成四步：先画 AOE 网，再算每个事件的最早发生时间 ve，然后倒推最迟发生时间 vl，最后用 e(i)=ve(j) 和 l(i)=vl(k)-weight 算活动的最早和最迟开始时间，差值等于零的活动就是关键活动。考试里最常见的失分点不是算错数，而是把「事件」和「活动」的时间混用，导致关键活动找错。复习时拿一张小图从头到尾算两遍，比看十遍定义有用。

注意：关键路径可能不止一条，题目如果没有特别说明，答「缩短某个关键活动时间一定能缩短工期」一律判错。

2.2 邻接表的三连问：边数、判断边、入度

简答题给了一个有向图 G={V,E}，顶点数为 n，存储结构是邻接表，问三件事：求边数的思路、判断顶点 i 和 j 是否有边、计算顶点 i 的入度。这三问其实是在考你对邻接表结构的理解程度。邻接表是「顶点数组 + 每个顶点挂一条边链表」，边链表里存的是该顶点的邻接点。

求边数：遍历所有顶点的边链表，统计边结点总数。有向图直接就是边数，无向图因为每条边在两个顶点的链表里各出现一次，所以要除以 2。判断 i 和 j 是否有边：遍历顶点 i 的边链表，看是否存在值为 j 的结点。计算顶点 i 的入度：邻接表只存出边，不能直接数 i 的链表长度，必须遍历所有顶点的边链表，统计指向 i 的边结点个数；如果题目允许，也可以维护一个逆邻接表，直接数 i 的逆邻接表长度。

这张表建议直接背下来，简答题按「思路 + 复杂度」两句话作答就能拿满。容易漏的是无向图边数要除以 2，以及入度不能直接数自己的链表——这两点几乎每年都有人踩。

2.3 Prim 与 Kruskal：两种最小生成树算法的执行过程

应用分析题给了一个带权无向图，要求以顶点 0 为起点分别写出 Prim 和 Kruskal 的执行过程。这两种算法目标相同，但贪心策略完全不同。Prim 是「从一个点开始，每次选连接已选集合和未选集合的最小边」，适合稠密图；Kruskal 是「把所有边按权值排序，每次选不构成回路的最小边」，适合稀疏图。

Prim 的手算过程建议写成表格：第一列是已选顶点集合，第二列是候选边（连接已选和未选的边），第三列是本次选中的边。每一步只加一个顶点，直到所有顶点入集合。Kruskal 的手算过程则是先排序边，再逐条判断「加入后是否成环」，不成环就选，成环就跳过，直到选够 n-1 条边。

# Prim 算法核心逻辑示意，不是完整可运行代码 def prim(graph, start): visited = {start} edges = [] # 存放候选边 (weight, u, v) while len(visited) < len(graph): # 把新加入顶点的所有出边放进候选堆 for v, w in graph[visited[-1]]: if v not in visited: edges.append((w, visited[-1], v)) edges.sort() # 选连接已选集合与未选集合的最小边 while edges: w, u, v = edges.pop(0) if v not in visited: visited.add(v) break return visited

上面这段代码只是帮你回忆 Prim 的「候选边 + 已选集合」结构，考试手算时不需要写代码，但理解这个循环能避免「选了一条两端都已访问的边」这种低级错误。Kruskal 的关键判断是并查集：每条边加入前检查两个端点是否已经在同一个集合里，如果在就跳过，不在就合并。手算时可以用「画圈标记连通分量」的方式代替并查集，速度更快。

提示：Prim 和 Kruskal 构造出的最小生成树权值相同，但树形可能不同，题目如果只要求「写出执行过程」，按步骤写边和顶点即可，不必纠结唯一性。

3. 树与二叉树：遍历还原、二叉排序树与平衡调整

二叉树是这份卷子里出现频率最高的结构：判断题考遍历还原，应用分析题考二叉排序树构造和 AVL 调整，程序设计题考度为 2 的结点计数。这几类题共用同一个基本功——递归地看树。复习时把「遍历序列互推」「二叉排序树插入」「四种旋转」当成三个独立技能练，每个技能都要求手写过程，不能只看懂。

3.1 由先序和中序推后序：根的位置决定一切

判断题给了一棵二叉树的中序 ABCDE 和先序 CABED，问后序是不是 BADCE。这类题的标准解法是：先序的第一个元素是根，拿着根去中序里切左右子树，然后递归处理。先序 C A B E D，根是 C；中序 A B C D E，C 左边是 AB，右边是 DE。左子树先序 AB、中序 AB，根是 A，A 没有左孩子，B 是 A 的右孩子。右子树先序 ED、中序 DE，根是 E，D 是 E 的左孩子。整棵树后序应该是 B A D E C，也就是 BADEC，题目给的 BADCE 是错的。

这个推导过程建议固定成三步：第一步标根，第二步切左右子树，第三步递归到空。手算时用草稿纸画树，画完再写后序，比直接在序列上推更稳。容易错的地方是「先序左子树的长度等于中序左子树的长度」这个对应关系，一旦切错长度，后面全错。

3.2 二叉排序树：插入路径与平均查找长度

应用分析题给先序序列 12,5,2,8,6,10,16,15,18,20，要求构造二叉排序树、写中序、算等概率下查找成功和不成功的平均查找长度。二叉排序树的插入规则很简单：比当前结点小往左走，大往右走，走到空位就挂上去。按这个规则构造出来的树，中序遍历一定是升序：2,5,6,8,10,12,15,16,18,20。

算 ASL 成功时，先标每个结点的层次：12 在第 1 层，5 和 16 在第 2 层，2、8、15、18 在第 3 层，6、10、20 在第 4 层。查找成功 ASL 等于所有结点查找长度之和除以结点数，也就是 (1+2+2+3+3+3+3+4+4+4)/10 = 2.9。算 ASL 不成功时，要补上外部空指针结点，每个空指针的查找长度等于它父结点的层次，再把所有空指针的查找长度求和除以空指针个数。这一步最容易漏的是「空指针个数等于结点数加一」，以及「空指针的查找长度按父结点层次算」这两条规则。

算完记得检查：成功 ASL 一定小于等于树高，不成功 ASL 一般比成功 ASL 略大，如果算出来明显偏离这个范围，大概率是层次标错了。

3.3 AVL 四种旋转：LL、RR、LR、RL 的判断与调整

应用分析题要求以 4,5,7,2,1,3,6 构造平衡二叉树，画出每次插入和调整过程，并指出调整类型。AVL 的调整类型只看「最小不平衡子树」的形态：从插入点往上找第一个失衡结点，看插入发生在它的左子树还是右子树，再看向左（或向右）走两步的方向。LL 型做右旋，RR 型做左旋，LR 型先左旋再右旋，RL 型先右旋再左旋。

以 4,5,7 为例：插入 4 和 5 后，5 是 4 的右孩子，仍然平衡；插入 7 后，4 的平衡因子变成 -2，失衡，插入发生在 4 的右子树的右子树，属于 RR 型，对 4 做一次左旋，5 成为根，4 变成 5 的左孩子，7 保持右孩子。后续插入 2、1 时会出现 LL 型，插入 3 时会出现 LR 型，插入 6 时会出现 RL 型。每一步都要画出调整前后的树形，并标注旋转类型，只写最终结果会丢过程分。

注意：AVL 调整的是「最小不平衡子树」，不是整棵树；旋转后要重新检查整棵树的平衡因子，不要只盯着局部。

3.4 二叉树度为 2 的结点计数：递归模型怎么写

程序设计题给二叉链表结构，要求求度为 2 的结点个数。递归模型可以这样设计：空树返回 0；叶子结点返回 0；如果当前结点同时有左孩子和右孩子，返回 1 加上左右子树的计数；如果只有一个孩子，返回左右子树计数之和，不加 1。写成代码就是：

typedef struct node { char data; struct node *lchild, *rchild; } BTNode; int CountDegree2(BTNode *b) { if (b == NULL) return 0; if (b->lchild != NULL && b->rchild != NULL) return 1 + CountDegree2(b->lchild) + CountDegree2(b->rchild); else return CountDegree2(b->lchild) + CountDegree2(b->rchild); }

这段代码的关键在第二个判断：只有左右孩子都不空时才加 1，否则直接递归左右子树。很多同学会写成「只要有一个孩子就加 1」，那是度为 1 的结点，不是度为 2。参数 b 是当前子树根指针，返回值是以 b 为根的子树中度为 2 的结点个数。递归出口是 b 为空，返回 0，不需要单独处理叶子，因为叶子会走 else 分支，左右子树都为空，返回 0+0。

4. 查找与排序：ASL、哈希表与二路归并

查找和排序在卷子里通常以计算题出现：判断题考顺序查找的 ASL，应用分析题考哈希表构造和二路归并的每一趟结果。这两块共同的要求是「过程可复现」，也就是你写出来的每一步，别人按同样的规则能算出同样的数。复习时不要只记公式，要把构造过程和查找长度的计算过程一起练。

4.1 顺序查找与哈希查找的 ASL 计算

判断题说「顺序查找算法的查找不成功的平均查找长度为 (n+1)/2」，这句话是错的。(n+1)/2 是查找成功且等概率时的 ASL，查找不成功时，如果顺序表没有哨兵，需要比较 n 次；如果有哨兵，需要比较 n+1 次。成功和不成功是两个不同的场景，公式不能混用。

哈希查找的 ASL 计算则依赖冲突处理方法。线性探查法下，查找成功的 ASL 等于每个关键字的探查次数之和除以关键字个数；查找不成功的 ASL 等于每个哈希地址探查到空位的次数之和除以哈希函数的值域大小。这两个分母不一样，是最容易出错的地方。

4.2 线性探查法构造哈希表：一步步填表

应用分析题给关键字 32,13,49,24,38,21,4,12，哈希函数 H(key)=key%7，地址空间 0 到 9，用线性探查法解决冲突。构造过程是：依次算哈希值，如果位置空就直接放，如果被占就往后找下一个空位。

32%7=4，放 4；13%7=6，放 6；49%7=0，放 0；24%7=3，放 3；38%7=3，冲突，往后找到 5，放 5；21%7=0，冲突，往后找到 1，放 1；4%7=4，冲突，4、5、6 都被占，放到 7；12%7=5，冲突，5、6、7 都被占，放到 8。最终表是：0 放 49，1 放 21，2 空，3 放 24，4 放 32，5 放 38，6 放 13，7 放 4，8 放 12，9 空。

查找成功 ASL：32 比较 1 次，13 比较 1 次，49 比较 1 次，24 比较 1 次，38 比较 2 次，21 比较 2 次，4 比较 4 次，12 比较 4 次，总次数 16，除以 8 得 2.0。查找不成功 ASL：对哈希值 0 到 6 分别数探查到空位的次数，0 地址探查 3 次到空位 2，1 地址探查 2 次，2 地址探查 1 次，3 地址探查 7 次到空位 9，4 地址探查 6 次，5 地址探查 5 次，6 地址探查 4 次，总次数 28，除以 7 得 4.0。注意不成功 ASL 的分母是哈希函数值域大小 7，不是地址空间大小 10。

提示：线性探查法构造哈希表时，地址空间通常比关键字个数大，题目如果说「0 到 9 的地址空间」，填表时不要越界，越界说明前面有步骤算错了。

4.3 二路归并排序：每一趟结果怎么写

应用分析题给整数序列 15,5,16,2,25,8,20,9,18,12，要求写二路归并排序每一趟的结果。归并排序是稳定排序，每一趟把相邻的两个有序段合并成一个有序段，段长从 1 开始翻倍。

第一趟：两两合并，[15,5] 变 [5,15]，[16,2] 变 [2,16]，[25,8] 变 [8,25]，[20,9] 变 [9,20]，[18,12] 变 [12,18]，结果是 5,15,2,16,8,25,9,20,12,18。第二趟：把相邻两个长度为 2 的有序段合并，[5,15] 和 [2,16] 变 [2,5,15,16]，[8,25] 和 [9,20] 变 [8,9,20,25]，[12,18] 单独保留，结果是 2,5,15,16,8,9,20,25,12,18。第三趟：把 [2,5,15,16] 和 [8,9,20,25] 合并成 [2,5,8,9,15,16,20,25]，[12,18] 保留。第四趟：合并成 2,5,8,9,12,15,16,18,20,25。

每一趟写完后检查两件事：段长是否按 1、2、4、8 翻倍，以及每个段内部是否有序。归并排序的常见错误是「把不相邻的段合并」或者「段长没有翻倍」，手算时用竖线把段隔开，能有效避免。

5. 易错点：五个最容易翻车的细节

复习到这一步，知识点已经铺开，但考试里真正拉开差距的往往是几个不起眼的细节。下面五条是从这份卷子里提炼出来的高频翻车点，每条按「易漏点 → 为什么漏 → 怎么补」写，建议对照自己的错题本逐条检查。

5.1 存储结构的分类不止三种

判断题说「数据结构的存储结构包括顺序存储、链式存储、哈希存储三种方式」，这句话漏了索引存储。数据结构的存储结构通常分四类：顺序存储、链式存储、索引存储、哈希存储。为什么容易漏？因为教材讲线性表时重点讲顺序和链式，讲查找时单独讲哈希，索引存储出现频率低，复习时容易被跳过。怎么补？把四种存储结构各配一个典型例子：顺序表、单链表、索引表、哈希表，记例子比记名词牢。

5.2 出栈序列的合法性不能靠感觉

判断题给进栈序列 1,2,3,4,5,6，问出栈序列 2,3,5,1,6,4 是否可能出现。判断方法是模拟栈：1 进，2 进 2 出，3 进 3 出，4 进 5 进 5 出，此时栈内是 1 和 4，栈顶是 4，下一个要出 1 就必须先出 4，所以这个序列不合法。为什么容易错？因为只看前几个数觉得「挺顺的」，没有完整模拟到冲突点。怎么补？每写一个出栈元素，就检查它是不是当前栈顶，不是就说明前面还有元素没出，序列非法。

5.3 顺序表删除函数的两个致命错误

简答题给了一个删除顺序表第一个元素的函数，函数体是for(i=1; i<L.length; i++) L.data[i-1]=L.data[i];，问错在哪。第一个错误是参数SqList L是值传递，函数内修改的是副本，原表不变；第二个错误是循环结束后没有L.length--，长度没有更新。为什么容易漏？因为平时写代码习惯用指针或引用，考试里看到值传递反而不敏感；长度更新则容易被「元素已经前移了」的错觉掩盖。怎么补？记住顺序表删除的三件套：判空、前移、长度减一，参数必须是指针或引用。

5.4 递归调用次数和递归深度不是一回事

简答题给递归函数fun(x,n)，问 fun(2,5) 的运算结果和执行过程中发生了多少次递归调用。函数功能是 x 的 n 次幂，fun(2,5)=32。递归调用次数包括初始调用在内是 5 次（fun(2,5)、fun(2,4)、fun(2,3)、fun(2,2)、fun(2,1)），如果题目问「递归调用」不含初始调用则是 4 次。为什么容易错？因为「调用次数」和「递归深度」两个说法在题目里经常混用，深度是 5 层，调用次数要看是否把最外层算进去。怎么补？答题时先写清楚「包括初始调用共 5 次，若不计初始调用则递归 4 次」，把两种口径都写上。

5.5 单链表删除最小值时漏删重复值

程序设计题要求删除带头结点单链表中结点值最小的所有结点，可能有多个最小值。常见错误是「找到第一个最小值就删掉然后返回」，漏掉后面同样是最小值的结点。正确做法是先遍历一遍找到最小值，再遍历一遍删除所有等于最小值的结点；或者一遍遍历记录最小值并删除，但删除时要注意前驱指针的更新。为什么容易漏？因为题目里「所有」两个字容易被忽略，看到「删除最小值」就默认只有一个。怎么补？读题时把「所有」「可能多个」圈出来，代码里用 while 循环而不是 if 判断。

6. 复习清单：考前一周怎么查漏补缺

最后一周不建议再从头翻教材，按「手算题 + 代码题 + 易错点」三条线走更有效。手算题每天挑两类，比如今天图论的关键路径和 Prim，明天二叉排序树和哈希表，每道题限时 15 分钟，写完对照步骤检查，重点看「中间过程有没有跳步」。代码题只练递归模型和链表指针操作，每道题先在纸上写递归出口和单层逻辑，再补代码，写完自己举一个空树、一个单结点、一个多结点的例子手动跑一遍。

查漏补缺的具体做法是：把最近三次练习里错过的题按知识点归类，如果同一个知识点错两次以上，就回到对应章节把定义和手算过程重新推一遍，不要只看答案。ASL 计算、AVL 旋转、哈希探查这三个点最容易反复错，建议单独抄在一张纸上，考前两天每天看一遍。另外，判断题不要只记「对错」，要能写出分析理由，因为卷子里的判断题本身就要求给理由，只写「错」拿不到全分。

我自己的习惯是考前三天把整份卷子的判断题重新做一遍，每道题在旁边写一句「考的是哪个知识点、为什么这么判」，写完再对照教材目录看有没有漏掉的章节。这个动作看起来笨，但能逼着我把「以为会了」和「真的会了」分开。从那以后我每次复习数据结构都强制走一遍「手算 + 代码 + 易错点」三线检查，翻车次数明显少了。希望这份梳理能帮到你。

本文还有配套的精品资源，点击获取