2019年辽宁科技大学硕士研究生自命题考试大纲-《数据结构》

    （一）绪论

了解和掌握数据结构的基本概念，这些概念包括:数据、数据元素、数据类型、抽象数据类型、数据逻辑结构、数据存储结构、数据结构上的操作集合、算法及算法特点等。了解和掌握算法效率分析的目的和方法。

考点：数据结构的定义，数据逻辑结构和存储结构以及二者之间的关系、算法效率分析（时间复杂度求解）。

（二）线性表

了解线性表的逻辑结构和基本操作；理解线性表的顺序存储结构和实现方法；理解线性表的链式存储结构和实现方法；了解单循环链表和双向链表的概念和基本设计方法。

考点：单链表的存储结构设计及操作实现算法，利用单链表完成差或等比及判断双链表是否对称的应用。

（三）栈和队列

理解栈的概念、顺序栈和链式栈的设计方法；理解队列的概念、顺序循环队列和链式队列的设计方法；了解优先级队列以及优先级队列和一般队列的差别；了解堆栈和队列的应用方法。

考点：栈和队列的操作特性，双栈共享空和满的条件，循环队列空，满的条件及队列中元素个数的求解。

（四）字符串和多维

理解串的概念；了解串基本操作的实现方法；了解串的BF模式匹配方法，掌握KMP模式匹配方法。熟练掌握二维数组的概念，了解特殊矩阵和稀疏矩阵的压缩存储方法；及稀疏矩阵的三元组表的概念。

考点：串的基本操作应用，KMP模式匹配的NEXT求解；数组中元素地址的求解，特殊矩阵的存储。

（五）树与二叉树

了解树的定义、表示方法及其典型存储结构；理解二叉树的定义、性质、存储结构和操作的实现方法；掌握二叉树的遍历算法及其应用实现；理解哈夫曼树的概念及其应用；了解树与二叉树的关系。考点：二叉树的性质；二叉树的遍历算法及应用；哈夫曼树的构建和编码的应用方法。并能利用树

的遍历实现如统计二叉树深度或宽度的算法，会实现树、二叉树和森林的相互转换。

（六）图

了解图的基本概念和术语；掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；理解图的深度和广度优先遍历方法和算法设计方法；理解小生成树的概念以及普里姆算法和单源短路径的狄杰斯特拉算法，拓扑排序和关键路径。

考点：图的邻接矩阵和图的邻接表存储结构；图的深度和广度遍历算法；小生成树的求解，单源点短路径的求解，拓扑排序。

（七）查找

了解查找的基本概念和查找方法的评判标准；理解顺序查找，掌握折半（二分）查找的算法设计方法；掌握二叉排序树和平衡二叉树树的基本结构和插入、删除方法；掌握散列函数、散列冲突函数和散列表的构造方法。

考点：二叉排序树和平衡二叉树的构造；散列函数、散列冲突函数和散列表（开散列和闭散列）的构造方法。

（八）排序

了解排序的基本概念和排序算法的评判标准；掌握直接插入排序、希尔排序、直接选择排序、堆排序、快速排序、二路归并排序、基数排序的算法思想和算法设计方法；理解各种排序方法的性能特点。

考点：希尔排序、堆排序、快速排序的实现，各种排序方法的时间复杂度分析。

VI参考文献

《数据结构（C++版）》（第二版），王红梅编著，清华大学出版社，2011年。