2021年内蒙古工业大学《数据结构》考研大纲-考博信息网

2021年内蒙古工业大学《数据结构》考研大纲

2021年内蒙古工业大学考研大纲

科目名称

数据结构

科目代码

808

考试范围：

1．数据结构的基本概念

数据、数据元素与数据项等概念及其相互间关系；数据的逻辑结构、存储结构的区别与联系；抽象数据类型、算法的时间性能和空间性能分析方法。

2．线性表

线性表的基本概念；线性表的顺序结构与链式结构定义，以及顺序结构与链式结构的存储分配特点；线性表顺序结构与链式结构的插入、删除和查找等基本算法实现，以及对相应算法的时间性能分析和空间性能分析。

3．栈与队列

栈与队列的概念与基本操作；链队列、循环队列的组织方法与基本操作的实现；栈的应用。

4．串

串的概念与串的基本操作的实现；模式匹配算法与算法时间和空间性能分析。

5．数组与广义表

多维数组的结构特点及其存储地址计算方法；矩阵的压缩存储思想、存储结构和存储地址映射关系；广义表的逻辑结构及其存储结构。

6．树与二叉树

树的基本概念；二叉树的定义与性质、顺序存储结构与链式存储结构；二叉树的遍历算法；树和森林的基本概念；哈夫曼树与哈夫曼编码。

7．图

图的基本概念、图的邻接矩阵和邻接表的表示方法；图的遍历算法；图的最小生成树的概念及相关算法；图的拓扑排序、关键路径与最短路径算法。

8．查找

查找的基本概念；静态查找表的实现；折半查找的实现；二叉排序树的概念及实现；哈希表的思想，各种查找算法的性能分析。

9．排序

排序的基本概念；插入排序算法与算法性能分析；交换排序算法与算法性能分析；选择排序算法与算法性能分析；归并排序算法与算法性能分析；基数排序算法与算法性能分析；不同排序算法间性能对比。

参考书目：

《数据结构（C语言版）》，严蔚敏，吴伟民编著，清华大学出版社，2012年。

《新编数据结构习题与解析》，李春葆编著，清华大学出版社，2019年。