《数据结构》复习提纲。
第一章绪论。
1） 数据结构概念。
2） 数据的物理结构（存储结构）、逻辑结构。
3） 数据的存储形式：顺序、链式、索引、散列存储结构。
4） 算法设计时，重点考虑时间复杂度、空间复杂度、稳定性。
第二章线性表。
1） 抽象数据类型线性表的定义（p19）：
2） 顺序表（基本操作：插入、删除数据元素）
1 数据元素存储位置、新结点的创建。
2 插入/删除一个数据元素时需移动元素的次数
3） 链表（基本操作：插入、删除数据元素）
1 单链表。
2 双链表。
3 链表的定义、创建、插入、删除操作的算法实现。
4 链结束的条件。
5 顺序表与链表的存储区别与联系。
第三章栈和队列。
1） 栈。1 栈的概念。
2 栈的特点：后进先出，插入和删除只能在栈顶。
3 栈的基本操作（p45）
4 栈的算法表示和实现。
5 栈的链式存储。
2） 队列。
1 队列的概念。
2 队列的特点：先进先出，插入在队尾，删除在队头。
3 队列的基本操作（p59）
4 队列的顺序、链式表示和实现（p60 63）
5 队列的“空”与“满”的判别条件。
第四章串和数组。
1） 串。1 串的字串、主串、字串的定义及位置、基本操作（p70）
2 两个串相等的判别条件：两串的长度相等，且对应的字符也相同。
3 求顺序串的子串、串相等判别、合并串。
4 串的顺序存储、链式存储。
2） 数组。
1 数组的顺序存储。
二维数组的存储。
以此类推多维数组的存储。
2 二维数组的基本操作。
a. 给定一组下标，修改该位置元素内容：assign(a,item,index1,index2)
b. 给定一组下标，返回该位置元素内容：value(a,item,index1,index2)
3 一般数组只使用顺序存储结构，不使用链式存储结构。（无插入、删除操作）
3） 矩阵的压缩存储。
1 特殊矩阵的存储。
a. 对称矩阵
b. 下（上）三角矩阵。
c. 对角矩阵。
矩阵中（i,j）在一维数组中存放位置、算法实现（见本章课件）
2 稀疏矩阵的压缩存储---三元组表示法。
三元（i,j,value）即（行号，列号，非零元素值）、算法实现（见本章课件）
第五章树和二叉树。
1） 树。1 树的基本操作（p119）
2 树的度与深度的概念、区别。
2） 二叉树。
1 二叉树概念、基本操作（p121）
2 二叉树的性质：
a. 在二叉树的第i层上至多有2i-1个结点（i≥1）
b. 深度为k的二叉树至多有2k-1个结点（k≥1）
c. 对任一棵二叉树t，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1
d. 具有n个结点的完全二叉树的深度为「log2n」+1
e. 如果对一棵有n个结点的完全二叉树(深度为「log2n」+1)的结点按层序号(从第1层到第「log2n」+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：
<1>如果i=1，则结点i是树根，无双亲；如果i>1，则其双亲是结点「i/2」
<2>如果2i>n，则结点i无左孩子(i为叶子结点)；否则其左孩子是结点2i
3>如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1
3 二叉树的存储结构
4 多维链式存储结构。
5 满二叉树和完全二叉树的概念。
6 二叉树结点总数的计算：
结点总数n=n0+n1+n2 n=n1+2n2+1 （推导过程见p124）
（n0为叶子结点数，n1为度为1的结点数，n2为度为2的结点数）
7 二叉树的遍历递归算法（具体实现算法见本章课件）：
<1>先序遍历---先序遍历左→先序遍历右。
<2>中序遍历---中序遍历左→访问根结点→中序遍历右。
<3>后续遍历---后续遍历左→后续遍历右→访问根结点。
二叉树的遍历与栈、队列的结合。
8 由各种遍历输出序列还原二叉树。
9 赫夫曼树。
<1>树的带权路径长度。
<2>赫夫曼树(最优树)--带权路径长度最短的树。
<3>赫夫曼编码规则、权值的计算。
<4>赫夫曼树的构造原理（过程）
<5>根据赫夫曼前缀编码还原二叉树。
第六章图。1） 有向图、无向图、完全图、有向完全图、入度、出度。
2） 连通图、连通分量→无向图；强连通图、强连通分量→有向图。
3） 图的存储结构：邻接矩阵、邻接表→链式存储结构。
有向图、无向图邻接表 （算法实现见本章课件）
4） 图的遍历（遍历顺序、算法实现）
1 深度优先。
2 广度优先。
5） 最小生成树（构造方法见本章课件）
根据边上的权值计算总权值，总权值最小的树即为最小生成树。
6） 拓扑排序（排序的方法、算法实现见本章课件）
第七章查找。
1） 静态查找（思想、算法见本章课件）
1 顺序表的查找---顺序查找。
2 有序表的查找---折半查找。
3 索引顺序表的概念、查找算法。
4 比较两种查找算法的时间复杂度、空间复杂度、稳定性
2） 动态查找---二叉排序树的性质、查找、插入、删除
3） 哈希表。
1 哈希函数、哈希表、哈希地址、冲突的概念。
2 哈希函数的构造方法—直接定址法、质数取余法、平方取中法、折叠法。
3 解决冲突的方法---开放地址法、链接地址法、再哈希法、溢出区法。
4 哈希表的查找方法、算法。
第八章排序。
1） 内部排序（基本思想、算法）
1 插入排序。
2 希尔排序。
3 交换排序---冒泡排序、快速排序。
4 选择排序---简单选择排序、堆排序。
5 归并排序---2路归并+递归算法。
2） 各种排序算法的优劣，有关时间复杂度、空间复杂度、稳定性问题。
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...