2020年北京交通大学数据结构考试大纲925

925 数据结构

1、绪论。

（1）掌握相关的基本概念，如数据结构、逻辑结构、存储结构、数据类型、 抽象数据类型等；（2）掌握算法设计的原则，掌握计算语句频度和估算算法时间复杂度和空 间复杂度的方法；（3）了解使用类 C 语言描述算法的方法。

2、线性表。

（1）掌握线性表的逻辑结构和存储结构；（2）掌握线性表在顺序结构和链 式结构上实现基本 *** 作的方法； （3）理解线性表两种存储结构的不同特点及其适用场合， 会针对需求选用合适的存储结构解决实际问题；（4）了解一元多项式的表示方法和基本运算 的实现方法。

3、栈和队列。

（1）了解栈和队列的特点；（2）掌握在两种存储结构上栈的基本 *** 作的 实现；（3）掌握栈的各种应用，理解递归算法执行过程中栈状态的变化过程；（4）掌握循环 队列和链队列的基本运算；（5）会应用队列结构解决实际问题。

4、串。

（1）掌握串的基本运算的定义，了解利用基本运算来实现串的其它运算的方法； （2）了解在顺序存储结构和在堆存储结构以及块链存储结构上实现串的各种 *** 作的方法； （3）理解 KMP 算法，掌握 NEXT 函数和改进 NEXT 函数的定义和计算。