数据结构图

考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。

这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。

n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。

即无向连通图的生成树不是唯一的。

连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。

图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。

最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。

最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。

解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。

他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。

时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。

数据结构数据的逻辑结构
线性表
顺序表静态，动态
字符串
朴素算法
KMP算法
队列
队头：用于插入元素
队尾：用于输出元素
特点：先进先出
举例：排队现象
链表单，双（头节点问题）
栈
特点：后出先进
栈底：栈底以及整个栈里面存放元素
栈顶：用于进出栈
举例：子弹匣
特例：循环队列
队空：(T.front==T.rear
队满：(T.rear+1)%Maxsize==T.fron
树二叉树
数据结构+算法=可执行程序
快速而有效完成预定任务，取决于选对了数据结构
能否清楚而正确地把问题解决，则取决于算法
算法
空间复杂度算法耗费的储存空间
时间复杂度程序运行的大概次数
特点有穷性，正确性，可行性
数据元素的储存
链式添加和删除方便，但占用空间大
顺序储存方便，删除困难。

数据结构流程图数据结构是计算机科学中非常重要的概念之一，它用于描述数据元素之间的关系和存储方式。

而流程图则是一种用于表示算法、操作过程或系统设计的图形化工具。

在计算机科学领域中，流程图常用于描述算法和程序设计过程。

本文将探讨数据结构流程图的相关概念和使用方法。

一、概述数据结构流程图是一种使用标准符号和连线来表示数据结构及其操作的图形化工具。

它包括了各种数据结构的表示方法和基本操作的实现流程。

通过使用数据结构流程图，人们可以清晰地了解数据元素之间的关系以及各种操作的执行过程。

二、符号表示数据结构流程图使用了一系列标准化的符号来表示不同类型的数据结构和操作。

下面是几种常用的符号表示：1. 开始/结束符号：用于表示程序的开始和结束点，通常使用圆角矩形来表示。

2. 输入/输出符号：用于表示输入或输出操作，通常使用矩形或平行四边形来表示。

3. 过程符号：用于表示具体的执行过程，通常使用矩形来表示。

4. 判断符号：用于表示条件分支和判断操作，通常使用菱形来表示。

5. 箭头线：用于表示不同符号之间的流向，表示数据或控制信息的传输方向。

三、使用方法数据结构流程图的使用方法可以分为以下几个步骤：1. 定义数据结构：根据实际需求，确定所需的数据结构类型，例如数组、链表、栈、队列等。

2. 设计算法流程：根据数据结构的特点和需求，设计相应的算法流程，包括数据的插入、删除、查找等操作。

3. 表示数据结构：使用符号表示数据结构及其属性，例如使用方框表示数组，使用箭头表示指针等。

4. 表示算法流程：使用符号表示算法流程，包括条件判断、循环操作、数据的移动等。

5. 绘制流程图：根据之前的设计，将数据结构和算法流程以符号形式绘制在图形界面上，使用箭头线表示数据流向。

6. 调试和改进：通过对流程图的分析和调试，发现问题并进行改进，保证算法的正确性和高效性。

四、实例演示以下是一个使用数据结构流程图描述数组插入操作的示例：思路：1. 输入待插入的元素和插入位置；2. 检查插入位置是否合法；3. 如果合法，将插入位置后的元素依次向后移动一个位置；4. 将待插入的元素放入插入位置处；5. 输出修改后的数组。

十三、左偏树（Leftist Tree）树这个数据结构内容真的很多，上一节所讲的二叉堆，其实就是一颗二叉树，这次讲的左偏树（又叫“左翼堆”），也是树。

二叉堆是个很不错的数据结构，因为它非常便于理解，而且仅仅用了一个数组，不会造成额外空间的浪费，但它有个缺点，那就是很难合并两个二叉堆，对于“合并”，“拆分”这种操作，我觉得最方面的还是依靠指针，改变一下指针的值就可以实现，要是涉及到元素的移动，那就复杂一些了。

左偏树跟二叉堆比起来，就是一棵真正意义上的树了，具有左右指针，所以空间开销上稍微大一点，但却带来了便于合并的便利。

BTW：写了很多很多的程序之后，我发觉“空间换时间”始终是个应该考虑的编程方法。

:)左偏左偏，给人感觉就是左子树的比重比较大了，事实上也差不多，可以这么理解：左边分量重，那一直往右，就一定能最快地找到可以插入元素的节点了。

所以可以这样下个定义：左偏树就是对其任意子树而言，往右到插入点的距离（下面简称为“距离”）始终小于等于往左到插入点的距离，当然了，和二叉堆一样，父节点的值要小于左右子节点的值。

如果节点本身不满，可插入，那距离就为0，再把空节点的距离记为-1，这样我们就得出：父节点的距离= 右子节点距离+ 1，因为右子节点的距离始终是小于等于左子节点距离的。

我把距离的值用蓝色字体标在上图中了。

左偏树并一定平衡，甚至它可以很不平衡，因为它其实也不需要平衡，它只需要像二叉堆那样的功能，再加上合并方便，现在来看左偏树的合并算法，如图：这种算法其实很适合用递归来做，但我还是用了一个循环，其实也差不多。

对于左偏树来说，这个合并操作是最重要最基本的了。

为什么？你看哦：Enqueue，我能不能看作是这个左偏树的root和一个单节点树的合并？而Dequeue，我能不能看作是把root节点取出来，然后合并root的左右子树？事实上就是这样的，我提供的代码就是这样干的。

Conclusion：左偏树比同二叉堆的优点就是方便合并，缺点是编程复杂度略高（也高不去哪），占用空间稍大（其实也大不去哪）。

数据结构图习题习题7 图7.1 单项选择题1．在⼀个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2B. 1C. 2D. 42．任何⼀个⽆向连通图的最⼩⽣成树。

A.只有⼀棵B.有⼀棵或多棵C.⼀定有多棵D.可能不存在3．在⼀个有向图中，所有顶点的⼊度之和等于所有顶点的出度之和的____倍。

A. 1/2B. 1C. 2D. 44．⼀个有n个顶点的⽆向图最多有____条边。

A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的⽆向完全图有____条边。

A. 6B. 12C. 16D. 206．具有6个顶点的⽆向图⾄少应有____条边才能确保是⼀个连通图。

A. 5B. 6C. 7D. 87．在⼀个具有n个顶点的⽆向图中，要连通全部顶点⾄少需要____条边。

A. nB. n+1C. n-1D. n/28．对于⼀个具有n个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵的⼤⼩是____。

A. nB. (n-1)2C. n-1D. n29．对于⼀个具有n个顶点和e条边的⽆向图，若采⽤邻接表表⽰，则表头向量的⼤⼩为_①___；所有邻接表中的接点总数是_②___。

①A. n B. n+1 C. n-1 D. n+e②A. e/2 B. e C.2e D. n+e10．已知⼀个图如图7.1所⽰，若从顶点a出发按深度搜索法进⾏遍历，则可能得到的⼀种顶点序列为__①__；按宽度搜索法进⾏遍历，则可能得到的⼀种顶点序列为__②__。

①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b②A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b图 7.1 ⼀个⽆向图11．已知⼀有向图的邻接表存储结构如图7.2所⽰。

⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

一、单选题1、设有5个结点的无向图，该图至少应有_________条边才能确保是一个连通图。

A.7B.8C.6D.5正确答案：A2、设图G=(V,VR)，其中: V={A,B,C,D,G}，VR={(A,C),(A,D),( B,C),(B,D) ,(G,C),(B,G)}，则对应的图形为_________。

A.B.C.D.正确答案：C3、设某有向图中有n个顶点，则该有向图对应的邻接表中有_________个表头结点。

A.n-1B.n+2C.nD.n+1正确答案：C4、在一个无向图中所有顶点的度数之和等于所有边数的_________倍。

A.1B.2C.3D.1/2正确答案：B5、一个无向连通图的生成树是该连通图的_____。

A.极小连通子图B.强连通子图C.连通子图D.极大连通子图正确答案：A6、设某无向图中有n个顶点，则该无向图邻接矩阵的大小是_________。

A.n(n+1)/2B.（n-1）2C. n2D. （n+1）2正确答案：C7、设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi 关联的所有边算法的时间复杂度为_________。

A.O(n2)B.O(n+e）C.O(n*e）正确答案：D8、设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为_________。

A.O(n）B.O(n*e）C.O(n+e）D.O(n2)正确答案：C9、设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下列说法中错误的是_____。

A.G'是G的连通分量B.G'是G的一个无环子图C.G'是G的极小连通子图且V=V'D.G'是G的子图正确答案：A10、设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。

A.7B.6C.5D.8正确答案：B11、 n个顶点的有向图为强连通图时，至少含有________。

数据结构图,查找,内排序的练习及答案数据结构课后练习习题要求：此次练习不要求上交，只是帮助⼤家掌握知识点，便于复习。

第⼋章图⼀．单项选择题（20分）1. 带权有向图G ⽤邻接矩阵A 存储，则Vi 的⼊度等于A 中___D______A. 第i ⾏⾮∞的元素只和B. 第i 列⾮∞的元素之和C. 第i ⾏⾮∞且⾮0的元素之和D. 第i 列⾮∞且⾮0的元素个数2. ⽆向图的邻接矩阵是⼀个___A____A. 对称矩阵B. 零矩阵C. 上三⾓阵D. 对⾓矩阵3. 在⼀个⽆向图中，所有顶点的度之和等于边数的__C____倍A. 1/2B. 1C. 2D. 44. ⼀个有n 个顶点的⽆向图最多有___C____条边。

A. nB. n(n-1)C. n(n-1)/2D.2n5. 对于⼀个具有n 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵⼤⼩是__D_____A. nB. 2)1(?nC. n-1D. 2n6. ⼀个有向图G 的邻接表存储如右图所⽰，现按深度优先搜索遍历，从V1出发，所得到的顶点序列是___B_____。

A. 1，2，3，4，5B. 1，2，3，5，4C. 1，2，4，5，3D. 1，2，5，3，47. 对右图所⽰的⽆向图，从顶点V1开始进⾏深度优先遍历，可得到顶点访问序列__A______（提⽰：可先画出邻居表图再遍历）A. 1 2 4 3 5 7 6B. 1 2 4 3 5 6 7C. 1 2 4 5 6 3 7D. 1 2 3 4 5 6 78. 如果从⽆向图的任⼀顶点出发进⾏⼀次深度优先搜索即可访问所有顶点，则该图⼀定是__B_____A. 完全图B. 连通图C.有回路D. ⼀棵树9. 任何⼀个⽆向连通图___B___最⼩⽣成树（提⽰：注意最⼩⽣成树的定义，此题易错）A. 只有⼀棵B. ⼀棵或多棵C. ⼀定有多棵D.可能不存在11. 若图的邻接矩阵中主对⾓线上的元素全是0，其余元素全是1，则可以断定该图⼀定是_D_____。

第七章 图一、选择题1．图中有关路径的定义是（ ）。

【北方交通大学 2001 一、24 （2分）】A ．由顶点和相邻顶点序偶构成的边所形成的序列B ．由不同顶点所形成的序列C ．由不同边所形成的序列D ．上述定义都不是2．设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n 2【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】【北京航空航天大学 1999 一、7 （2分）】3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。

【浙江大学 1999 四、4 (4分)】A ．n-1B ．nC ．n+1D ．nlogn ；4．要连通具有n 个顶点的有向图，至少需要（ ）条边。

【北京航空航天大学 2000 一、6(2分）】A ．n-lB ．nC ．n+lD ．2n5．n 个结点的完全有向图含有边的数目（ ）。

【中山大学 1998 二、9 （2分）】A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ）6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A ．0B ．1C ．n-1D ．n【北京邮电大学 2000 二、5 （20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

【哈尔滨工业大学 2001 二、3 （2分）】A ．1/2B ．2C ．1D ．48．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。

【中山大学1999一、14】A ．5B ．6C ．8D ．99．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A ．逆拓扑有序B ．拓扑有序C ．无序的 【中科院软件所1998】10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。

第七章 图一、写出如下有向图的邻接矩阵及图中各顶点的入度、出度和度。

【分析】有向图中顶点的度＝顶点的入度＋顶点的出度。

【参考答案】邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******010101000000110 顶点ａ；入度１，出度２，度３；顶点ｂ；入度２，出度１，度３；顶点ｃ；入度１，出度２，度３；顶点ｄ；入度２，出度１，度３；顶点ｅ；入度１，出度１，度２。

二、设如下有向网以邻接表形式存储，画出其存储结构示意图。

【分析】表结点中应含三个域：邻接到顶点的下标域、权值域和指向下一表结点的指针域。

【参考答案】三、写出对如下无向图从顶点ａ出发进行广度优先遍历可能得到的所有遍历序列。

【分析】广度优先遍历中应保证先被访问的顶点的邻接点先于后被访问的顶点的邻接点处理。

图中各顶点间并无必然的先后顺序。

各顶点的邻接点间也并无必然的先后顺序。

【参考答案】ａｂｃｄｅｆｇａｂｄｃｅｇｆａｃｂｄｆｅｇａｃｄｂｆｇｅａｄｂｃｇｅｆａｄｃｂｇｆｅ四、设有无向网如下，写出其邻接矩阵，并在此基础上按普里姆算法求最小生成树。

【分析】【参考答案】邻接矩阵：⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞6456252363794567555553955434最小生成树：五、写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。

【分析】每次输出一个入度为０的顶点。

【参考答案】ａｂｃｄｅｆｇａｂｃｄｆｅｇａｂｃｆｄｅｇ六、设有ＡＯＥ网如下，试求关键路径。

【分析】【参考答案】关键路径１：v1→v2→v5→v7关键路径２：v1→v3→v6→v7七、设有向网如下，用迪杰斯特拉算法求从顶点ａ出发到其余各顶点的最短路径。

【分析】【参考答案】ａｂ：３ａｆ：５ａｆｅ：７ａｆｅｃ：８ａｆｅｃｄ：１０八、编写算法，由依次输入的顶点数、弧数、各顶点信息和各条弧信息建立有向图的邻接表。