数据结构(严蔚敏C语言版)学习复习提纲.docVIP

期末复习 第一章 绪论 复习 1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。 2、算法分析的两个主要方面是空间复杂度和时间复杂度。 3、数据元素是数据的基本单位。 4、数据项是数据的最小单位。 5、数据结构是带结构的数据元素的集合。 6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。 第二章 线性表 复习 1、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 、一个指向后继结点的指针 2、线性表采用顺序存储，必须占用一片连续的存储单元 3、线性表采用链式存储，便于进行插入和删除操作 4、线性表采用顺序存储和链式存储优缺点比较。 5、简单算法 第三章 栈和队列 复习 栈和队列的异同点。 栈和队列的基本运算 出栈和出队 基本运算 第四章 串 复习 第五章 数组和广义表 复习 第六章 树 复习 1、三个结点可以组成2种不同形态的树。 2、一个稀疏矩阵Am*n采用三元组形式表示，若完成了其的转置运算要经过哪几步: 矩阵的行、列数值互换 、矩阵元素所在行列值互换、元素在矩阵中排列的位置）重新排列 3、若二叉树中每一层结点的个数都达到了最大，则称为一棵满二叉树。 4、树最适合用来表示现有元素之间具有分支层次关系的数据 5、哈夫曼树是带权路径长度最小的二叉树。 6、以下那些项为用十字链表表示的稀疏矩阵元素结点信息元素所在行和列 、元素的值 、指向该元素所在行的下一个元素的指针 、指向该元素所在列的下一个元素的指针。 7、一个广义表可以为其它广义表所共享。 8、广义表可以是一个多层次的结构。 9、压缩存储的三角矩阵和对称矩阵的存储空间相同。 10、广义表中的元素类型可以不相同。 11、两个稀疏矩阵的和仍为稀疏矩阵。 12、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。 13、对于一棵具有n个节点的树，该树中所有节点的度数之和为n-1。 14、树和森林的遍历中有中序遍历。 15、二叉树用链式存储时，空链域数多于非空链域数。 16、由森林转换成二叉树，其根节点的右子树总是空的。 17、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 18、当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。x 19、某二叉树的先序遍历序列和中序遍历序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树。 20、某二叉树的先序遍历序列和后序遍历序列相同的二叉树为空树或仅有一个结点的非空二叉树。 21、某二叉树的后序遍历序列和中序遍历序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树。x 22、某二叉树的先序遍历序列和后序遍历序列相反的二叉树为高度等于结点数的二叉树。 满二叉树就是除叶子结点外的任何结点均有两个孩子结点，且所有的叶子结点都在同一层上的二叉树。 23、用一维数组存放二叉树时，总是以前序遍历存储结点，这是错误的说法　 24、在度为k的树中，至少有一个度为k的结点。 25、在非空完全二叉树中，只有最下面一层的结点为叶结点。 26、在完全二叉树中，没有左孩子的结点一定是叶子结点。 27、 特殊矩阵主要形式有对称矩阵、上三角矩阵、下三角矩阵、对角矩阵 28、在结点数目一定的前提下，各种形态的二叉树中，完全二叉树具有最小深度。 29、在所有深度相同的二叉树中，满二叉树具有最大结点数目。 30、给定一组权值，构造出来的哈夫曼树是不惟一的。 31、哈夫曼树中不存在度为1的结点。 32、线索二叉树中的每个结点通常包含有5个数据成员。 33、判断两个串相等的充分必要条件有两个:两个串的长度相等;两个串上对应位置的字符相同 34、下列哪些是广义表的特性:层次性 、共享性 、递归性 35、稀疏矩阵元素的三元组表示的项:元素所在行 、元素所在列 、元素的值 第七章 图 复习 1、强连通分量是有向图的极大连通子图。连通分量指的是无向图中的极大连通子图。 2、在一个图中，所有顶点的度数之和等于图的边数的2倍。 5、最小生成树只能是带权连通图的运算。 6、一个有向无环图的拓扑排序的序列是不唯一的。 7、一个图的邻接矩阵表示法是惟一的。一个图的邻接表表示法是不惟一的。 8、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。若一个有向图中存在回路，则该图的拓扑有序序列不存在。 9、用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关，与顶点数有关。 10、有n个顶点的无向图, 采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。 11、邻接表中边结点数目为奇数的图一定是有向图。 12、不同的求最小生成树的方法最后得到的生成树是不一定相同的。 13、在一个图中，所有顶点的度数之和等于图的