简介湖北大学数据结构期末试卷以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 四个题型的分值与能力映射卷面的分值结构是这样的题型题量单题分合计真正考的能力判断分析题5315概念边界识别 举反例简答题5525存储结构选型、算法分析应用分析题5840手算全过程的可复核性程序设计题21020递归建模、链表指针操作判断和简答合计 40 分全部是文字或口述型作答不需要写一行代码应用分析 40 分是纸笔推演程序设计 20 分才是编码。换句话说这张卷子里 80 分跟能不能写代码关系不大考的是你能不能把过程一步步摆出来让人复核。这个分布和多数院校数据结构 A 卷的取向是一致的手算题占比高是因为它能在一张纸上同时检验理解深度和表述完整度。按两小时的常规配速合理的分配是判断 10 分钟、简答 25 分钟、应用分析 55 分钟、程序设计 25 分钟剩下 5 分钟回头补判断分析题的理由。很多人栽就栽在判断分析题只写了个×——题干明写了判断下列描述是否正确并给出分析理由理由本身占分。2.2 从题干反推考点清单把 17 道小题逐条拆开能反推出一份相当完整的考点地图。这张表建议直接抄下来当复习目录用题号题干要点考点所属知识块一.1缩短关键路径上某活动时间是否一定能缩短工期AOE 网、多条关键路径图一.2顺序查找不成功 ASL 是否为 (n1)/2查找性能指标查找一.3进栈 16 时出栈序列 2,3,5,1,6,4 是否可能栈的出入序列合法性线性表一.4存储结构是否只有顺序、链式、哈希三种四种存储结构绪论一.5中序 ABCDE、先序 CABED 推后序遍历序列互推树二.1邻接表求边数、判边、求入度图的存储结构图二.2递归函数 fun(x,n) 的功能与调用次数递归模型分析栈与算法二.3三种结构中哪个最适合做链栈存储结构选型线性表二.4哪种矩阵压缩会失去随机存取特殊矩阵与稀疏矩阵数组二.5顺序表删除首元素函数的错误顺序表基本操作线性表三.1二路归并排序每一趟结果归并排序排序三.2Prim 与 Kruskal 的构造过程最小生成树图三.3由先序构造 BST、中序、ASL二叉排序树树三.4平衡二叉树的构建与旋转类型AVL 树树三.5线性探查法构造哈希表并求 ASL哈希表查找四.1求二叉树中度为 2 的结点个数递归遍历树与编程四.2删除单链表中值最小的所有结点链表双指针线性表与编程看这张表会发现一件事树和图各占了三到四道题加起来接近 60 分线性表虽然是基础但只在判断、简答和一道程序设计题里出现。复习优先级应该是树 → 图 → 哈希 → 线性表 → 排序。2.3 用这套卷子做全真自测的操作步骤拿这份卷子当模拟题光做一遍价值不大得按考场规则跑一遍才有意义。我一般会这么做打印或手抄一份空白卷把答案页隔开判断题不留任何标记。掐 120 分钟计时中途不查书、不看答案遇到卡壳的题在题号旁画个圈标记继续往下做。时间一到立刻停笔先不批改用另一种颜色把当时不确定但蒙对了的题也圈出来。按题型分段批改判断题只看理由里有没有命中采分点简答题按关键步骤给分应用分析题逐步对照过程对结果错只扣一半程序设计题用编译器跑一遍。统计三栏确定的错、蒙对的、完全没思路的。第三栏对应的知识块就是接下来三天的全部复习内容。这套流程跑两遍第二遍应该在 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]几个关键点第一趟合并长度是 11第二趟是 22第 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之间的所有边里挑权值最小的那条。答题时用三列表格最清楚步骤已选顶点集 U当前候选边连接 U 与 V-U选中的边与权值1{0}从 0 出发的所有边权值最小的那条2加入上一步选中的邻接点更新候选边集合再次取最小…直到 U 含全部 n 个顶点—共选 n-1 条边写 Prim 过程时有两个细节必须体现一是每步都要写出候选边集合是怎么更新的二是遇到权值相同的边时说明按顶点编号小者优先避免和标准答案对不上。用 lowcost 数组描述也行但表格更直观。Kruskal 是从边集里挑先把所有边按权值升序排列然后依次取边用并查集判断两端点是否已在同一连通分量里是则丢弃否则并入。步骤考察的边升序两端点所属集合是否成环动作1权值最小的边分属不同集合否加入2次小边分属不同集合否加入…某条边已在同一集合是丢弃直到选满 n-1 条边——结束两种算法写在同一道题里最好在最后加一句结论两种算法得到的最小生成树权值之和相同但选边顺序不同树形可能不同。这句话往往是这道 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 要看外部结点空指针共 n1 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。插入 54 的右孩子平衡因子正常。插入 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线性探查解决冲突地址空间 09。逐个算关键字H(key)探查过程最终地址比较次数3211 空111366 空614900 空012433 空313833 占探 4422100 占1 占2 空23444 占5 空521255 占6 占7 空73最终表0:491:322:213:244:385:46:137:128 空9 空。ASL成功 (11112323)/8 14/8 1.75。ASL失败要按散列函数的值域算H(key) key % 7 只可能落到 06 这 7 个地址所以分母是 7 而不是表长 10。对每个可能的散列地址从它出发一直探查到第一个空位为止探测次数计入起始地址探查路径探测次数00→1→2→3→4→5→6→7→8911→2→3→4→5→6→7→8822→3→4→5→6→7→8733→4→5→6→7→8644→5→6→7→8555→6→7→8466→7→83ASL失败 (9876543)/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(ne)。第三问的代码大概是这样/* 邻接表结构顶点数组 每个顶点挂一条出边链表 */ 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(ne)比邻接矩阵的 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)最后一次 n1 直接返回不再递归。加上最开始的那一次函数调用总共进入了 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根为 AB 是 A 的右孩子右子树的先序是 ED根为 ED 是 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本文还有配套的精品资源点击获取 
长河君 · 2026/10/27 3:13:34 · 阅读 1.2k 数据结构期末A卷四段式拆解与高频考点自测指南
简介湖北大学数据结构期末试卷以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 四个题型的分值与能力映射卷面的分值结构是这样的题型题量单题分合计真正考的能力判断分析题5315概念边界识别 举反例简答题5525存储结构选型、算法分析应用分析题5840手算全过程的可复核性程序设计题21020递归建模、链表指针操作判断和简答合计 40 分全部是文字或口述型作答不需要写一行代码应用分析 40 分是纸笔推演程序设计 20 分才是编码。换句话说这张卷子里 80 分跟能不能写代码关系不大考的是你能不能把过程一步步摆出来让人复核。这个分布和多数院校数据结构 A 卷的取向是一致的手算题占比高是因为它能在一张纸上同时检验理解深度和表述完整度。按两小时的常规配速合理的分配是判断 10 分钟、简答 25 分钟、应用分析 55 分钟、程序设计 25 分钟剩下 5 分钟回头补判断分析题的理由。很多人栽就栽在判断分析题只写了个×——题干明写了判断下列描述是否正确并给出分析理由理由本身占分。2.2 从题干反推考点清单把 17 道小题逐条拆开能反推出一份相当完整的考点地图。这张表建议直接抄下来当复习目录用题号题干要点考点所属知识块一.1缩短关键路径上某活动时间是否一定能缩短工期AOE 网、多条关键路径图一.2顺序查找不成功 ASL 是否为 (n1)/2查找性能指标查找一.3进栈 16 时出栈序列 2,3,5,1,6,4 是否可能栈的出入序列合法性线性表一.4存储结构是否只有顺序、链式、哈希三种四种存储结构绪论一.5中序 ABCDE、先序 CABED 推后序遍历序列互推树二.1邻接表求边数、判边、求入度图的存储结构图二.2递归函数 fun(x,n) 的功能与调用次数递归模型分析栈与算法二.3三种结构中哪个最适合做链栈存储结构选型线性表二.4哪种矩阵压缩会失去随机存取特殊矩阵与稀疏矩阵数组二.5顺序表删除首元素函数的错误顺序表基本操作线性表三.1二路归并排序每一趟结果归并排序排序三.2Prim 与 Kruskal 的构造过程最小生成树图三.3由先序构造 BST、中序、ASL二叉排序树树三.4平衡二叉树的构建与旋转类型AVL 树树三.5线性探查法构造哈希表并求 ASL哈希表查找四.1求二叉树中度为 2 的结点个数递归遍历树与编程四.2删除单链表中值最小的所有结点链表双指针线性表与编程看这张表会发现一件事树和图各占了三到四道题加起来接近 60 分线性表虽然是基础但只在判断、简答和一道程序设计题里出现。复习优先级应该是树 → 图 → 哈希 → 线性表 → 排序。2.3 用这套卷子做全真自测的操作步骤拿这份卷子当模拟题光做一遍价值不大得按考场规则跑一遍才有意义。我一般会这么做打印或手抄一份空白卷把答案页隔开判断题不留任何标记。掐 120 分钟计时中途不查书、不看答案遇到卡壳的题在题号旁画个圈标记继续往下做。时间一到立刻停笔先不批改用另一种颜色把当时不确定但蒙对了的题也圈出来。按题型分段批改判断题只看理由里有没有命中采分点简答题按关键步骤给分应用分析题逐步对照过程对结果错只扣一半程序设计题用编译器跑一遍。统计三栏确定的错、蒙对的、完全没思路的。第三栏对应的知识块就是接下来三天的全部复习内容。这套流程跑两遍第二遍应该在 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]几个关键点第一趟合并长度是 11第二趟是 22第 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之间的所有边里挑权值最小的那条。答题时用三列表格最清楚步骤已选顶点集 U当前候选边连接 U 与 V-U选中的边与权值1{0}从 0 出发的所有边权值最小的那条2加入上一步选中的邻接点更新候选边集合再次取最小…直到 U 含全部 n 个顶点—共选 n-1 条边写 Prim 过程时有两个细节必须体现一是每步都要写出候选边集合是怎么更新的二是遇到权值相同的边时说明按顶点编号小者优先避免和标准答案对不上。用 lowcost 数组描述也行但表格更直观。Kruskal 是从边集里挑先把所有边按权值升序排列然后依次取边用并查集判断两端点是否已在同一连通分量里是则丢弃否则并入。步骤考察的边升序两端点所属集合是否成环动作1权值最小的边分属不同集合否加入2次小边分属不同集合否加入…某条边已在同一集合是丢弃直到选满 n-1 条边——结束两种算法写在同一道题里最好在最后加一句结论两种算法得到的最小生成树权值之和相同但选边顺序不同树形可能不同。这句话往往是这道 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 要看外部结点空指针共 n1 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。插入 54 的右孩子平衡因子正常。插入 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线性探查解决冲突地址空间 09。逐个算关键字H(key)探查过程最终地址比较次数3211 空111366 空614900 空012433 空313833 占探 4422100 占1 占2 空23444 占5 空521255 占6 占7 空73最终表0:491:322:213:244:385:46:137:128 空9 空。ASL成功 (11112323)/8 14/8 1.75。ASL失败要按散列函数的值域算H(key) key % 7 只可能落到 06 这 7 个地址所以分母是 7 而不是表长 10。对每个可能的散列地址从它出发一直探查到第一个空位为止探测次数计入起始地址探查路径探测次数00→1→2→3→4→5→6→7→8911→2→3→4→5→6→7→8822→3→4→5→6→7→8733→4→5→6→7→8644→5→6→7→8555→6→7→8466→7→83ASL失败 (9876543)/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(ne)。第三问的代码大概是这样/* 邻接表结构顶点数组 每个顶点挂一条出边链表 */ 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(ne)比邻接矩阵的 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)最后一次 n1 直接返回不再递归。加上最开始的那一次函数调用总共进入了 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根为 AB 是 A 的右孩子右子树的先序是 ED根为 ED 是 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本文还有配套的精品资源点击获取