数据结构复习.pdfVIP

数据结构复习

本课程学习的目的:

通过本课程的学习，应能掌握数据结构的特点、存储方

法和基本运算，培养自己运用C++语言正确编写算法及

调试的能力，运用数据结构解决简单的实际问题的能力，

可为后续计算机方面课程的学习打下坚实的基础。

基本要求:

1、掌握重要数据结构的逻辑结构、存储结构及基本运算

的实现，会运用线性表、二叉树等设计算法以解决一些简

单的实际问题，会通过阅读算法理解算法；

2、学会做简单的算法分析，包括算法的时间复杂度和空

间复杂度。

题型：

一、选择题（20分）20*1

二、填空题（20分）10*2

三、应用题（45分

二叉树（二叉树的遍

历和转换、哈夫曼树和编码）、图（最小

生成树或单源点最短路径）、查找（散列

查找）、排序（希尔、快速或堆））5*9

四、算法设计题（15分

单链表的应用、

二叉树遍历的应用）

题目给出函数框架，只需实现函数功能

即可

法求此二叉树上度为1的结点个数。

structBiNode//二叉树的结点结构

{

intdata;

BiNode*lchild,*rchild;

};

intcount(BiNode*root)/*root为二叉树的根结点*/

{

}

第一章概论

基本要求:

1、熟悉数据、数据元素(数据项)、数据结构、数据的

逻辑结构与物理结构概念

2、熟悉逻辑结构分线性和非线性（树、图）结构及每

种结构的基本特征

3、了解物理结构分顺序存储和链式存储

4、了解算法的定义、算法的特性、算法的时间复杂度、

算法的空间复杂度

5、了解简单的计算语句频度和估算算法时间复杂度的

方法

第二章线性表

基本要求：

1、了解线性表的逻辑结构特性，以及线性表的两种存储

实现方式

2、熟练掌握两种存储结构的描述方法。链表是本章的重

点和难点。

3、灵活掌握顺序表的定义与基本操作的实现，包括插入、

删除算法的实现；

4、灵活掌握链表结构实现线性表基本操作的实现算法；

5、能够从时间和空间复杂度的角度综合比较线性表两种

存储结构的不同特点及其适用场合。

6、会用线性表解决简单的实际问题。

第三章栈、队列

基本要求：

1、掌握栈和队列的定义、特性，并能正确应用它们解决实

际问题；会通过阅读算法理解算法。

2、熟练掌握栈的顺序表示、链表表示以及相应操作的实现。

特别注意栈空和栈满的条件；（主要是出栈和入栈）掌握

递归函数的阅读。

3、熟练掌握队列的顺序表示、链表表示以及相应操作的实

现。特别是循环队列中队头与队尾指针的变化情况及队列

空和队列满的条件及元素的个数。

循环队列

空：front==rear

满：(rear+1)%MAXN==front

队列的元素个数：

（rear-front+MAXN)%MAXN

入队:rear=(rear+1)%MAXN;

data[rear]=x;

出队：front=(front+1)%MAXN

return(data[front]);

第4章串和数组

1、掌握数组在以行（列）为主的存储结构中的地址计算法

2、掌握对特殊矩阵（主要是下三角）进行压缩存储时的下标变换

公式

3、了解稀疏矩阵的三元组压缩存储方法

4、理解串的基本操作的含义，并能利用这些基本操作来实现串的

其它各种操作的方法。

第5章树

基本要求：

1、了解树和森林的概念。包括树的定义、树的术语；

2、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结

的特点和性质；

3、熟练掌握二叉树的遍历方法及遍历算法和算法的应用；

4、了解树的各种存储结构及其特点，掌握树、森林与二叉树

的转换方法；

5、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的

计算.

完全二叉树、满二叉树

第6章图

基本要求

1、理解图的基本概念，熟悉图的各种存储结构（邻接

矩阵和邻接表）；

2、熟练掌握图的两种搜索路径的遍历；

3、掌握构造最小生成树（prim算法）的方法，并理解

克鲁斯卡尔算法；

4、理解求AOV网的拓扑排序的方法；

5、掌握用Dijkstra方法求解单源最短路径问题；

6、了解在AOE网中求关键路径的方法。

第7章查找

基本要求

1、熟练掌握顺序表和有序表的查找算法及其性能分析

方法:顺序查找、二分查找（判定树）

2、熟