《数据结构》期末复习提纲（计算机10级）
第一部分 章节知识点
第1章 绪论
1、基本概念
（1）数据元素：是数据的基本单位。一个数据元素由若干数据项组成，数据项是数据不可分割的最小单位。
（2）数据类型：是性质相同的数据元素的集合及在这个集合上的一组操作。 （3）数据结构
a、广义：按某种逻辑关系组织起来的一批数据应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。
数据结构包含三个方面的内容，即数据的逻辑结构、存储结构和对数据所施加的运算（操作），具体如下图所示。
b、狭义：就是指数据的组织形式，即逻辑结构（具体4类：集合、线性结构、树形结构和图形结构）。
2、算法分析（主要分析：时间复杂度和空间复杂度）
（1）定义：是对特定问题求解步骤的一种描述，是指令的有限序列。
特性（5个）：有穷性、确定性、可行性、输入、输出。 （2）算法和程序的区别与联系：
区别：a、一个程序不一定满足有穷性（死循环）。
B、程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 联系：一个算法若用计算机语言来书写，则它就可以是一个程序。 （3）会分析时间复杂度（包括时间频度）。
第2章 线性表（结点间一对一的关系）
1、线性表的逻辑结构描述。 2、线性表的存储结构及其运算。
第3章 栈和队列――都是操作受限的线性表
1、栈的定义。
2、栈的存储结构（主要指顺序栈）： （1）类型描述；（2）运算：栈空状态、栈满状态、入栈、出栈、取栈顶。 二、队列的基本内容 1、队列的定义。 2、队列的存储结构：
普通顺序队列：队空、队满、队列长度、入队、出队、取队头元素顺序存储队列链式存储
类型描述、队空、队满、队列长度、入队、出队、取队头元素循环队列：类型描述、队空、队满、队列长度、入队、出队、取队头元素链队列：
第4章 串――是一种特殊的线性表
特殊性：每个元素只有一个字符组成
1、串的定义。
2、子串、子串在主串中的位置、两串相等、空串、空格串的概念 3、以下运算的使用：
StringAssign(S,string_constant); StrCmp(S,T); StrLen(S); Strcat(S,T); StrCpy(S,T);SubStr(S,pos,len,sub); Index(S,T); Replace(S,T,V); StrInsert(S,pos,T);StrDelete(S,pos,len)
第5章 数组和广义表
1、数组的逻辑结构。
2、地址计算：对称矩阵、对角矩阵、三角矩阵中元素aij的地址计算。 3、稀疏矩阵、三元组的概念，稀疏矩阵的存储（三元组顺序表） 4、广义表的概念、基本运算（取表头、取表尾）
第6章 树（结点间一对多的关系）
1、树的定义。
2、树的表示（4种）和基本术语：结点的度、树的度、路径、祖先、子孙、父结点、孩子结点、层次、树的深度。 3、二叉树
（1）定义；3个结点的二叉树形态（5种）；二叉树的5个性质（其中性质3要求会推导）。 （2）满二叉树和完全二叉树的概念、特性。
（3）二叉树的存储：顺序存储结构和链式存储结构（要求会画结构）。
（4）二叉树的前、中、后序遍历：会进行遍历，另外要求如下：①链式存储结构描述；②算法思想；③算法代码（c语言描述）。
（5）二叉树线索化：给出一棵二叉树，会进行前、中、后序线索化，会画出线索二叉链表。 4、树
（1）存储（孩子兄弟表示法）。
（2）树、森林和二叉树的相互转换。 5、哈夫曼树
（1）最优二叉树（哈夫曼树）、前缀码的定义 （2）哈夫曼编码及性能分析
第7章 图（结点间多对多的关系）
1、图的基本概念：有向图、无向图、完全图、子图、路径、连通图、连通分量、强连通图、强连通分量、生成树。
2、图的存储结构：数组表示法（即邻接矩阵）、邻接表。（要求会画） 3、图的遍历
（1）遍历的定义。
（2）深度优先遍历（类似于树的先根遍历）和广度优先遍历（类似于树的按层次遍历）：要求会写出遍历序列，能画出其生成树。 4、最小生成树 （1）定义。
（2）能用普里姆算法和克鲁斯卡尔算法生成最小生成树。 5、最短路径：要求能用迪杰斯特拉算法求出单源最短路径。
第9章 查找
1、查找表定义、静态查找表和动态查找表定义。 2、具体查找方法要求：
第10章 排序
1、排序过程的两种基本操作： （1）比较两个关键字的大小；（2）将记录从一个位置移动至另一个位置。 2、具体排序算法要求：
直接插入排序：排序过程。最好情况、最差情况、平均时间复杂度。稳定性。插入排序内部排序交换排序排序过程。平均时间复杂度。稳定性。希尔排序：冒泡排序：排序过程。最好情况、最差情况、平均时间复杂度。稳定性。排序过程。最好情况、最差情况、平均时间复杂度。稳定性。快速排序：
3、选择排序
直接选择排序：排序过程、最好情况、最差情况、平均时间复杂度、稳定性。
