数据结构期末复习资料_数据结构期末复习讲义

数据结构期末复习资料由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构期末复习讲义”。

《数据结构》课程复习资料

第一章：数据结构概述

1、掌握数据结构的定义，即数据结构三要素：数据的逻辑结构、存储结构、操作；

2、数据结构包括：逻辑结构和存储结构；

3、数据之间的关系：表（一对一之间的关系）、树（一对多之间的关系）、图（多对多之间的关系）；

4、算法的定义：算法衡量的标准：时间复杂度和空间复杂度；

5、算法时间复杂度的求法：给定一段程序，求其时间复杂度；时间复杂度的比较；

6、为什么学习“数据结构”？“数据结构”课程主要学了哪些知识？

第二章：线性表

1、线性表按照存储结构不同分为顺序表、链式表；顺序表的特点：逻辑上相邻的两个元素在物理上也相邻；链式表的特点：逻辑上相邻的两个元素在物理上未必相邻；（“未必”的含义是可相邻也可以不相邻）

2、比较线性表顺序存储和链式存储的优缺点。

第三章：栈和队列

1、栈和队列的特点：栈：后进先出，队列：先进先出

2、熟悉栈和队列的基本操作：初始化栈、入栈操作、出栈操作、判断栈是否为空、取栈顶元素等。

3、根据实例，能够容易的判断出是栈的应用还是队列的应用？

4、重点掌握栈的应用：进制转换算法的思想或程序。

第四章：数组

1、牢记对称矩阵、三角矩阵、对角矩阵的特点，掌握矩阵中的元素Aij与一维数组SA[K]的对应关系。

2、掌握稀疏矩阵的三元组表示法。

第五章：串

1、掌握上课介绍的9种函数名称及其实现结果；

第六章：树

1、二叉树的5个性质；

2、二叉树前序、中序和后序遍历，根据2种遍历结果求第3种遍历结果。

3、完全二叉树、满二叉树、哈弗曼树的定义；

4、给定一组叶子权值，求带权路径长度最小的多少？

第七章：图

1、掌握图的术语：无向完全图、有向完全图、顶点的度等；

2、图的深度优先遍历和广度优先遍历；

3、图的邻接矩阵存储，给定一个图，求出邻接矩阵；或者给定一个邻接矩阵，构造图；

4、图的最小生成树；

第八章：查找

1、查找的定义：静态查找和动态查找

2、折半查找算法的思想；

第九章：排序

1、掌握排序的分类：插入排序、交换排序、选择排序；

2、重点掌握希尔排序、快速排序、简单选择排序；