资讯 / 正文

真题详解系列:数据结构分布!

真题详解系列:数据结构分布!

233 道题,先看清骨架

2009 到 2026,数据结构一共考了 233 道题:197 道选择,36 道大题。

每年固定 2 道大题,一道写代码,一道算、画、说。18 年,18 道代码题,18 道综合题,一次没破例。

代码题:在某个结构上写算法

考点
次数
考了什么
顺序表
6
循环左移、两序列中位数、找主元素、最小未出现正整数、三元组距离、乘积最大值
链表
4
倒数第 k 个、共同后缀、删绝对值重复、重排
树
4
求 WPL、表达式树转中缀、判 BST、找与 K 最近结点
图
3
EL 路径、出度大于入度、拓扑序列是否唯一
排序
1
一趟快排拆两半

数组和链表占 10 道,一半多。这 10 道里 6 道是在原表上倒腾元素,动作就两种:双指针、原地交换,一个共同要求是不许开新数组。

结构一直在换,但 18 道都卡在一条线上:空间 O(1),时间一到两趟。

综合题:图占了一半

考点
次数
年份
图
7
2009、2011、2014、2015、2017、2018、2025
查找
4
2010、2013、2022、2024
树
3
2012、2016、2020
排序
2
2021、2023
栈
1
2026
队列
1
2019

图的 7 道,分给四种算法:

  • 最短路径 2 道:2009 手算 Dijkstra,2014 走 OSPF
  • 邻接矩阵 2 道:2011 画矩阵,2015 求 A²
  • 最小生成树 2 道:2017 Prim,2018 光缆代价
  • 关键路径 1 道:2025 AOE 网

给一张图,按算法一步步算,错一步后面全错。

剩下 11 道:

  • 查找 4 道:散列占 3 道(2010、2013、2024,都是建表 + 算 ASL),堆求前 10 小 1 道(2022)
  • 树 3 道:哈夫曼 2 道(2012、2020),正则 k 叉树 1 道(2016)
  • 排序 2 道:2021 认算法说复杂度,2023 外部排序归并趟数
  • 栈、队列各 1 道:2026 出栈序列,2019 可扩容队列

考点排行

考点
合计
选择
大题
排序算法
35
32
3
树的性质
16
15
1
哈夫曼与编码
15
12
3
图的存储与概念
14
11
3
二叉树遍历
12
11
1
链表
10
6
4
入栈出栈序列
10
9
1
散列表与 ASL
10
7
3
复杂度分析
9
9
0
B 树
9
9
0
平衡二叉树
8
8
0
二叉排序树
8
6
2
堆
8
7
1
顺序表
8
2
6
队列
7
6
1
关键路径
6
4
2
拓扑排序
6
5
1
特殊矩阵压缩
6
6
0
最小生成树
6
4
2
数组查找
5
5
0
最短路径
5
3
2
图的遍历
5
5
0
表达式求值
4
4
0
KMP
3
3
0
线索二叉树
3
3
0
栈
2
2
0
B+ 树
2
2
0
分块查找
1
1
0

排序算法 35 次遥遥领先,但只有 3 道大题,基本都挤在选择题里。真正靠大题吃饭的是顺序表和链表——顺序表 8 次里 6 道大题,链表 10 次里 4 道。

最后一列为 0 的那些:复杂度、B 树、AVL、特殊矩阵、图的遍历、KMP、线索树,从来没出过大题,会算、会判断就够。

近三年大题,2027 押什么

先看最近三年:

年份
代码题
综合题
2024
拓扑序列是否唯一(图)
散列表建表 + ASL
2025
数组乘积最大值(顺序表)
关键路径(图)
2026
BST 找最近结点(树)
出栈序列(栈)

代码题三年换了三个结构:图、数组、树。按这个轮法,2027 大概率回到链表——链表上一次出代码题还是 2019 年,之后就没再碰过,是所有结构里欠得最久的。考法还是老一套:快慢指针、就地逆置、重排。

综合题三年也换了三个考点:散列、图、栈。栈 2026 刚考完,按"刚考过的不考",2027 不会再出栈。剩下最大头的还是图,但 2025 刚考过关键路径,所以更可能是最短路径或最小生成树——这俩上一次出综合题分别是 2014 和 2018,早该轮到了。

一句话:代码题押链表,综合题押图的最短路径和 MST。

← 返回资讯列表