大连理工数据结构考试考点.docx

键入文档标题键入文档副标题 年黄薇Microsoft选取日期第一章一名词解释数据：是对客观事物的客观表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：构成数据的基本单位。数据项：数据不可分割的最小单位。数据对象：性质相同的数据元素的集合。数据结构：带结构的数据元素的集合。相互之间存在一种或多种特定关系的数据元素的集合。二数据结构的三个方面：数据的逻辑结构数据的存储结构数据的运算（操作）三抽象数据类型的定义是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型可用（D，S，P）三元组表示。其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。四算法的概念特性原则概念：解决某一特定问题的具体步骤的描述，是指令的有限序列。五大特性：有穷性，确定性，可行性，有零个或多个输入，有一个或多个输出。四大原则：正确性，可读性，健壮性，高效率和低存储量需求。五算法的时间复杂度 对足够大的n，有以下顺序 常见数量级第二章1、顺序线性表与链式线性表的区别对线性表的操作主要有查找，插入和删除三大类。基于时间上的比较查找时，数组是可以随机存取的，因此查找时间复杂度为O(1)，对于链表，每次查找都必须从链表的首结点开始，时间复杂度为O(n)，因此查找速率上，数组是优于线性表的。插入和删除时，数组必须首先采用顺序查找的方式定位相应的数据元素，接下来还需要移动大量的数据元素，而链表在插入和删除时，仅需要先定位数据元素，然后通过简单的指针修改即可完成。这方面链表是优于数组的。基于空间上的比较数组的存储空间是预先静态分配的，虽然在实现过程中可以动态拓展，但是如果线性表的长度变化范围较大，空间在使用过程中会存在大量的闲置空间。链表的内存主要被分配为两部分，一部分存储数据元素，另一部分则存储指针域，因此在线性表数据元素结构简单，且长度变化不大时，可以考虑使用数组。2、链表的操作（插入、删除）1 线性表操作ListInsert(&L, i, e)在单链表中的实现：O(ListLength(L)有序对改变为和因此，在单链表中第i 个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。2 线性表的操作ListDelete (&L, i, &e)在链表中的实现:O(ListLength(L)有序对和改变为在单链表中删除第i 个结点的基本操作为:找到线性表中第i-1个结点p，修改其指向后继的指针。3、链式结构实现一元多项式一般情况下的一元稀疏多项式可写成Pn(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指数为ei的项的非零系数，且 0 e1 e2 1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm，其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。二叉树：或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。2、二叉树的重要特性性质 1 ：在二叉树的第 i 层上至多有2i-1 个结点。 (i1)性质 2 ：深度为 k 的二叉树上至多含 2 k-1 个结点（k1）。性质 3 ：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。性质 4 ：具有 n 个结点的完全二叉树的深度为 log2n +1 。性质5 ：若对含n 个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对于完全二叉树中任意一个编号为i的结点：(1) 若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2) 若2in，则该结点无左孩子，否则，编号为2i 的结点为其左孩子结点；(3) 若2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。3、二叉树的遍历方式二、遍历算法对“二叉树”而言，可以有四种搜索路径：先（根）序遍历-波兰式中（根）序遍历-中缀表示后（根）序遍历-逆波兰式层序遍历先序遍历：A B C D E F中序遍历：B C A D F E后序遍历：C B F E D A层序遍历：A B D C E F4、按给定的表达式建相应二叉树习题一：已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树。5、森林和二叉树的对应及转换设森林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m);二叉树 B =( LBT, Node(root), RBT );由森林转换成二叉树的转换规则为:若F = ，则B = ；否则，由ROOT( T1 )对应得到Node(root)；由(t11, t12, , t1m )对应得到LBT；由(T2, T3, Tn)对应得到RBT。由二叉树转换为森林的转换规则为：若B = ，则F = ；否则，由Node(root)对应得到ROOT( T1)；由LBT对应得到( t11, t12, ，t1m)；由RBT对应得到(T2, T3, , Tn)。由此，树的各种操作均可对应二叉树的操作来完成。应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。6、构造哈夫曼树及编码1 最优二叉树（哈夫曼树）树中结点的路径长度定义为：从根结点到该结点的路径上经过的分支数目。树的路径长度定义为：树中每个结点的路径长度之和。树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和 WPL(T) = Swklk(对所有叶子结点)。带权路径长度最小的二叉树称为最优二叉树，简称为最优树或哈夫曼树。2 如何构造最优树赫夫曼算法(两两合并方法) ：(1)根据给定的n 个权值w1, w2, , wn，构造n 棵独立的二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；(2)在F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(3)从F中删去这两棵树，同时加入刚生成的新树；(4)重复(2)和(3)两步，直至F 中只含一棵树为止。(5)对树中的分支进行编码标注：如果某分支指向左子树，则其编码为0，否则为1；(6)产生所有叶子结点的编码：每个叶子结点的编码为：从根结点到该叶子结点的路径上所有分支的编码的串联（二进制编码）。第七章1、图的概念图的结构定义:图是由一个顶点集V 和一个弧集VR构成的数据结构。 Graph = (V , VR )其中，VR | v,wV 且P(v,w)表示从v 到w 的一条弧，并称v 为弧尾，w 为弧头。谓词 P(v,w) 定义了弧的意义或信息。由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。2、图的存储及遍历一、图的数组(邻接矩阵)存储表示有向图的邻接矩阵一般为非对称矩阵无向图的邻接矩阵一定是对称矩阵二、图的（逆）邻接表存储表示三、 有向图的十字链表存储表示四、无向图的邻接多重表存储表示typedefstructEbox /VisitIf mark; / 访问标记，用于遍历intivex, jvex; /该边依附的两个顶点的位置structEBox*ilink, *jlink; /指向下一条依附于ivex/ jvex的边InfoType*info; / 该边信息指针EBox;3、图的最小生成树算法，两种算法的比较该问题等价于： 构造网的一棵最小（代价）生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。算法一：（普里姆算法） 算法二：（克鲁斯卡尔算法） 普里姆（Prim）算法的基本思想: 取图G=(V, E)中任意一个顶点 v 作为生成树的根（U=v)，之后往生成树上添加新的顶点 w。在添加的顶点 w （wV-U）和已经在生成树上的顶点v （vU） 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。克鲁斯卡尔（Kruskal）算法的基本思想：考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小，但不能出现回路。具体做法:首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。4、图中两点最短路径（源点到任意顶点）迪杰斯特拉算法： 设置辅助数组Dist，其中每个分量Distk 表示当前所求得的从源点到其余各顶点 k 的最短路径。一般情况下，Distk = 或者 = + 。 /求每一对顶点之间的最短路径 /弗洛伊德算法的基本思想是： /从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。上面所述的其它顶点j必定是已求得最短路径且与v0相通的顶点，且顶点j的最短路径中的顶点必然也已求得最短路径。即：从v0到k的最短路径或者是从v0到k（G),或者是中间只经过已求得最短路径的顶点j而到达k的一条路径。 1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）假设已求得最短路径的顶点为u，修改与u相邻的其它各顶点的Distk值若 Distu+G.arcsuk Distk则将 Distk 改为 Distu+G.arcsuk。5、图中关键路径的算法“关键活动”指的是：该