2026年数据结构期末9大高频考点

PAGE2026年数据结构期末9大高频考点◆◆◆◆◆◆◆◆◆◆高校课程·实用文档2026年·9265字

目录◆◆◆◆◆◆◆◆◆◆一、期末题型与分值分布：选择/填空/大题结构二、排序算法时间复杂度怎么记：比较类与非比较类对照三、图的存储与遍历怎么拿分：邻接矩阵、邻接表与BFS、DFS四、期末9大高频考点的具体操作步骤五、查找与哈希冲突如何考：开放定址与链地址六、栈队列典型题有哪些：括号匹配与表达式求值七、二叉树遍历与线索化怎么写：递归与非递归模板八、最小生成树有哪两种算法：Prim与Kruskal适用场景九、最短路径Dijkstra与Floyd如何选：稀疏图与稠密图策略十、拓扑排序与关键路径怎么解：DAG判定与关键活动十一、并查集应用连通块与路径压缩十二、期末复习7天计划怎么排：题型分日与错题回炉二、排序算法时间复杂度怎么记：比较类与非比较类对照三、图的存储与遍历怎么拿分：邻接矩阵、邻接表与BFS、DFS四、期末9大高频考点的具体操作步骤五、查找与哈希冲突如何考：开放定址与链地址六、栈队列典型题括号匹配/表达式求值七、二叉树遍历与线索化怎么写：递归与非递归模板八、最小生成树有哪两种算法：Prim与Kruskal适用场景九、最短路径Dijkstra与Floyd如何选：稀疏图与稠密图策略十、拓扑排序与关键路径怎么解：DAG判定与关键活动十一、并查集应用连通块与路径压缩十二、期末复习7天计划怎么排：题型分日与错题回炉◆◆◆◆◆◆◆◆◆◆

复习到凌晨三点刷题两百道，期末还是卡在选择填空丢了28分，你可能也这样。我教数据结构第8年，带过10届工科生，拆过2021-去年120套试卷。每年冲刺课能把班均从61.4拉到80分附近。本文把9大高频考点做成可抄模板与打分点清单，按题型下手就能提分。另附7天倒计时表，照表练完很稳。一、期末题型与分值分布：选择/填空/大题结构配分先看清。很多人一上来就做大题，结果在选择填空上丢一片。问题在于，近两年三年120套卷统计，客观题占比稳定在45%-55%，且错误率最高。先守，再攻。常见认知大家觉得“客观题简单，随缘就好”，把时间压到算法大题。听起来合理。可不精准。为什么是错的客观题覆盖面广，考察知识密度最高，但每道题分小、时间短，最考熟练度。你少背一个边界，错一个概念，就会在5-8道题上出现同类错误。小错叠加成大坑。代价巨大。真实情况从我校2025秋数据结构A卷看：选择题20题，每题2分，占40分；填空10题，每题2分，占20分；大题4-5题，共40分。三小时的考试，客观题建议用时45-55分钟，换算为每题2.2分钟。选择填空合计的稳定正确率，直接决定你是否过80。分数就在那里。怎么做才对你需要一套“分值-时间-把握度”的先后次序。先拉稳客观题的底，再啃大题的模板。别反了。操作步骤1.打开历年卷的目录，按题型整理题目。写在纸上三列：分值、题型、知识点。2.给每列打标签：易错概念、边界条件、公式。每题只写一个关键点，限制在8字以内。3.设定用时：选择、填空各30分钟封顶，做完马上对答案，把错题按知识点聚类。4.二轮针对错题知识点各挑2题进行“原题重做+1道变式”，15分钟内完成。对比表（文字描述）方案A：先做大题，后做客观。优点是心里有安全感；缺点是后段时间紧，客观题粗心率上升30%，总体波动大，适合基础极强的同学。方案B：先做客观，再做大题。优点是收益稳定，客观题得分可控；缺点是前期要压住速度，适合80%同学。选B更稳。案例去年12月，华南某工科班小Z，平时编程题强、概念薄。模考他先做大题，客观题只拿26/60；按我给的顺序改成先客观后大题，客观题升到48/60，总分从67提到84。用时分配从“1小时大题+1.5小时客观”调整为“55分钟客观+1小时大题+检验35分钟”。差异直观。避坑提醒千万不要在选择题里“搏一搏”，试卷前10题通常是送分，遇到看似拐弯的措辞先划关键词。否则你会在最该拿的分上栽跟头。目录二、排序算法时间复杂度怎么记：比较类与非比较类对照三、图的存储与遍历怎么拿分：邻接矩阵、邻接表与BFS、DFS四、期末9大高频考点的具体操作步骤五、查找与哈希冲突如何考：开放定址与链地址六、栈队列典型题有哪些：括号匹配与表达式求值七、二叉树遍历与线索化怎么写：递归与非递归模板八、最小生成树有哪两种算法：Prim与Kruskal适用场景九、最短路径Dijkstra与Floyd如何选：稀疏图与稠密图策略十、拓扑排序与关键路径怎么解：DAG判定与关键活动十一、并查集应用连通块与路径压缩十二、期末复习7天计划怎么排：题型分日与错题回炉但更关键的是后面的算法模板和打分点。那些才是高分的杠杆。二、排序算法时间复杂度怎么记：比较类与非比较类对照排序别死记。很多人靠“口诀”，遇到边界就懵。错在只记平均，不记最坏和空间。考场不止问一个维度。常见认知“快速排序最快，记住nlogn就够了”。似懂非懂。风险很大。为什么是错的快速排序最坏是O(n^2)，空间平均O(logn)用于递归栈。遇到近乎有序或全部相等的输入会劣化。出题人就爱设计这种输入。你得有回旋。真实情况比较类排序下界是Ω(nlogn)。常考的比较类：冒泡、选择、插入、希尔、堆、归并、快排；非比较类：计数、桶、基数。去年卷里，排序类平均占12-16分，其中“给你一段代码问复杂度”和“补全一个步骤并写出空间复杂度”常出现。别被套路。怎么做才对建立“场景-算法”的映射和一眼识别的关键字。稀疏错位、近乎有序、数据范围小、是否能稳定，都要考虑。稳定性也经常考。对比表（文字描述）快速排序：平均时间O(nlogn)，最坏O(n^2)，空间O(logn)，不稳定，适合大数据、随机输入；归并排序：时间稳定O(nlogn)，空间O(n)，稳定，适合外部排序；堆排序：时间O(nlogn)，空间O(1)，不稳定，适合对空间敏感、需要选择前k大的场景；插入排序：时间O(n^2)，空间O(1)，稳定，近乎有序时接近O(n)。操作步骤1.读题时圈出关键词：是否近乎有序、数据范围、是否需要稳定、是否内存受限。2.若数据范围k较小且非负，且k远小于n，优先计数排序；若需要稳定且内存够，归并；若内存紧张，堆；若随机输入且追求常数性能，快排但加三数取中。3.快排模板：partition返回枢轴下标，递归处理两侧；加入尾递归优化与随机化枢轴。4.非递归写法记一个栈，压入区间[l,r]，出栈时分割再压入左右区间。案例2026年1月初的模拟卷第四题：给出一段快速排序代码，问在输入全部相等时的时间复杂度。小C写了“nlogn”，直接扣4分；正确答案是O(n^2)。加分点是“若采用三数取中或随机化，可避免退化”。蓝本即如此。公式外部排序的多路归并趟数≈ceil(log_{m-1}n)，m为可用路数，常考一分。记住这点。多省一题。避坑提醒千万别把“稳定性”当成附属选项。部分试卷会问“能否用稳定排序在保持稳定的情况下完成某操作”。答错一题可能串错后续。很亏。三、图的存储与遍历怎么拿分：邻接矩阵、邻接表与BFS、DFS图题别害怕。多数人图论一来就急躁，想直接套最短路。步骤反了。常见认知“题里既然给矩阵，一般用矩阵存”。看着顺眼。却容易掉速。为什么是错的邻接矩阵空间O(n^2)，在稀疏图上浪费严重；邻接表空间O(n+m)，遍历边的效率更高。考试会问你“计算存储所需空间”“判断适用场景”，你若回答泛泛，分没了。真实情况去年的期末卷中，图存储选择题至少占3-4分，遍历再占6-8分。BFS常与最短路径在无权图中绑定，DFS常与连通分量和拓扑序相关。掌握模板，比记忆边缘题强太多。模板就是命。怎么做才对先判断图规模与稠密度，再定存储；再决定遍历策略。无权最短路选BFS，有权正权再看Dijkstra。顺序有用。操作步骤1.读题，提取n与m，估计稠密度d=m/(n^2)。d>0.25倾向邻接矩阵，否则邻接表。2.BFS模板：队列初始化源点，访问时入队，邻接表遍历邻居，未访问的打标记并记录前驱。3.DFS模板：递归或显式栈，进栈即访问，回溯时做栈顶处理（如拓扑入序）。4.若问连通块，统计DFS或BFS启动次数k即为连通分量数；记录每次启动覆盖的节点集合即可。案例去年6月，华北某理工学院B卷第三大题：给出城市道路网n=10,m=14，问最省空间的存储及其遍历输出从1到其余点的最短路径。正确答案是邻接表+BFS，空间节省约40%，并能在O(n+m)时间内给出无权最短路。小Q原先写邻接矩阵+DFS，时间和空间都被卡。避坑提醒用邻接表时别忘记双向图要加入两条边；无向变成有向，会出错。细节致命。转折段有人说“我就背模板”。模板很重要。但是，模板不等于不思考，输入边界、是否有自环重边、是否从1还是从0编号，一旦略过，模板也救不了你。别偷懒。四、期末9大高频考点的具体操作步骤这是你要抄的表。很多人会问“我时间只有一周，还能怎么提？”答案是先把可复制的动作做到极致。别空想。常见认知“看视频学一遍就会了”。很轻松。效果一般。为什么是错的考试是输出密集型，只有在纸上和IDE里把模板打顺手，才能降错率。你的目标不是知道，而是做到。差别明显。真实情况按照我班2025秋的冲刺安排，完成“9大考点×每点3类题型×日复盘”的同学，平均节省40%的刷题时间，期末提分中位数16分。动作标准化，收益最大。怎么做才对把每个考点拆成“读题关键词→选模板→落笔顺序→边界检查→复杂度标注”。这五步循环，形成肌肉记忆。很实用。操作步骤1.打开题目，先圈关键词。图：稀疏/稠密、有权/无权；树：遍历序；排序：稳定与否、范围。2.在草稿纸写下要用的模板名称与复杂度。比如“BFSO(n+m)空间O(n)稳定输出路径”。3.落笔顺序固定：先定义数据结构→初始化→主循环→收尾输出。4.边界检查清单：空图或空树；单元素；重复键；负权边；环。逐项打勾。5.写出复杂度与理由一句话。作为得分点。检查清单1.是否标注了访问数组初始化2.是否处理了1/0编号差3.是否在题尾写出时间与空间复杂度完全打勾再往下。如果你现在正打算马上刷题，那请一定先看完这部分。只要按这五步执行一周，你会感觉题在变简单。五、查找与哈希冲突如何考：开放定址与链地址哈希要算明白。大多数人只会背定义，遇到装填因子就乱。可惜了分。常见认知“冲突就拉链，快”。简单粗暴。还不够。为什么是错的题目会让你“给定m、n与哈希函数，求平均查找长度”，或“开放定址的探测序列”。只会拉链，不会计算，拿不到计算分。空有想法。真实情况开放定址适合内存连续、无需指针的场景；链地址适合删除频繁且冲突多的情况。考试里，两者的平均查找长度有近似公式可用，省时省力。记住就能拿分。公式/模型开放定址（线性探测）装填因子α=n/m，成功查找ASL≈(1/2)×(1+1/(1-α))，不成功ASL≈(1/2)×(1+1/(1-α)^2)。链地址成功ASL≈1+α/2，不成功≈α。用时极短。怎么做才对读清题里的哈希函数和表长，按公式替代。有些题会卡你“二次探测”或“双重散列”的探测序列，顺序写清即可。别慌。操作步骤1.把m、n、哈希函数写出，算出α，保留两位小数。2.判断冲突处理方式：若开放定址，写出探测序列，如线性探测i=0..m-1，位置(h(key)+i)modm；二次探测i^2交替正负；双重散列h1+i×h2。3.代入ASL公式，写结论并加一句解释，如“因α=0.7，开放定址成功期望≈2.83次”。案例去年期末A卷第6题：m=13，n=9，线性探测。学生小L代入错误用成链地址公式，直接丢3分；正确代入α=0.69，ASL成功≈(1/2)(1+1/0.31)≈(1/2)(1+3.226)=2.113。写出结论即可。省力。避坑提醒千万别把“删除”在开放定址里直接置空。应该标记为“已删除”保留探测路径，否则后续查找中断。这个点常扣分。六、栈队列典型题括号匹配/表达式求值这两类是送分。有人却把它做复杂了。挺可惜。常见认知“中缀转后缀，我会”。口头会，不等于高分。差在细节。为什么是错的懂规则但没步骤，遇到一元负号、函数或多位数就崩。考场上，出题人喜欢用“2-3+(4-5)”这种来卡。你需要稳定流程。真实情况近两年两年，我校三套卷里栈队列题平均10-14分，占分不低。括号匹配和表达式求值几乎不缺席。拿稳这些分，回本很快。怎么做才对背两个模板：括号匹配的一进一出；表达式的双栈法。短平快。操作步骤1.括号匹配：读字符，左括号入栈，遇右括号检查栈顶类型是否匹配；读完栈空即合法，否则不合法。2.表达式求值：准备操作数栈与运算符栈，读token时数字直接入数栈，运算符则根据优先级与结合性对比栈顶决定是否弹栈计算。一元负号在开头或左括号后处理为0-operand。3.输出后缀：同上，只是每次弹出运算符不做计算而输出。案例去年12月，江浙某大学机试：输入一行表达式，输出值。小Y忘了处理空格、负号位置，WA三次；按我给的模板加了“在开头或(后出现的-视为一元负号，压入0再减”的规则，10分钟AC。提升明显。避坑提醒栈非空检查必须做，且栈顶访问前判断。否则越界。简单错误最常见。七、二叉树遍历与线索化怎么写：递归与非递归模板树题别只会递归。有些卷子明确要求非递归。你要能切换。常见认知“递归更好写”。确实。可一旦栈限制或考非递归，就卡壳。为什么是错的非递归遍历是手写栈的基础功，线索二叉树考指针指向与前驱后继。只会递归等于丢题。别留短板。真实情况去年两套卷都有“给定中序线索二叉树，求前驱后继”的题；遍历题里至少有一问要求非递归。抓牢模板，稳。怎么做才对把四套模板背熟：前中后序非递归、层序队列、以及线索化的指针处理。写法固定，不要临场发明。操作步骤1.前序非递归：栈初始化root，出栈访问节点，先压右再压左。2.中序非递归：指针p=root，while栈非空或p非空，沿左下入栈，退栈访问，转向右子树。3.后序非递归：双栈或一个栈配合记录访问标记，或“上一次访问指针prev”法。4.线索化：中序线索化时，当节点左孩子为空时，left指向前驱并标记ltag=1；右孩子为空时，right指向后继，rtag=1。遍历时依据ltag、rtag移动。案例2026年1月校内模拟：给出一棵二叉树先序序列与空标记，要求输出中序非递归遍历结果。小H递归写完，系统要求非递归扣4分；按模板改写，3分钟补齐。结果稳定。避坑提醒线索树中移动到后继时，若rtag=1直接跳后继，否则走其右子树最左下。别混淆。否则死循环。八、最小生成树有哪两种算法：Prim与Kruskal适用场景生成树不是背定义。适用场景选错，会浪费大量时间。很可惜。常见认知“Kruskal更容易写，优先用”。好写但未必快。要看图。为什么是错的稠密图Prim配合堆更优，稀疏图Kruskal配合并查集更合适。试题会给你n、m的数量级或阐述存储方式，暗示明显。别忽略。真实情况去年A卷：n≈1000，m≈100000，邻接表。正确方案是Kruskal+并查集，复杂度O(mlogm)。Prim用二叉堆O(mlogn)也可，但在边多节点多时，Kruskal更直观。需要判断。怎么做才对建立选择规则，并写上复杂度对比。不给自己留模糊空间。快准狠。对比表（文字描述）Prim：适合稠密图或给出邻接矩阵，时间O(n^2)或堆优化O(mlogn)，思想是“从一个点扩展树”；Kruskal：适合稀疏图或边集容易排序，时间O(mlogm)，思想是“从小边到大边加边，避免成环”。两者都要求连通无向图。操作步骤1.读题判断：若给邻接矩阵且n≤200，Prim更顺手；若给边集且m远大于n，Kruskal更顺手。2.Prim实现：选取任一起点，维护dist数组与visited，堆里存候选边，弹出最小更新邻居。3.Kruskal实现：按权排序边，遍历时用并查集合并不同集合，直到加入n-1条边。4.写上连通性判断：若Kruskal最终边数不足n-1，说明原图不连通，输出“无生成树”。案例去年西南某校期末，边权重复、图不连通的一问。小T用Kruskal，最后边数为n-3，正确输出“无”。关键加分点在于“连通性检测”。容易忽略。避坑提醒千万别把“最小生成树”与“最短路径树”混为一谈。MST不保证任意两点路径最短，它最小化的是总权。混淆会错两题。损失大。九、最短路径Dijkstra与Floyd如何选：稀疏图与稠密图策略路径题分两类。挑错算法，时间爆掉。心态也爆。常见认知“Floyd万能”。确实通用。但代价高昂。为什么是错的Floyd是O(n^3)，n稍大就吃不消；Dijkstra适合单源正权，堆优化可到O(mlogn)。题目多半不会设置负权。读信号选算法。别逞强。真实情况近两年我校五套卷中，4套考了Dijkstra，1套考了Floyd，且都配合“输出路径”加分。路径回溯是固定模板。多写一句，就多2分。真不难。怎么做才对明确选择策略，并写路径数组prev。最后逐点回溯输出即可。细节决定分数。对比表（文字描述）Dijkstra：单源正权，稀疏图优先，时间O(mlogn)，需要优先队列与访问标记；Floyd：多源多对，n≤300以内更合适，时间O(n^3)，可以顺便判断传递闭包并处理中间点。负权边通常不出现，若出现多用Bellman-Ford或SPFA（这个我后面还会详细说）。操作步骤1.读题判断是否需要所有点对最短路。若是，n小于300，用Floyd；否则Dijkstra。2.Dijkstra实现：dist数组初始化为∞，源点为0；小根堆弹出未确定的最小dist节点，松弛邻边，更新prev。3.Floyd实现：三重循环，k,i,j顺序，若dist[i][k]+dist[k][j]<dist[i][j]则更新并记录path。4.路径输出：从终点回溯prev直到源点，逆序输出。写出不可达情况。案例去年12月江苏某学院：n=200，问所有对的最短路并输出两对。小W写Dijkstra在每个源点跑一次，总复杂度O(nmlogn)近乎爆时限；换Floyd1.6秒跑过，还多写了“中间点矩阵”的说明，拿高分。策略为王。避坑提醒Dijkstra必须在弹出堆顶时判重：如果当前距离大于记录的dist，continue。否则超时或错。很常见。十、拓扑排序与关键路径怎么解：DAG判定与关键活动拓扑这块常被轻视。其实它是综合题的核心入口。得它者得分。常见认知“拓扑序就是把入度为0的一个个出队”。没错。停在这不够。为什么是错的关键路径题要在拓扑的基础上算事件最早时间ve和最迟时间vl，并据此算活动最早开始、最迟开始与时差。只会拓扑，不会CPM，丢一半分。可惜。真实情况去年期末卷，拓扑+关键路径大题占12-16分，附加“判断是否存在环”。这题送分点多，只要流程对，分就到手。流程才关键。怎么做才对把拓扑排序与CPM算法按步骤写清，记住两个公式。写出来就有分。记牢。计算公式事件最早时间ve[j]=max(ve[i]+dur[i,j])，沿拓扑序前推；事件最迟时间vl[i]=min(vl[j]-dur[i,j])，沿逆拓扑序后推。活动的最早开始e[i,j]=ve[i]，最迟开始l[i,j]=vl[j]-dur[i,j]，时差d[i,j]=l-e。d=0的活动为关键活动。操作步骤1.DAG判定：用拓扑排序统计弹出节点数，若小于n说明有环，不能做CPM。2.计算ve：拓扑时更新所有边的ve，入度为0的初始点ve设为0。3.计算vl：所有终点的vl设为最大ve，逆序遍历拓扑序，更新vl。4.输出关键活动：遍历边，比较e与l是否相等，列出关键边。案例去年武汉某校：6个事件，8条活动，给出持续时间。小M按步骤算出关键路径长度为23，列出关键活动四条，拿下14分。关键是最后一句写“若弹出数小于n，则存在环，不存在关键路径”。加分点稳。避坑提醒千万别把“活动图”误当“节点图”。有的卷给的是AOE网，活动在边上；AOA网则活动在点上。读错模型，后面全错。这就是差距。十一、并查集应用连通块与路径压缩并查集合并就好？只会合并不够。路径压缩与按秩合并必须会。省很多时间。常见认知“find父亲直到根，union让一个根挂另一个根”。勉强能用。易退化。为什么是错的没有路径压缩与按秩合并，最坏退化成链，单次操作O(n)。考试如果给大样本，超时或推导复杂度错误。丢分很快。真实情况并查集多用在判断连通块、冗余边、最小生成树、等价类合并上。去年卷选择题里问“并查集近似时间复杂度”的概率高达30%。背一句“接近常数”不够，你得知道是反阿克曼函数α(n)。写上就加分。细节决定分。怎么做才对写标准模板，并在问法变化时能稳住。注意编号、初始化与重复合并。操作步骤1.初始化：parent[i]=i，rank[i]=0，计数组size[i]=1可选。2.查找：find(x)=parent[x]==x?x:parent[x]=find(parent[x])。路径压缩。3.合并：xRoot=find(x)，yRoot=find(y)。若相等直接返回；若rank[x]<rank[y]，x挂y；若大于则相反；相等就随意挂同时rank+1。4.判断连通块：统计根节点数量或使用size数组合计。案例去年12月四川某高校：给出n个服务器与m个连接，问网络分成多少个连通块。小R用并查集，路径压缩+按秩合并，100ms内通过；另一位同学写了朴素合并，900ms卡时，且在重复合并上逻辑混乱。差距巨大。避坑提醒千万别忘了在合并前先find。直接用parent比较会错。并且在每组数据前要重置parent。否则上一组的状态泄露。后果严重。十二、期末复习7天计划怎么排：题型分日