数据结构总复习2013-2014-1

《数据结构总复习2013-2014-1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章绪论一.基本概念和术语数据结构是一门研究非数值计算的程序设计问题屮计算机的操作对象以及它们之间的关系和操作等的学科。术语：数据、数据元素、数据对彖、数据结构、抽彖数据类型、算法。数据结构的形式定义（二元组）数据的逻辑结构:（四类基本结构）线性结构、树型结构、图状结构、集合它们各自的特性？数据的存储结构（物理结构）：主要冇顺序存储结构（以存储地址相邻来表示逻辑上的相邻关系），链式存储结构（用指针来指示逻辑上的相邻关系）抽象数据类空（三元组）算法的定义，算法的5个重要特性。二.算法的时间复杂度和空间复杂度算法的评价：正确性、可

2、读性、健壮性、高效率、低存储量求语旬频度、时间复杂度第二章线性表线性表的定义线性结构的特点二.线性表的存储结构1.顺序存储结构（顺序表人随机存取插入/删除元素时，需移动元素的次数。2.链式存储结构（链表，分为单（向）链表、双（向）链表）：非随机存取（顺序存取）带头结点的链表和不带头结点的链表；循环/非循环的链表；链表空与非空的情况（判断条件）。3.两种存储结构的优缺点比较，各适合那些场合。三.线性表操作的实现（算法描述）插入元索、删除元索、查找、判表是否满足某种特性、逆置等。例：判断题：1.线性表的逻辑顺序与存储顺序总是一致的。

3、2.线性结构的基本特征是：每个结点有且仅有一个总接前驱和一个直接后继。3.线性表的链式存储结构优于顺序存储结构。选择题：线性表L在（）情况下适于使用链表结构实现。A.不需修改L的结构B.需不断对L进行删除、插入C.需经常修改L中结点值D.L中含有大量结点填空题：1•对于顺序表，在笫i个元素前插入一个元素需移动个元素，要删除第i个元素，需移动个元素。2.在双向循坏链表中某结点（由指针p指示）之后插入s指针所指结点的操作是:第三章栈和队列一.栈1.栈的定义、特点（后进先出）2.栈的存储结构：顺序存储结构链式存储结构3.栈的应用：二叉

4、树的先序、中序、后序遍历算法图的深度优先遍历算法（将递归算法改写为非递归算法可借助栈来完成；递归算法的执行需用栈來实现。）二.队列1.队列的定义、特点（先进先出）2.队列的存储结构：顺序存储结构（循环队列），链式存储结构3.队列的应用：二义树层序遍历算法图的广度优先遍历算法4.循环队列：・队空、队满的判断条件・求队列的长度例：判断题：因为栈是特殊的线性表，所以对线性表的所有操作都可以用于对栈操作。填空题：循环队列队满的条件是O第五章数组和广义表第六章树和二叉树一.树、二叉树的定义二.二叉树1.二叉树的性质（5条）2.二叉树的存储

5、结构：顺序存储结构（按完全二叉树层序存放）链式存储结构（二义链表、三义链表）（空链域的个数）3.遍历二义树：先序、中序、后序、层序应用：给定二叉树的先序和中序（或后序和中序）序列，画出相应的二叉树。三.树和森林1.树的存储结构：双亲表示法孩子表示法孩子■兄弟（二叉树）表示法1.树（森林）与二叉树的相互转换2.树的遍历：先根、后根次序遍历3.森林的遍历：先序、中序遍历一.赫夫曼树及其应用1.构造最优二叉树（赫夫曼树），求WPL2.赫夫曼编码五.各种二叉树概念的区分1.满二叉树（若深度为k,结点数？）2.完全二叉树（若深度为k,结点

6、数至多、至少？）3.正则二叉树（严格二叉树）（若深度为k,结点数至多、至少？）4.最优二叉树5.（折半查找的）判定树6.二义排序（二义查找树）树7.平衡二叉树8.堆六.二叉树有关的递归算法例：判断题：1.已知二叉树的先序序列和后序序列并不能唯一地确定这棵二叉树，因为不知道二叉树的根结点是哪一个。2.一般二叉树的第i层上有2曰个结点，深度为k的二叉树2k-l个结点。选择题：1.下列二义树中，（）可用于实现符号不等长高效编码。A.最优二叉树B.二叉查找树C.平衡二叉树D.二叉排序树2.结点数为n的二叉树高度至多为（）。A.不定B.n

7、C.Llog2nJ+lD.Iog2n填空题：1・将满/完全二叉树（含n个结点）屮各结点从上到下，从左到右进行编号（根结点编号为1）,则编号为i的结点，其双亲编号为,其左孩子编号为，其右孩子编号为o2.対树的遍历有先根次序遍历树和后根次序遍历树。若以二叉链表作树的存储结构,则树的先根遍历可借卅二义树的遍历算法來实现,而树的后根遍历可借用二叉树的遍历算法来实现。应用题：1.已知某二叉树的先序遍历序列是ABCDEFGHI,中序遍历序列是BDCEAGHH,画出该二叉树。2.以数据集（4,5,6,7,10,12,18）为叶结点权值，构造一

8、棵赫夫曼树，给出每个叶了的赫夫曼编码，并求具带权路径长度。第七章图图的定义和术语!1!五.例:无向图、冇向图、（无向/冇向）完全图、了图、（强）连通图、（强）连通分屋、生成树图的存储结构无向图（或网）：邻接矩阵、邻接表有向图（或网）：邻接矩阵、邻接表、逆邻接表图