2023考研大纲：山东理工大学2023年考研 005-计算机科学与技术学院 考试大纲及参考书目

科目代码：

8

80

科目名称：

数据结构

考试范围：

一、

绪论

1

、考核知识点

数据的逻辑结构与物理结构；抽象数据类型；算法及其度量

。

2

、考核要求

（

1

）理解数据结构的基本概念和术语；

（

2

）掌握抽象数据类型的表示与实现；

（

3

）掌握算法的基本概念和算法的性能分析方法。

3

、考核重点

（

1

）数据的逻辑结构与物理结构；

（

2

）算法时间复杂度性能分析的方法。

二、线性表

1

、考核知识点

线性表；顺序表

的表示

与实现；链表

的表示

与实现；顺序与链式存储的比较

。

2

、考核要求

（

1

）理解线性表的定义和逻辑结构特性；

（

2

）掌握线性表的顺序存储方法和

常用

算法；

（

3

）掌握线性表的链式存储方法和

常用算法

；

（

4

）了解用线性表表示一元多项式和稀疏多项式的方法

3

、考核重点

（

1

）

顺序存储结构与链式存储结构的区别；

（

2

）

顺序表和单链表的

常用经典

算法。

三、栈和队列

1

、考核知识点

栈与队列的特点；栈的递归算法；链队列；循环队列。

2

、考核要求

（

1

）熟练掌握栈的类型定义、表示和基本操作的实现；

（

2

）灵活运用栈的特性设计算法；

（

3

）掌握递归算法的设计方法和设计思路；

（

4

）熟练掌握队列的类型定义、表示和基本操作的实现

3

、考核重点

（

1

）栈和队列的特性；

（

2

）栈与队列基本操作的实现；

（

3

）栈的递归算法应用。

四、串

1

、考核知识点

串，模式匹配算法。

2

、考核要求

（

1

）掌握串类型的定义及其表示方法；

（

2

）掌握串基本算法的实现方法；

（

3

）

掌握

KMP

算法。

3

、考核重点

KMP

算法

五、数组和广义表

1

、考核知识点

数组；稀疏矩阵的压缩存储；广义表。

2

、考核要求

（

1

）了解数组的定义和数组的顺序表示方法；

（

2

）数组元素顺序存储的地址计算；

（

3

）掌握特殊矩阵和稀疏矩阵的压缩存储方法；

（

4

）了解广义表的定义和存储结构。

3

、考核重点

（

1

）数组元素的地址计算方法；

（

2

）矩阵的压缩存储；

（

3

）广义表的基本性质。

六、树和二叉树

1

、考核知识点

二叉树的定义、性质与存储结构；二叉树的遍历及其应用；树与森林的表示与遍历；哈夫曼树与哈夫曼编码。

2

、考核要求

（

1

）理解树和二叉树的定义、术语；

（

2

）理解二叉树的基本性质；

（

3

）理解二叉树存储结构；

（

4

）理解二叉树的遍历算法思想，掌握递归和非递归遍历算法实现；

（

5

）掌握二叉树遍历算法的应用；

（

6

）了解树

、

森林的存储方法及与二叉树间的转换方法；

（

7

）掌握哈夫曼树及其应用。

3

、考核重点

（

1

）二叉树的基本特性；

（

2

）二叉树的遍历及其应用算法；

（

3

）哈夫曼树及哈夫曼编码

七、图

1

、考核知识点

图的逻辑结构；邻接表

与邻接矩阵

；深度优先遍历；广度优先遍历；最小生成树、拓扑排序、关键路径、最短路径。

2

、考核要求

（

1

）理解并掌握图的基本概念、术语和基本逻辑结构特征；

（

2

）理解并掌握图的存储结构；

（

3

）掌握图的深度优先和广度优先遍历算法；

（

4

）掌握图结构的典型应用，如最小生成树、拓扑排序、关键路径、最短路径等。

3

、考核重点

（

1

）图的逻辑结构与存储方法；

（

2

）图的深度优先、广度优先遍历算法；

（

3

）最小生成树算法；

（

4

）拓扑排序算法；

（

5

）单源点最短路算法

八、查找

1

、考核知识点

顺序查找；折半查找；分块查找；二叉排序树；平衡二叉树；哈希表。

2

、考核要求

（

1

）理解静态查找表、动态查找表和哈希查找的基本概念；

（

2

）掌握静态查找表的各种查找方法如：顺序查找、折半查找、分块查找；

（

3

）掌握二叉排序树与平衡二叉树；

（

4

）掌握哈希表的概念

、

查找

以及

哈希函数的构造方

与

解决冲突的基本方法；

（

5

）掌握各种查找算法的效率分析。

3

、考核重点

（

1

）折半查找算法；

（

2

）二叉排序树；

（

3

）哈希表。

九、排序

1

、考核知识点

直接插入排序；希尔排序；冒泡排序；快速排序；堆排序；归并排序；基数排序。

2

、考核要求

（

1

）理解排序的基本概念；

（

2

）掌握基于插入思想的排序算法如：直接插入排序、希尔排序；

（

3

）掌握基于交换思想的排序算法如：冒泡排序、快速排序；

（

4

）掌握基于选择思想的排序算法如：简单选择排序、堆排序；

（

5

）掌握其它排序算法如：归并排序、基数排序；

（

6

）能够对各种排序算法进行分析比较。

3

、考核重点

（

1

）快速排序算法及其应用；

（

2

）堆排序算法；

（

3

）归并排序算法。

参考书目：

数据结构

（

C

语言版）

严蔚敏

吴伟民

编著

清华大学出版社