《数据结构》考试大纲基本参考书《数据结构(C语言版)》严蔚敏吴

《数据结构》考试大纲基本参考书《数据结构(C语言版)》严蔚敏吴

《数据结构》考试大纲

基本参考书：《数据结构（C语言版）》 严蔚敏 吴伟民 清华大学出版社

一、考试的基本要求

用计算机解决一个问题，要将反映问题的数据信息存入计算机，和设计能解决问题的算法。数据结构学科就是回答计算机如何存储各种数据及数据之间的关系，以及对数据作基本处理的算法实现。

要求考生比较系统地理解数据结构的基本概念和基本理论，掌握常用数据结构及其基本算法，具有综合运用数据结构知识解决问题的能力。

二、考试方法和考试时间

考试采用闭卷、笔试形式，考试时间为180分钟。

三、对编程语言的要求

试题中所有的算法，要求用C或C++语言描述。

四、考试内容和考试要求

1、基本概念

考试内容

数据结构的基本概念；渐近算法分析方法。

考试要求

1) 数据结构包含数据元素集合和数据元素之间关系的集合。

2) 理解算法与数据结构之间的关系。

3) 掌握渐近算法分析方法：估算算法时间复杂性的大O表示法。

2、线性表和字符串

考试内容

线性表的特点，线性表的顺序实现和链式实现，线性表的应用；字符串的基本运算，字符串匹配算法。

考试要求

1） 理解线性表的结构和特点，掌握线性表上基本操作的实现算法。

2） 掌握顺序存储线性表的存储方式，掌握基本操作的实现算法。

3） 掌握链接存储线性表的存储方式。掌握单链表和循环链表的结构，基本操作的实现

《数据结构》考试大纲基本参考书《数据结构(C语言版)》严蔚敏吴

算法。

4） 理解字符串的存储结构，字符串的基本运算。

5） 掌握字符串简单匹配算法；理解字符串KMP匹配算法，掌握KMP算法的匹配过程，

以及求模各字符失败链接值的方法。

3、栈和队列

考试内容

栈和队列的基本运算及其应用。

考试要求

1) 理解栈的定义和结构特点，掌握其存储方式(顺序存储与链接存储)和基本操作的实现

算法。

2) 理解队列的结构和特点，掌握其存储方式(顺序存储与链接存储)和基本操作的实现算

法。

4、递归

考试内容

递归的基本概念，递归的简单应用。

考试要求

1) 理解递归的基本概念和实现原理，掌握用递归的思想描述问题和构造算法的方法。

2) 掌握求整数的阶乘、汉诺塔等问题的递归解法。

3) 掌握用栈改递归求解为非递归求解的方法。

5、树和二叉树

考试内容

树和二叉树。

考试要求

1) 理解树的结构和定义，掌握树的主要概念。

2) 理解各种二叉树的结构，掌握其特点，具有运用二叉树解决实际问题的能力。

3) 掌握二叉树的三种遍历方法的实现原理和性质，能将二叉树的遍历方法应用于求解二

叉树的叶子结点个数、二叉树计数等问题，掌握遍历的非递归实现方法。

4) 理解树的存储结构，掌握树的遍历等方法的实现。

5) 理解霍夫曼编码的基本原理，掌握基于霍夫曼树生成霍夫曼编码的方法。

6、集合和搜索

考试内容

集合、二叉搜索树和AVL树。

《数据结构》考试大纲基本参考书《数据结构(C语言版)》严蔚敏吴

考试要求

1) 理解集合的基本概念，掌握常用实现集合的各种存储方法。

2) 掌握无序线性表的顺序搜索、有序线性表的二分搜索。

3) 理解二叉搜索树的定义和特点，掌握二叉搜索树插入和删除的算法。

4) 理解AVL树的定义和特点，掌握AVL树上插入新结点的方法。

7、图

考试内容

图的存储，图的遍历，最小生成树，最短路径和活动网络。

考试要求

1) 掌握图的基本概念，图的邻接矩阵存储方式和邻接表存储方式。

2) 掌握图的深度优先遍历和广度优先搜索遍历方法。

3) 掌握Kluskal和Prim生成最小生成树的方法。

4) 掌握Dijkstra求单源最短路径的方法。

5) 掌握AOV活动网络的拓扑排序算法，AOE活动网络的关键路径的方法。

8、排序

考试内容

插入排序，交换排序，选择排序，归并排序和基数排序。

考试要求

理解各种排序方法的实现，掌握各种排序算法的特点和时间复杂性，能按指定的排序方法实现对数表作排序。

9、索引结构与散列

考试内容

线性索引结构、B－树和B+树索引结构，散列。

考试要求

1) 理解线性索引结构的特点。

2) 理解B-树和B+树索引的结构，掌握B-树和B+树进行插入和删除的方法。

3) 理解散列的实现原理，能按指定的散列函数和解决冲突的方法构造散列表。