图练习：1．图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。A．0B．1C．n-1D．n7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．48.下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程9．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b10.关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路1.A2.B3.A4.B5.D6.1B6.2D7.1B7.2C8C9D10A二、判断题1.树中的结点和图中的顶点就是指数据结构中的数据元素。（）2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=。（）4.有e条边的无向图，在邻接表中有e个结点。（）5.有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）6．强连通图的各顶点间均可达。（）7．邻接多重表是无向图和有向图的链式存储结构。（）8.十字链表是无向图的一种存储结构。（）9．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）10．有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。（）11.有向图的邻接矩阵是对称的。（）12．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）13.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）14.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）15.广度遍历生成树描述了从起点到各顶点的最短路径。（）16．任何无向图都存在生成树。（）17.不同的求最小生成树的方法最后得到的生成树是相同的.（）18．带权无向图的最小生成树必是唯一的。（）19.最小代价生成树是唯一的。（）20．一个网（带权图）都有唯一的最小生成树。（）21．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）22．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（）23．带权的连通无向图的最小代价生成树是唯一的。（）24.最小生成树问题是构造连通网的最小代价生成树。（）1.√2.×3.×4.×5.×6.√7×8×9.×10.√11×12.×13.×14.√15.×16.×17.×18.×19.×20.×21.√22.×23×24√三、填空题1.判断一个无向图是一棵树的条件是______。2．有向图G的强连通分量是指______。3．一个连通图的______是一个极小连通子图。4．具有10个顶点的无向图，边的总数最多为______。5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。6.设无向图G有n个顶点和e条边，每个顶点Vi的度为di（1<=i<=n〉，则e=______7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。8.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。9．在有n个顶点的有向图中，每个顶点的度最大可达______。10．设G为具有N个顶点的无向连通图，则G中至少有______条边。11．n个顶点的连通无向图，其边的条数至少为______。12．如果含n个顶点的图形形成一个环，则它有______棵...
