2019年北京交通大学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)掌握数组在以行为主和以列为主的存储结构中的地址计算方法;

(2)掌握矩阵压缩存储时的下标变换方法，了解以三元组表示稀疏矩阵的方法;

(3)理解广义表的定义及其存储结构，理解广义表的头尾和子表两种分析方法。

6、树和二叉树。

(1)熟练掌握二叉树的结构特点和性质，掌握二叉树各种存储结构及

构建方法;

(2)掌握按先序、中序、后序和层次次序遍历二叉树的算法，理解二叉树的线索化实质和方法;

(3)利用二叉树的遍历求解实际问题;

(3)掌握树的各种存储结构及其特点，掌握树的各种运算的实现算法;(4)掌握建立最优二叉树和哈夫曼编码的方法。

7、图。

(1)熟练掌握图的基本概念，会构建各种图的存储结构;

(2)掌握深度优先搜索遍历图和广度优先搜索遍历图的算法;

(3)灵活运用图的遍历算法求解各种路径问题，包括最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。

8、查找。

(1)熟练掌握各种静态查找和动态查找算法，会计算查找成功时和失败时的平均查找长度;

(2)掌握二叉排序树的建立、插入和删除过程，掌握二叉平衡树的建立和旋转平衡方法;

(3)掌握B-树的建立、插入和删除结点的过程;

(4)熟练掌握哈希表的构造方法和处理冲突的方法。

9、排序。

(1)掌握各种排序算法，包括插入类、交换类、选择类、归并类排序及基数排序;

(2)能够对各种排序方法进行比较分析，如稳定性、时间和空间性能等，了解各种排序方法的特点和不同并灵活应用;

(3)理解外部排序的主要思想和过程。