考试科目：数据结构

试卷满分及考试时间:试卷满分为100分，考试时间为120分钟。

一、绪论

考试内容

基本概念 抽象数据类型的表示与实现  算法和算法分析

考试要求：

1. 了解数据结构的基本概念；

2. 理解数据的逻辑结构和存储结构的概念及其相互关系；

3. 了解算法的五个要素；

4. 掌握计算语句的频度和时间、空间复杂度的方法。

二、线性表

考试内容

线性表的类型定义 线性表的顺序表示和实现　线性表的链式表示和实现

考试要求

1．理解线性表的逻辑结构和特性，熟练掌握线性表的两类存储结构：顺序存储结构和链式存储结构；

2．熟练掌握线性表在顺序存储结构上实现查找、插入和删除等基本运算的算法；

3．熟练掌握在各种链表结构中实现线性表运算的算法；

4．从时间和空间复杂度的角度分析比较线性表两种存储结构的不同特点。

三、栈和队列

考试内容

栈 栈的应用 栈与递归的实现 队列

考试要求

1．理解栈和队列两种数据结构的概念和特点；

2．熟练掌握在顺序和链式两种存储结构上完成栈的基本运算；

3．熟练掌握链式队列和循环队列的基本操作；

4. 掌握利用栈将递归算法转化为非递归算法的方法。

四、串

考试内容

串类型的定义 串的表示和实现 串的模式匹配算法 串操作应用

考试要求

1．了解串的定义和相关概念；

2．掌握串的基本运算及其组合应用方法；

3．理解串的静态存储结构和动态存储结构，及其对应的各种运算；

4. 理解串的模式匹配算法。

五、数组和广义表

考试内容

数组的定义 数组的顺序表示和实现 矩阵的压缩存储 广义表的定义 广义表的存储结构 

考试要求

1．理解数组存储方式，熟练掌握数组在以行序为主的存储结构中的地址计算方法；

2．理解稀疏矩阵的压缩存储方法，掌握稀疏矩阵运算采用的处理方法；

3. 了解广义表的定义及存储结构。

六、树和二叉树

考试内容

树的定义和基本术语 二叉树 遍历二叉树和线索二叉树 树和森林

考试要求

1．掌握树的定义和相关术语，熟练掌握二叉树的定义、性质和存储结构；

2．熟练掌握二叉树按各种顺序遍历的递归和非递归算法；

3. 了解线索二叉树的定义和线索的建立方法；

4. 了解树的各种存储结构，森林与二叉树的转换，树和森林的遍历。

七、图

考试内容

图的定义和术语　图的存储结构图的遍历 图的连通性问题 有向无环图及其应用 最短路径 

考试要求

1．了解图的定义和有关术语，理解并掌握图的各种存储结构；

2．熟练掌握按深度优先和广度优先遍历图的算法；

3. 理解图的连通性问题；

4. 理解拓扑排序和关键路径；

5. 熟练掌握求最短路径的算法。

八、查找

考试内容

静态查找表 动态查找表 哈希表 

考试要求

1．熟练掌握顺序查找、折半查找和索引查找算法；

2．掌握二叉排序树的查找方法和构造方法；

3. 熟练掌握哈希函数的构造方法以及哈希表的查找方法。

九、内部排序

考试内容

内部排序的概念 插入排序  快速排序  选择排序 归并排序 基数排序 各种内部排序方法的比较讨论

考试要求

1.熟练掌握插入排序、快速排序、选择排序、归并排序和基数排序的排序方法、过程和特点;

2. 掌握各种排序方法的应用，并能够灵活选择；

3. 掌握各种排序方法的时间复杂度分析方法。

参阅：

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