2018年北京交通大学925数据结构考研大纲硕士研究生入学考试大纲

北京交通大学 2018 年招收硕士研究生入学考试大纲
925 数据结构
1、绪论。（1）掌握相关的基本概念，如数据结构、逻辑
结构、存储结构、数据类型、抽象数据类型等；（2）掌握算
法设计的原则，掌握计算语句频度和估算算法时间复杂度和
空间复杂度的方法；（3）了解使用类 C 语言描述算法的方法。
2、线性表。（1）掌握线性表的逻辑结构和存储结构；（2）
掌握线性表在顺序结构和链式结构上实现基本操作的方法；
（3）理解线性表两种存储结构的不同特点及其适用场合，
会针对需求选用合适的存储结构解决实际问题；（4）了解一
元多项式的表示方法和基本运算的实现方法。
3、栈和队列。（1）了解栈和队列的特点；（2）掌握在两
种存储结构上栈的基本操作的实现；（3）掌握栈的各种应用，
理解递归算法执行过程中栈状态的变化过程；（4）掌握循环
队列和链队列的基本运算；（5）会应用队列结构解决实际问
题。
4、串。（1）掌握串的基本运算的定义，了解利用基本运
算来实现串的其它运算的方法；（2）了解在顺序存储结构和
在堆存储结构以及块链存储结构上实现串的各种操作的方
法；（3）理解 KMP 算法，掌握 NEXT 函数和改进 NEXT 函数
的定义和计算。
5、数组和广义表。（1）掌握数组在以行为主和以列为主