概要
我总结了 2009~2024 年 408 数据结构的选择题部分. 简要分析了其命题规律与命题内容, 将所有题目的分为 11 类进行归纳, 并对每类题的解题方法做了简要介绍.
分类标准纯主观, 解题方案纯主观.
命题规律
数据结构命题的灵活性主要体现在大题, 所以选择题的套路与规律非常明显, 多加练习即可取得高分.
但数据结构的选择题仍然是最耗时间的题, 因为它比其它三科都更需要动脑子, 把它放在试卷的第一部分很考心态. 个人认为 20~25min 做完是最佳用时.
题目的命制角度全部基于以下三个方面: 基本概念, 存储方式, 算法模拟.
每一章的题目分布较为平均, 但仍有个别年份有异常, 例如:
- 2015 年选择题没有考察线性表 (顺序表, 队列, 链表等), 而是直接从树开始出题. 结果是把链表放到了编程大题考.
- 2024 年选择题没有考察图论, 反而连着考了 5 道排序, 与其它年份差别巨大. 结果是把图论放到了编程大题考.
所以, 如果在考场上发现选择题好像少了点什么, 那么很不幸, 大概率要在大题会面了…
考察内容
题目的考察内容全部与考试大纲一一对应.
至今 (2024 年), 大纲中只有并查集, 十字链表, 分块查找, 红黑树这四个知识点尚未考察, 其它知识全都有不同频次的考察.
分类归纳
基本概念
基本概念题主要出现在第一道题. 主要考察各数据结构的定义和程序复杂度分析.
使用程序设计的基础知识即可做出.
线性表, 广义线性表的概念与存储
掌握线性表的基本概念, 会用 “数格子” 的方法算出下标或地址即可做出.
队列, 循环队列, 特殊矩阵的存储有额外的要求, 要牢记.
无论是何种线性表, 都要注意下标的起点.
链表的模拟
链表操作曾经只在 16 年考过一次, 但 21, 23, 24 年连着考了三次, 应该是未来的新高频考点.
会手动模拟即可.
栈与队列的模拟
这俩的模拟是永远的高频考点, 问法灵活多变, 条件千奇百怪, 但只要你会手动模拟, 就一定能做出来.
如果单纯的模拟做不出来, 那就在模拟的过程中找规律.
树, 森林的概念与存储
会根据树, 森林的性质计算结点数即可.
如果不会抽象推导, 那就写几个特例找规律. 实际上找规律反而是最快的方法.
要特别注意完全二叉树的存储方式.
树, 森林的模拟与分析
掌握树的遍历方式 + 树, 森林, 二叉树的转换这两个知识点, 会手动模拟这两者即可做出.
树的线索化其实就是让考生模拟遍历, 了解基本概念即可.
另外, 还是那句老话, 如果单纯的模拟做不出来, 那就在模拟的过程中找规律.
特殊树
我把哈夫曼树, 二叉查找树, 二叉平衡树, B 树全部归于这一类题. 虽然它们之中的几位也可以归到排序和查找.
特殊树是必考点, 100% 会考, 自 2009 年以来没有任何例外.
它们与前面的题目相比少了思维上的难度, 增加了记忆的难度.
要死死地记住它们的定义, 存储, 操作等, 每一个细节都不能有模糊的地方, 才能保证做对.
另外, 与哈夫曼树相关的编码, 加权路径长度等概念也要记忆.
红黑树虽在大纲中, 至今未考过.
图的概念与存储
熟记图的概念和各存储方式即可. 对存储细节也要掌握, 不能浮于表面, 408 就爱考细节.
经常把存储方式与具体算法结合起来考, 要会分析复杂度.
另外, 十字链表存储尚未考过, 但其孪生兄弟多重邻接表在 24 年考了.
图的模拟与应用
没什么好说的, 所有的图遍历算法和图应用算法都得会手动模拟.
会模拟就有分, 没有就没分.
当然, 会模拟的同时也得明确算法是解决什么问题的, 别光会模拟了.
天天模拟要是模过头了可能就魔怔了, 一问基础概念都不会了.
查找 (不含B树, B+树)
该类题想说的与上一节相同, 狠狠地模, 但也要重视基础概念.
其中 KMP 算法比较特殊, 要专门练习. 24 年考了优化后的 KMP 算法, 所以要全面掌握了.
排序
该类题想说的与上一节相同, 狠狠地模, 但也要重视基础概念.
排序经常把若干个算法放在一起比较, 所以也要全面掌握, 不要有侥幸心理.
很多人头疼排序性质的分析, 比如稳定性和比较趟数等. 但只要你会模, 这些性质压根不用死记硬背.
另外, 外部排序要重点学习. 这是很多人都很陌生的排序算法, 但 408 并不轻视外部排序, 甚至在 23 年考了一道外部排序的大题.
总结
解法全都归结于开头的三个词, 基本概念, 存储方式, 算法模拟. 尤其是算法模拟这一点, 哪怕你毫无算法思维, 只要你肯记, 大部分题都能手动模拟出来.