企业官网建设流程全解析

简介：湖北大学数据结构期末试卷以PDF形式收录2022—2023学年度第一学期数据结构A卷，面向计算机与信息安全相关专业学生，用于期末复习、自测与查漏补缺。试卷知识点覆盖图论、查找算法、二叉树遍历、递归函数和存储结构，题型包含判断分析、简答与应用计算；其中有向图邻接表、递归调用次数、链栈选择、二路归并排序、普里姆与克鲁斯卡尔算法、二叉排序树平均查找长度、平衡二叉树构建及哈希表线性探查等内容，能帮助读者按章节梳理概念、检验算法推演与综合解题能力。资源包共1个PDF文件，大小约252KB，便于打印和移动端查看，完整保留试题纸与分页结构。已有376人学习，适合需要系统复盘和考前训练的学生使用。

1. 拿到这份 A 卷先做什么：用 100 分四段式摸清自己的漏洞

期末前两周，我把一份数据结构期末试卷的 A 卷从头到尾掐表做了一遍：判断题打叉打得飞快，结果五道题只对了两道——关键路径那条想当然地判成"正确"，遍历序列还原那道算完没回头验算。后来对着答案复盘才发现，这份卷子把一学期的内容压成了四段式结构：判断分析 5 题 15 分、简答 5 题 25 分、应用分析 5 题 40 分、程序设计 2 题 20 分。前两段考概念的边界和反例能力，第三段是纯手算流程的完整度，第四段才落到真正的代码。它最适合两类人：正在准备期末、需要一个全真自测载体的人；以及工作几年后想把树、图、哈希这几块手算重新捡回来的从业者。

2. 试卷结构拆解：15/25/40/20 四个题型各自在考什么

一张卷子的分值分布，直接决定了复习时间的分配比例。很多人栽在这份卷子上不是因为不会写代码，而是把八成时间花在两道程序设计题上，结果 40 分的应用分析题因为手算步骤跳跃被扣得七零八落。先把四段式的结构看清楚，再决定每个知识块投入多少小时。

2.1 四个题型的分值与能力映射

卷面的分值结构是这样的：

判断和简答合计 40 分，全部是文字或口述型作答，不需要写一行代码；应用分析 40 分，是纸笔推演；程序设计 20 分才是编码。换句话说，这张卷子里 80 分跟"能不能写代码"关系不大，考的是你能不能把过程一步步摆出来让人复核。这个分布和多数院校数据结构 A 卷的取向是一致的：手算题占比高，是因为它能在一张纸上同时检验理解深度和表述完整度。

按两小时的常规配速，合理的分配是判断 10 分钟、简答 25 分钟、应用分析 55 分钟、程序设计 25 分钟，剩下 5 分钟回头补判断分析题的"理由"。很多人栽就栽在判断分析题只写了个"×"——题干明写了"判断下列描述是否正确，并给出分析理由"，理由本身占分。

2.2 从题干反推考点清单

把 17 道小题逐条拆开，能反推出一份相当完整的考点地图。这张表建议直接抄下来当复习目录用：

看这张表会发现一件事：树和图各占了三到四道题，加起来接近 60 分；线性表虽然是基础，但只在判断、简答和一道程序设计题里出现。复习优先级应该是：树 → 图 → 哈希 → 线性表 → 排序。

2.3 用这套卷子做全真自测的操作步骤

拿这份卷子当模拟题，光"做一遍"价值不大，得按考场规则跑一遍才有意义。我一般会这么做：

1. 打印或手抄一份空白卷，把答案页隔开，判断题不留任何标记。
2. 掐 120 分钟计时，中途不查书、不看答案，遇到卡壳的题在题号旁画个圈标记，继续往下做。
3. 时间一到立刻停笔，先不批改，用另一种颜色把"当时不确定但蒙对了"的题也圈出来。
4. 按题型分段批改：判断题只看理由里有没有命中采分点；简答题按关键步骤给分；应用分析题逐步对照，过程对结果错只扣一半；程序设计题用编译器跑一遍。
5. 统计三栏：确定的错、蒙对的、完全没思路的。第三栏对应的知识块就是接下来三天的全部复习内容。

这套流程跑两遍，第二遍应该在 90 分钟内完成且正确率有明显提升，否则说明第一遍的复盘没落到具体知识点上，只是把答案抄了一遍。

提示：批改应用分析题时，宁可对自己的步骤苛刻一点。考场上阅卷看的是过程，一个"显然可得"跳过的中间状态，很可能就是 2 分。

3. 应用分析五道大题：归并、最小生成树、BST、AVL、哈希的落笔顺序

这 40 分是最容易拿也最容易丢的一段。容易拿是因为全是机械流程，记住模板就不会错；容易丢是因为每道题都要写"每一趟""每一步",漏一趟就少一档分。下面按卷面顺序把这五道题拆开，每道都给到可以直接照抄的落笔格式。

3.1 二路归并排序：每一趟从哪儿算起

题目给的序列是 {15,5,16,2,25,8,20,9,18,12}，要求升序，写出每一趟归并后的结果。二路归并的第一趟是把每个单元素看成有序表，两两合并，所以第一趟的结果一定是"相邻两个数排好序"的形态，不可能是原序列。这一点每年都有人写错。

落笔格式这样写：

初始： [15] [5] [16] [2] [25] [8] [20] [9] [18] [12] 第1趟： [5,15] [2,16] [8,25] [9,20] [12,18] 第2趟： [2,5,15,16] [8,9,20,25] [12,18] 第3趟： [2,5,8,9,15,16,20,25] [12,18] 第4趟： [2,5,8,9,12,15,16,18,20,25]

几个关键点：第一趟合并长度是 1+1，第二趟是 2+2，第 k 趟的合并段长度是 2^(k-1)。10 个元素，趟数是 ⌈log₂10⌉ = 4 趟，最后一趟因为右段只有 2 个元素，直接整体并入。写的时候把每趟的方括号画清楚，比连成一长串数字更容易让阅卷看出你确实按段合并了。

有人习惯把"初始序列"也算作第 0 趟，然后第 1 趟直接写 [5,15][2,16]…，这没错，但要和题目的问法对齐——题目问"每一趟排序后的结果"，第 0 趟不算排序后。稳妥的做法是开头标一行"初始"，再从第 1 趟开始编号，两边都不吃亏。

3.2 Prim 与 Kruskal：同一张图的两种走法

第二大题给了一张带权无向图，以顶点 0 为起点构造最小生成树，要求分别写出 Prim 和 Kruskal 的执行过程。这类题的图在纸质卷上是示意图，转录成电子版后边权很容易糊在一起，所以这里只讲流程模板，具体权值以你手上那张卷面为准。

Prim 的本质是"从一个点长出一棵树"，每一步都从"已选顶点集 U"和"未选顶点集 V-U"之间的所有边里挑权值最小的那条。答题时用三列表格最清楚：

写 Prim 过程时有两个细节必须体现：一是每步都要写出"候选边集合是怎么更新的"，二是遇到权值相同的边时说明按顶点编号小者优先，避免和标准答案对不上。用 lowcost 数组描述也行，但表格更直观。

Kruskal 是"从边集里挑"，先把所有边按权值升序排列，然后依次取边，用并查集判断两端点是否已在同一连通分量里，是则丢弃，否则并入。

两种算法写在同一道题里，最好在最后加一句结论："两种算法得到的最小生成树权值之和相同，但选边顺序不同，树形可能不同。"这句话往往是这道 8 分题的最后一个采分点。

3.3 二叉排序树：由先序序列反推树形

第三题给的是先序序列 (12,5,2,8,6,10,16,15,18,20)，要求构造二叉排序树、写中序、求平均查找长度。这里的陷阱在于：它给的不是"插入序列"，而是"先序序列"。虽然对 BST 来说，先序序列恰好等于按该顺序逐个插入得到的树形，但你要在答卷上说明这一点，否则步骤分会被扣。

构造逻辑：先序第一个元素 12 是根；剩下的序列里，比 12 小的 (5,2,8,6,10) 全部落在左子树，比 12 大的 (16,15,18,20) 落在右子树；递归处理。结果如下：

12 / \ 5 16 / \ / \ 2 8 15 18 / \ \ 6 10 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×1 + 2×2 + 4×3 + 3×4) / 10 = 29/10 = 2.9

查找失败的 ASL 要看外部结点（空指针），共 n+1 = 11 个，比较次数取它父结点所在的层数：父在层 3 的（2、15 各两个空，18 一个空）共 5 个，比较 3 次；父在层 4 的（6、10、20 各两个空）共 6 个，比较 4 次。

ASL失败 = (5×3 + 6×4) / 11 = 39/11 ≈ 3.55

注意，不同教材对"失败时比较次数"的口径有差异，有的把落在空指针那一步也算一次比较，结果会整体加 1。答题前翻一下任课教材的例题，按它的口径写，别自作主张。

3.4 AVL 的插入与旋转判定

第四题的插入序列是 {4,5,7,2,1,3,6}，要求写出构建过程、画出每次调整后的结果并指出旋转类型。这道题设计得很巧——四种旋转类型它全考了一遍，一个都没落下。

过程如下：

• 插入 4：树为单结点 4。
• 插入 5：4 的右孩子，平衡因子正常。
• 插入 7：路径 4→右→右，失衡点在 4，属 RR 型，对 4 做一次左旋。得到根 5，左 4，右 7。
• 插入 2：挂在 4 的左边，仍平衡。
• 插入 1：路径 4→左→左，失衡点在 4，属 LL 型，对 4 做一次右旋。得到 5(2(1,4),7)。
• 插入 3：挂在 4 的左边，此时 5 的左子树高度 3、右子树高度 1，失衡点在 5，路径是"左孩子的右子树"，属 LR 型。先对 2 左旋，再对 5 右旋。
• 插入 6：挂在 7 的左边，此时 5 的右子树高度 3、左子树高度 1，失衡点在 5，路径是"右孩子的左子树"，属 RL 型。先对 7 右旋，再对 5 左旋。

最终形态：

4 / \ 2 6 / \ / \ 1 3 5 7

判型的口诀是"看失衡结点到新插入结点的路径前两步"：左左→LL 右旋，右右→RR 左旋，左右→LR 先左后右，右左→RL 先右后左。很多人翻车是因为只看插入位置相对失衡结点的方向，没看完整路径，把 LR 当成 LL 处理，旋转一次之后树还是不平衡。

3.5 线性探查哈希表：装表与失败 ASL

第五题：关键字 {32,13,49,24,38,21,4,12}，H(key) = key % 7，线性探查解决冲突，地址空间 0～9。逐个算：

最终表：0:49，1:32，2:21，3:24，4:38，5:4，6:13，7:12，8 空，9 空。

ASL成功 = (1+1+1+1+2+3+2+3)/8 = 14/8 = 1.75。

ASL失败要按散列函数的值域算，H(key) = key % 7 只可能落到 0～6 这 7 个地址，所以分母是 7 而不是表长 10。对每个可能的散列地址，从它出发一直探查到第一个空位为止，探测次数计入：

ASL失败 = (9+8+7+6+5+4+3)/7 = 42/7 = 6。

这个值偏大，原因是装填因子 8/10 = 0.8 已经很高，线性探查又容易产生堆积。写答案时把这张探查表画出来，比只写一个 6 有说服力得多。

4. 判断与简答：七个高频考点的答题模板

40 分的判断题和简答题，全部是文字作答。它们看着简单，实际上区分度很高——会的人三句话说完，不会的人写满半页也没踩到点上。这一章按"问什么、答什么、坑在哪"的方式把七个考点过一遍。

4.1 邻接表三问：边数、判边、入度

简答题第一问给了一个 n 个顶点、用邻接表存储的有向图，问三件事：怎么求边数、怎么判断顶点 i 和 j 之间有没有边、怎么求顶点 i 的入度。这三问分别对应邻接表的三种遍历方式。

求边数：遍历顶点数组，对每个顶点统计它后面挂的边结点个数，全部累加。对无向图要注意同一条边在两端各存了一次，累加后要除以 2。判边 i→j：在顶点 i 的邻接表里顺序查找，看有没有值为 j 的边结点，时间复杂度是 O(出度(i))。求入度：邻接表只存出边，所以要遍历所有顶点的链表，统计指向 i 的结点个数，复杂度 O(n+e)。

第三问的代码大概是这样：

/* 邻接表结构：顶点数组 + 每个顶点挂一条出边链表 */ int InDegree(ALGraph *G, int i) { int cnt = 0, k; EdgeNode *p; for (k = 0; k < G->n; k++) { /* 遍历全部顶点 */ for (p = G->adjList[k].first; p != NULL; p = p->next) { if (p->adjvex == i) /* 有弧 k -> i，贡献一次入度 */ cnt++; } } return cnt; }

这段代码的要点是把"入度"翻译成"有多少条弧指向 i"，然后在外层套一遍所有顶点的出边链表。代价是 O(n+e)，比邻接矩阵的 O(n) 慢，但邻接表本来就省空间，这是典型的空间换时间。如果图经常需要求入度，另一种做法是额外建一张逆邻接表，把每条弧按"终点"挂链，查询就降到 O(入度(i))。

答这道题时，三个小问分开写、每问先给一句话结论再给理由，比连成一段更容易得分。

4.2 递归函数的三个追问

第二题给了一段函数：

double fun(double x, int n) { if (n == 1) return x; return x * fun(x, n - 1); }

三个小问：功能是什么、fun(2,5) 的结果和执行过程中发生了几次递归调用、最多发生几次递归调用。

功能：计算 x 的 n 次幂。第一问要写全，别只写"求幂"，最好补一句"当 n 为正整数时返回 xⁿ"。

fun(2,5)：2⁵ = 32。递归调用次数是 4 次——fun(2,5) 内部调 fun(2,4)，再到 fun(2,3)、fun(2,2)、fun(2,1)，最后一次 n==1 直接返回，不再递归。加上最开始的那一次函数调用，总共进入了 5 次函数体。题目问"递归调用"就答 4，问"函数调用"就答 5，两个概念别混。

最多调用次数：n 每递归一次减 1，从 n 减到 1 需要 n-1 次递归调用，所以最多 n-1 次，空间上对应 n 层调用栈，空间复杂度 O(n)。

这道题还埋了个可以延伸讨论的点：如果传入 n = 0 会怎样？由于没有 n == 0 的出口，函数会一直递归下去直到栈溢出。答完三问后补一句"该函数缺少 n ≤ 0 的边界处理"，往往能多拿一点印象分。

4.3 链栈选型与稀疏矩阵的随机存取

第三问给了三种结构：带头结点的单链表、不带头结点的循环单链表、带头结点的双链表，问哪个最适合做链栈。

答案是带头结点的单链表。理由要写三层：栈的插入删除只在栈顶一处发生，把表头当栈顶，进栈出栈都是 O(1)，不需要遍历；带头结点让空栈和非空栈的操作统一，省掉判空的特判分支；双链表多一个前驱指针，栈用不上，白费空间；循环单链表的价值在于尾到头能绕回去，栈也不需要。

第四问：特殊矩阵和稀疏矩阵两种压缩方法，哪一种失去随机存取功能。答案是稀疏矩阵的三元组顺序表。原因是特殊矩阵（对称矩阵、三角矩阵、带状矩阵）的非零元位置有规律，压缩后依然可以用下标换算公式直接算出存储位置，比如对称矩阵的 a[i][j] 和 a[j][i] 共享一个单元，公式一算就到。稀疏矩阵的非零元分布没有规律，只能把 (行号, 列号, 值) 三元组按行优先排成一串，要访问某个位置的元素必须从头扫描三元组表比对行列号，随机存取就没了。

这一问容易答成"稀疏矩阵"，但漏掉"三元组顺序表"这个限定。如果稀疏矩阵用十字链表存，丢失的其实不只是随机存取，连顺序访问的局部性也没了。所以答案落到具体存储表示上更稳。

4.4 出栈序列判定与遍历序列还原

判断题第三问：进栈序列 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，但栈顶是 4，卡住了。所以这个序列不可能。更简明的反证：1 要出栈，前提是它上面的元素全部弹出，也就是 4 必须先出栈，可 4 排在序列最后，矛盾。

第五问：中序 ABCDE、先序 CABED，问后序是不是 BADCE。按先序定根、中序分左右的方法走一遍：先序首元素 C 是根；中序里 C 左边 AB 是左子树、右边 DE 是右子树；左子树的先序是 AB，根为 A，B 是 A 的右孩子；右子树的先序是 ED，根为 E，D 是 E 的左孩子。后序按"左、右、根"读出来是 B、A、D、E、C，即 BADEC，不是题干给的 BADCE。所以判断为错误。

这类题的检查手段只有一个：算完之后用后序 + 中序反推先序，看能不能还原出题干给的那串。能还原就说明你的树是对的。

4.5 顺序表删除函数的四处错误

第五问给了一段删除顺序表首元素的代码，要求指出错误：

void del(SqList L) { int i; for (i = 1; i < L.length; i++) L.data[i - 1] = L.data[i]; }

第一处也是最致命的：参数 L 是值传递，函数收到的是实参的一份拷贝。函数体里对 L.length 的任何修改都不会传回调用方，即使补上 L.length-- 也没用。正确写法是传指针void del(SqList *L)或 C++ 引用void del(SqList &L)。

第二处：函数里根本没有更新表长。元素虽然整体前移了一位，但 length

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