北京工商大学

《数据结构》考试大纲

一、考查目标

1.掌握数据结构的基本概念、基本原理和基本方法。

2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

3.能够利用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

二、考试形式和试卷结构

1、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟

2、答题方式

答题方式为闭卷、笔试

3、试卷题型结构

单项选择题

判断题

简答题/填空题

综合应用题

算法设计题

三、考试范围及基本要求

(一)　绪论

【内容】

数据结构的基本概念和术语，数据抽象，算法的描述和算法分析。

【要求】

掌握基本概念和术语，初步学会算法的分析度量。

(二)　线性表

【内容】

线性表的逻辑结构，线性表的顺序存储结构，线性表的链式存储结构，循环链表，双向链表。线性表的应用。

【要求】

1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的不同方法得到两类不同的存储结构。

2. 熟练掌握这两类存储结构的描述方法，以及循环链表、双向链表的特点等。

3. 熟练掌握线性表在顺序存储结构上实现的基本操作：插入、删除等算法。

(三)　栈和队列

【内容】

栈的定义，栈的表示和实现，栈的顺序存储结构，应用举例：表达式求值(*)。

队列的定义，队列的顺序存储结构(和栈类似结构及循环队列)，链式存储结构。总结线性表静态及动态的特点(包括栈和队列)，并举例说明在实际工作中的应用。

【要求】

1. 掌握栈和队列这两种数据结构的特点,懂得在什么样的问题中应该利用哪种结构。

2. 熟练掌握在顺序存储结构上实现栈的基本运算,特别注意栈满和栈空的条件及它们的描述。

3. 熟练掌握循环队列和链队列的基本运算,特别注意队满和队空的描述方法。

4. 理解递归算法执行过程中栈的状态变化过程。

(四)　树和二叉树

【内容】

二叉树的定义及基本操作，二叉树的性质，二叉树的存储结构，二叉树的遍历。

树的定义及存储结构，森林与二叉树的转换，树和森林的遍历，哈夫曼树及其应用。

【要求】

1. 熟练掌握二叉树的结构特性,了解相应的证明方法。

2. 了解几种特殊形态的二叉树。

3. 熟悉二叉树的各种存储结构的特点及适用范围。

4. 遍历二叉树是二叉树各种运算的基础,不仅要熟练掌握各种序遍历的递归和非递归算法,还要了解遍历过程中“栈”的状态,并能灵活运用递归遍历算法实现二叉树的其他各种运算。

5. 树和森林(树的存储结构、遍历方法;森林与二叉树的转换方法)。

6. 哈夫曼树及哈夫曼编码。

(五)　图

【内容】

图的定义和术语，图的存储结构，图的遍历，深度优先搜索，广度优先搜索，应用举例：人工智能中的问题求解(*)。

无向图的连通分量和生成树，最小生成树，有向无环图及其应用：最短路径，拓扑排序(*)，关键路径(*)。

【要求】

1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。

2. 熟练掌握图的遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。在学习中应注意图的遍历算法与二叉树的遍历算法之间的类似和差异。

3. 应用图的遍历算法求解各种简单路径问题。

4. 理解参考书中讨论的各种图的算法，掌握其主要数据结构的变化情况。

(六)　查找

【内容】

静态查找表，二叉排序树和平衡二叉树(*)，散列(Hash)表。

【要求】

1. 顺序表和有序表的查找方法及其平均查找长度的计算方法。

2. 静态查找树的构造方法和查找算法,理解静态查找树和折半查找的关系。

3. 熟练掌握二叉排序树的构造和查找方法。

4. 熟练掌握散列表的构造方法，深刻理解散列表与其它结构的表的实质性的差别。

6. 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

(七)　内部排序

【内容】

冒泡排序，插入排序，快速排序，选择排序，堆排序，归并排序。

【要求】

1. 了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。

2. 掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能(*)。

3. 理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。