数据结构复习资料.doc

数据结构的定义 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据结构：是指数据以及数据元素相互之间的联系,可以看作是相互之间存在着某种特定关系的数据元素的集合。 对数据结构的内容包括以下几个方面： 数据的逻辑结构，指数据元素之间的逻辑关系。 数据的存储结构，指数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构。 数据运算，指施加在数据上的操作。 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中，每一条指令表示一个或多个操作。 粗略地说，算法是为了求解问题而给出的一个指令序列，程序是算法的一种具体实现。 一个算法必须满足以下五个重要特性：1. 有穷性 2. 确定性 3. 可行性 4. 有输入 5. 有输出算法的重要特征(1) 有穷性: 算法在有穷步之后结束，每一步在有穷时间内完成。(2) 确定性: 算法中的每一条指令有明确的含义，无二义性。 (3) 可行性: 可通过已经实现的基本运算执行有限次来实现算法中的所有操作。 算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。算法的执行时间主要与问题的规模有关。问题规模是一个与输入有关的量。语句频度是指算法中该语句被重复执行的次数。算法中所有语句的频度之和记作(n)，是该算法所求解问题规模的函数。当问题规模趋向无穷大时，(n)的数量级称为渐进时间复杂度，简称时间复杂度，记作(n)=O(f(n)。 通常采用算法中表示基本运算的语句的频度来分析算法的时间复杂度。 例题：1. 数据结构中的逻辑结构是指()，物理结构是指（）。2. 算法的基本特征包括有穷性、( )、( )、有输入和输出 。3. 算法的有穷性是指（）。4. 算法的确定性是指（）。5. 算法的可行性是指（）。6. 算法分析的两个主要方面是分析算法的（）和空间复杂度。7. 语句频度是指（ 算法中该语句被重复执行的次数 ）。 8. 设n为正整数，对下面的程序段，写出语句、的频度及该程序段的时间复杂度。 for (i=1; i =n; i+) s=0; n for (j=1; j next; if (p) s = p-next;p-next = NULL; p = s;s = s -next;p-next = head - next;head - next = p;p = s;s = s -next;p-next = head - next;head - next = p;F 将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分。F 设置两个指针p和s，p指向已完成逆置部分链表的第一个结点，s指向未逆置部分的第一个结点。F 初始时令指针p指向第一个元素结点，s指向p所指结点的后继。将第一个元素结点的指针域置为空。F 将未逆置部分的结点逐个插入到头结点之后。算法：void reverse(LinkList head) /带头结点的单链表逆置 p = head-next; if (!p) return; s = p-next; p-next = NULL; while (s) p = s; s = s - next; p - next = head - next; head-next = p; 第三章 栈和队列F 栈是后进先出的线性表，队列是先进先出的线性表；F 在应用中，栈和队列都是容器，因此需要判断是否“栈空”或“队空”；F 采用顺序存储结构时，栈和队列都可能存在“溢出”问题，分别称为“栈满”、“队满”；F 采用顺序结构的队列常见形式是循环队列。F 栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA 。 例题1. 用S、X分别表示入栈、出栈操作，若元素入栈顺序为1、2、3、4，为得到出栈序列1、3、4、2，则相应的S和X操作串是（ SXSSXSXX ）。2. 若push、pop分别表示入栈、出栈操作，初始栈为空且元素a、b、c依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为( b a c )。 3. 如果进栈的序列为1、2、3, 则不能得到的出栈序列为（ 3 1 2 ）。 令队列空间中的一个单元闲置，使得在任何时刻，保持Q.rear和Q.front之间至少间隔一个空闲单元 MAXSIZE=8 F 队列满(full)： (Q.rear+1)%MAXSIZE = Q.front F 队列空： Q.rear=Q.front F 队列长度： (Q.rear - Q.front+ MAXSIZE)% MAXSIZE例题1. 在循环队列结构中（队列空间容量为M），.rear指向队尾元素所在位置，.front指向队头元素所在位置，则队列的长度为( (Q.rear - Q.front + 1 + M) % M )。2. 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ O(1) ）和（O(n)）；若只设尾指针，则出队和入队的时间复杂度分别是（O(1)）和（O(1)）。1. 若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。 #define MAXSIZE 100 /最大队列长度 typedef struct Qelemtype *base; /base为队列所在存储区域的首地址 int length; /队列长度 int rear; /队尾元素位置 SqQueue；1. 若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。 #define MAXSIZE 100 /最大队列长度 typedef struct Qelemtype *base; /base为队列所在存储区域的首地址 int length,rear; /队列长度和队尾元素位置 SqQueue； Status EnQueue（SqQueue &Q, Qelemtype e） /将元素e插入队列Q if（ （1） ） return ERROR；/队列满，无法插入 Q.rear （2） ; /计算元素e的插入位置 （3） e; /在队尾加入新的元素 Q.length+； /队列长度加1 return OK; / (1) Q.length MAXSIZE (2) （Q .rear + 1） MAXSIZE (3) Q.baseQ .rear 第四章 串1. 了解串的基本运算2. 了解串的模式匹配算法第六章 树和二叉树二叉树或者是一棵空树；或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成 满二叉树中所有分支结点都有左孩子和右孩子， 叶结点都集中在二叉树的最后一层。满二叉树结点的编号：从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。 完全二叉树中，最多只有最下面两层的结点的度数可以小于2，最下面一层的叶结点都排列在该层最左边的位置上。完全二叉树结点的编号：从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。例题1. 一棵满二叉树中共有n个结点，其中有m个叶子结点，则n和m的关系为（ n=2m-1 ）。 2. 在完全二叉树中，若一个结点没有左孩子子结点，则它一定没有( B )。 A父结点 B右孩子结点 C左兄弟结点 D右兄弟结点性质1 非空二叉树上第i层上至多有2i-1个结点i1。性质2 高度为h的二叉树至多有2h-1个结点(h1)。性质3 非空二叉树上叶结点数(度为0)等于双分支结点数(度为2)加1。 性质4 对完全二叉树中编号为i的结点(1in，n1，n为结点数)，可以算出其左孩子结点、右孩子结点和父结点的编号（若这些结点存在）。 性质5 具有n个(n0)结点的完全二叉树的高度为log2 (n+1) 或 log2n+1。F 二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系.F 一般用二叉链表存储二叉树(每个结点有两个指针域)F 树的遍历是访问树中每个结点仅一次的过程。可以认为遍历是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。F 先序遍历DLR、中序遍历LDR、后序遍历LRDF 层序遍历F 先序遍历DLR：访问根结点、先序遍历左子树、先序遍历右子树F 中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树F 后序遍历LRD：后序遍历左子树、后序遍历右子树、访问根结点F 先序遍历：访问根结点、先序遍历左子树、先序遍历右子树。下图的先序遍历序列为A B D E G C F。F 中序遍历：中序遍历左子树、访问根结点、中序遍历右子树。下图的中序遍历序列为D B G E A C F。F 后序遍历：后序遍历左子树、后序遍历右子树、访问根结点。下图的后序遍历序列为D G E B F C A。F 层序遍历：先根后子树、先左子树后右子树。下图的层序遍历序列为A B C D E F G。例题1. 在有n个结点的二叉树的二叉链表中必定存在（n+1）个空链域。2. 前序遍历序列与中序遍历序列相同的二叉树为（ D ）。 A. 根结点无左子树的二叉树 B. 根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树 3. 已知一棵二叉树的先序遍历序列为ABDGCEF，中序遍历序列为DGBAECF，画出此二叉树。树（森林）采用孩子兄弟链存储结构。可以将一棵树或一个森林转换为一棵二叉树，反之亦然。 树的孩子兄弟链存储结构是指在一个结点中既指出当前结点的第一个孩子，也指示出当前结点的兄弟。下图(a)的树对应的孩子兄弟链存储结构如图(b)所示。森林转换为二叉树的过程：左指针：父子关系 右指针：兄弟关系线索二叉树F 对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域，又由于只有n-1个结点被有效指针所指向（n个结点中只有树根结点没有被有效指针域所指向），则共有2n-(n-1)=n+1个空链域。遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这些指向结点在某种遍历序列中的“前驱”和“后继”的指针，称作线索哈夫曼树F 哈夫曼树（或最优二叉树）是一类带权路径长度最短的树，这种树的叶子结点带有权值。F 路径和路径长度 从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。F 结点的带权路径长度 从根到该结点的路径长度与该结点权的乘积称为结点的带权路径长度F 树的带权路径长度 树中所有叶子的带权路径长度之和称为树的带权路径长度，记作 树的带权路径长度 WPL = 7*2+5*2+2*2+4*2 = 36 WPL= 4*2 + 7*3 +5*3 + 2*1 = 46F 设有四个叶子a、b、c和d的二叉树中，对应的权值分别为7、5、2和4，构造哈夫曼树。练习题1. 设n为某棵哈夫曼树的叶子结点数目，则该哈夫曼树共有（ 2n-1 ）个结点。2. 已知组成电文的字符集D及其概率分布W 为： D=a,b,c,d,e W=0.25, 0.30, 0.12, 0.25，0.08 用哈夫曼算法为该字符集中的字符编码，画出哈夫曼树。 1. 二叉树第i层上的结点数目最多为（ 2i-1 ）。2. 在n个结点的线索二叉树中，线索的数目是（ n+1 ）。3. 假设二叉树中所有非叶子结点都有左、右子树，则对有m个叶子结点的此类二叉树，结点总数为（ 2m-1 ）。4. 已知二叉树T的后序遍历序列和中序遍历序列分别为H C D F I G B A E和D H C E F B G I A。 （1）试画出二叉树T； （2）画出与二叉树T对应的中序线索二叉树； （3）画出与该二叉树对应的树（森林）。第七章图存储1. 邻接矩阵 顶点之间相邻关系用矩阵表示。1. 邻接矩阵 顶点之间相邻关系用矩阵表示。2. 邻接链表 顶点：通常按编号顺序将顶点数据存储在一维数组中关联同一顶点的边：用线性链表存储 F 从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。F 遍历方法:深度优先遍历和广度优先遍历F 生成树 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。 F 生成树的代价等于其边上的权值之和，我们把具有权值最小的生成树称为最小生成树。F 普里姆算法和克鲁斯卡尔算法是两种常用的构造最小生成树的方法。q 拓扑排序方法：1) 在有向图中选一个无前趋的顶点v，输出之；2) 从有向图中删除v及以v为尾的弧；3) 重复1)、2)，直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。最短路径问题 1. 单源点最短路径问题：从一个顶点到其余各顶点的最短路径(迪杰斯特拉算法) 2. 每一对顶点间的最短路径问题(弗洛伊德算法) 问题：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。 迪杰斯特拉算法以路径长度递增的方式解单源点最短路径问题。 例题1. 对于有n个顶点的完全无向图，其边数e等于（ n(n-1)/2 ）。2. 一个连通图的生成树是一个（ 极小 ）连通子图，n个顶点的生成树有（ n-1 ）条边。 3. 假设含n个结点的无向图形成一个环，则它的生成树为（n）个。4. 单源最短路径的Dijkstra算法是按路径长度（路经长度递增的次序）依次求解的。5. 在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是（ m/2 ）条。6. 已知一赋权有向图如下： 1. 写出该图的邻接矩阵表示并据此给出从顶点v1出发的深度优先遍历序列； 2. 说明该有向图是否强连通； 3. 给出该图的两个拓扑序列； 4. 若将该图视为无向图，用克鲁斯卡尔算法求最小生成树l 已知一赋权有向图如下： 1. 写出该图的邻接矩阵表示并据此给出从顶点v1出发的深度优先遍历序列； 2. 说明该有向图是否强连通；深度优先遍历序列：v1 v2 v3 v5 v7 v4 v6该图不是强连通图，例如，存在v1至v2的路径，反之则没有。第9章 查找二分查找(折半查找)q 折半查找判定树是描述折半查找过程的二叉树若有序顺序表为：a1a2a3a4a5a6a7a8 则其判定树（(low+high)/2）如下： q 二分查找判定树:描述二分查找过程的二叉树F 若有序顺序表为：a1a2a3a4a5a6a7key=key) return bt; else if (key key) return BSTSearch (bt-lchild, key); else return BSTSearch (bt-rchild, key);/BSTSearch 二叉排序树的查找性能分析F 若查找成功，则走了一条从根结点到某结点的路径，若查找失败，则走到一棵空的子树时为止。因此，最坏情况下，其平均查找长度不会超过树的高度。二叉排序树的构造平衡二叉树四种平衡处理F 在平衡二叉排序树上插入结点时，其祖先结点的平衡因子可能发生变化，离插入结点最近且平衡因子变为2或-2的祖先结点作为根的子树称为最小不平衡子树。F 一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a，则失去平衡后进行调整的规律可归纳为以下四种情况：RR型左旋平衡处理LL型右旋平衡处理LR型先左后右旋转平衡处理RL型先右后左旋转平衡处理哈希表查找F 一个散列结构是一块地址连续的存储空间，它与一个称为散列（哈希）函数的函数相关联，该函数是数据记录的关键字到地址空间的映射。 Hash：关键字 哈希地址F 这种存储空间的使用方式，使得(1) 存储记录时，通过散列函数计算出记录的存储位置并按此存储位置存储记录 记录位置 Hash(记录的关键字) (2)访问记录时，同样利用散列函数计算存储位置，然后根据所计算出的存储位置访问记录F 散列技术中的主要问题 表面上看，设置了散列函数后，只需作简单的函数计算就可以实现元素的定位及查找操作，但事实上没有这么简单，概括起来，主要有以下两个问题：(1) 冲突及解决 一般情况下，设计出的散列函数很难是单射的，即不同的关键字会对应到同一个存储位置，这样就造成了冲突(碰撞)。此时，发生冲突的关键字互为同义词。(2)散列函数的设计 设计一个简单、均匀、存储空间利用率高、冲突少的散列函数是关键。构造哈希函数的常用方法1直接定址法2数字分析法3平方取中法4折叠法5除留余数法 该方法的散列函数形式为： Hash(key) = key % p其中，p为不大于散列表表长m的整数6. 随机法 常用的冲突解决方法1 开放地址法开放定址法利用下列公式求“下一个”空地址 Hi = (H(key)+di) MOD m i=1,2,K(K=m-1) 其中H(key)为散列函数，m为散列表长度，di为增量序列根据di的取法，解决冲突时常使用下面一些方法：(1) 线性探测再散列(2) 二次探测再散列(3) 伪随机探测再散列假设哈希表的地址为0m-1，则哈希表的长度为m。若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，当达到表尾m-1时，又从0，1，2，.开始探查，直到找到一个空闲位置来存储冲突的关键字，将这一种方法称为线性探测再散列。 Hi = (H(key)+di) MOD m i = 1,2,k (km-1) 其中，H(key)为关键字key的哈希函数值，di=1,2,3,m-1例如: 给定关键字序列如下，散列函数为H(k)=k%13 19，14，23，1，68，20，84，27，55，11，10，79试用线性探测再散列法建立散列表。2 链地址法例题1. 对于查找算法来说, 通常以（ 平均查找长度 ）作为衡量查找算法好坏的依据.2. 在关键字序列为（5 , 10, 19 , 21 , 28 , 34 , 41，53 , 58 ,65）的顺序表中，用折半法查找关键字为5的记录（mid（lowhigh）DIV 2），需要经过（ 3 ）次比较。3. 对二叉排序树进行（中序）遍历，可将树中结点按关键字值进行升序排列。4. 在平衡二叉树中，任意结点的左、右子树的高度之差为（ -1、0、1 ）。 第十章 排序例题1. 排序方法的稳定性是指（ ）。 2. 对于直接插入排序, 当待排序列中记录按关键字（ 有序 ）排列时, 所需进行关键字间比较的次数达最小值n-1, 记录不需移动。 3. 将两个长度分别为m和n的有序表归并成一个有序表（ m n），需要的元素比较次数最少为（ m ）。 4. 快速排序在（ 元素有序 ）的情况下排序性能最差。 5. 每趟排序都是从未排序的子序列中依次取出元素与已经排好序的序列中元素进行比较，然后将其放在已经排好序的序列的合适位置。这种排序法称为（直接插入）排序法。 6. 希尔排序、快速排序、堆排序和二路归并排序法中，要求辅助空间最多的是（二路归并排序）。7. 在希尔排序、冒泡排序、选择排序、直接插入排序、快速排序、基数排序等方法中，关键字比较的次数与记录的初始排列次序无关的排序方法是（选择排序、基数排序）。8. 设有序列（503，87，512，61，908，170，897） （1）写出增量为3时进行一趟希尔排序的结果； （2）建成一个小顶堆； （3）给出执行一趟快速排序的结果； （4）写出进行3路归并排序的过程。 术语解释 数据结构 逻辑结构 存储结构 头结点 头指针 单链表 栈 队列 哈夫曼树 最小生成树 AOV网 拓扑排序 AOE网 关键路径 平均查找长度 二叉排序树 哈希表