数据结构习题与答案--图

第7章 图一、单选题01、在一个图中，所有顶点的度数之和等于图的边数的 倍。A1/2 B1 C2 D402、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。A1/2 B1 C2 D403、有8个结点的无向图最多有 条边。A14 B28 C56 D11204、有8个结点的无向连通图最少有 条边。A5 B6 C7 D805、有8个结点的有向完全图有 条边。A14 B28 C56 D11206、用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。A栈 B队列 C树 D图07、用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。A栈 B队列 C树 D图08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 。AO(n) BO(e) CO(n+e) DO(n2)09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 。 A0 2 4 3 1 5 6 B0 1 3 6 5 4 2C0 1 3 4 2 5 6 D0 3 6 1 5 4 210、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是 。A0 2 4 3 6 5 1 B0 1 2 3 4 5 6C0 4 2 3 1 5 6 D0 1 3 4 2 5 611、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 。 A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 312、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 。 A0 3 2 1 B0 1 2 3 C0 1 3 2 D0 3 1 213、图的深度优先遍历类似于二叉树的 。A先序遍历 B中序遍历 C后序遍历 D层次遍历14、图的广度优先遍历类似于二叉树的 。A先序遍历 B中序遍历 C后序遍历 D层次遍历15、任何一个无向连通图的最小生成树 。A只有一棵 B一棵或多棵C一定有多棵 D可能不存在( )16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为 ，所有边链表中边结点的总数为 。An、2e Bn、e Cn、n+e D2n、2e17、判断有向图是否存在回路，可以利用 算法。A关键路径 B最短路径的Dijkstra C拓扑排序 D广度优先遍历18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为 。A图中每个顶点的入度 B图中每个顶点的出度C图中弧的条数 D图中连通分量的数目19、求最短路径的Dijkstra算法的时间复杂度是_。AO(n) BO(n+e) CO(n2) DO(n*e)20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为 。AO(n) BO(n+e) CO(n2) DO(n*e)21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 。A第i行非的元素之和B第i列非的元素之和C第i行非且非0的元素个数D第i列非且非0的元素个数22、一个有n个顶点的无向图最多有 条边。An Bn(n-1) Cn(n-1)/2 D2n23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。An B(n-1)2 Cn-1 Dn224、对某个无向图的邻接矩阵来说， 。A第i行上的非零元素个数和第i列的非零元素个数一定相等B矩阵中的非零元素个数等于图中的边数C第i行上，第i列上非零元素总数等于顶点vi的度数D矩阵中非全零行的行数等于图中的顶点数25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 。Aabecdf Bacfebd Caebcfd Daedfcb26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为 。Aabcedf Babcefd Caebcfd Dacfdeb27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1出发得到的顶点序列是 。Av1,v2,v3,v5,v4 Bv1,v2,v3,v4,v5 Cv1,v3,v4,v5,v2 Dv1,v4,v3,v5,v228、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是 。Av1,v2,v3,v4,v5 Bv1,v3,v2,v4,v5Cv1,v2,v3,v5,v4 Dv1,v4,v3,v5,v229、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用 次深度优先遍历算法。Ak B1 Cn-k Dn30、以下不正确的说法是 。A无向图中的极大连通子图称为连通分量B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D有向图的遍历不可采用广度优先搜索方法二、填空题01、在有向图中，以顶点v为终点的边的数目称为v的 。02、含n个顶点的无向连通图中至少含有 条边。03、图的存储结构表示有 、 、十字链表、邻接多重表等多种存储结构。04、遍历图的2种常见方法是 优先遍历和 优先遍历。04、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 。05、如果n个顶点的图是一个环，则它有 棵生成树。06、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。若采用邻接表存储，则空间复杂度为 。07、图的逆邻接表存储结构只适用于 图。08、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 。09、图采用邻接矩阵表示，则计算第i个顶点入度的方法是求 。10、用邻接矩阵表示图时，则判断任意两个顶点vi和vj之间是否有路径相连，只需要检查 即可。11、用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 。12、对稀疏图最好用 算法求最小生成树，对稠密图最好用 算法来求解最小生成树。13、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。14、拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的。15、有向图G用邻接矩阵存储，则第i行的所有元素之和等于顶点i的 。16、有n个顶点的强连通有向图G至少有 条弧。17、设有向图G的邻接矩阵为A，如果图中不存在弧，则Ai,j的值为 。18、在n个顶点的无向图中，若边数n-1，则该图必是连通图，此断言是 的。(正确/错误)19、在有n个顶点的有向图中，每个顶点的度最大可达 。20、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定 。(存在/不存在)三、简答题01、写出下面有向图的所有强连通分量。02、已知图的邻接表如下，画出图G的所有连通分量。03、如下图，分别用普里姆算法和克鲁斯卡尔算法从顶点1开始求最小生成树，写出按次序产生边的序列。说明：边用(i,j)方式表示。04、如下图，写出所有的拓扑序列，并求在添加什么边之后仅可能有惟一的拓扑序列。05、已知如图所示的有向图，请给出该图的:(1) 每个顶点的入/出度；(2) 邻接矩阵；(3) 邻接表；(4) 逆邻接表。06、写出无向带树图的邻接矩阵，并按普里姆算法填写表格中的内容，最后画出最小生成树；VbcDeFghUV-UVexlowcosta4a3AaaaaabcdefghVexlowcostVexlowcostVexlowcostVexlowcostVexlowcostVexLowcostVexlowcost07、写出无向带树图的邻接表，并按克鲁斯卡尔算法写出求最小生成树产生的边序列。08、已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。09、利用Dijkstra算法填写表格求图中从顶点a到其他各顶点间的最短路径，并写出最终结果。终点DistbcDefgS(终点集)k=1k=2k=3k=4k=5k=610、求出下图中从顶点1出发到其余各顶点的最短路径。要求利用表格给出求解过程。11、设图G=(V，E)，V=1，2，3，4，5，6，E=，。画出图G，并写出图G中顶点的所有拓扑序列。12、已知图的邻接表表示的形式说明如下：#define MaxNum 80typedef struct node int adjvex; /邻接点域 struct node *next; /链指针域 EdgeNode; /边表结点结构描述typedef struct char vertex; /顶点域 EdgeNode *firstedge; /边表头指针 VertexNode; /顶点表结点结构描述typedef struct VertexNode adjlistMaxNum; /邻接表 int n,e; AlGraph; /邻接表结构描述 下列算法输出图G的深度优先生成树(或森林)的边，阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。typedef enum FALSE,TRUE Boolean;Boolean visitedMaxNum;void DFSForest(AlGraph *G) for(i=0; in; i+) visitedi=_; for(i=0;in;i+) if (!visitedi) DFSTree(G,i);void DFSTree(AlGraph *G, int i) visitedi=TRUE; p=G-adjlisti.firstedge; while(p!=NULL) if (!visitedp-adjves) printf(G-adjlisti.vertex, G-adjlistp-adjvex.vertex); _; _;四、算法设计题01、编写编历算法，完成对图的深度优先搜索和广度优先搜索。02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。03、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。提示：要删除所有从第i个顶点出发的边，即将邻接矩阵的第i行全部置0。04、有n个顶点的有向图的邻接表定义如下：#define MaxNum 80typedef struct ArcNode int adjvex; /邻接点域 struct ArcNode *nextarc; /链指针域 ArcNode; /边表结点结构描述typedef struct VNode VertexType data; /顶点域 ArcNode *firstedge; /边表头指针 VNode,AdjListMaxNum; /顶点向量结点结构描述typedef struct AdjList vertices; /邻接表 int vexnum,arcnum; AlGraph; /邻接表结构描述设计算法分别实现以下要求(1)求出图G中每个顶点的出度；(2)求出图G中出度最大的一个顶点，输出该顶点号及其信息；(3)计算图G中出度为0的顶点数；(4)判断图G中是否存在弧。05、试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(ij)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。第7章 图一、单选题 01-10 CBBCC BAACB 11-20 DAADB ACACB 21-30 DCDAD BCBAD二、填空题01、入度02、n-103、邻接矩阵、邻接表04、深度、广度04、出度05、n06、O(n2)、O(n+e)07、有向08、将邻接矩阵的第i行全部置009、矩阵第i列非0元素之和10、第i行第j列的元素是否为011、O(n2)、O(elog2e)12、克鲁斯卡尔(Kruskal)、普里姆(Prim) 13、递增14、015、出度16、n17、018、错误19、2(n-1)20、存在三、简答题01、3个，分别是：a,bce,dfg02、03、普里姆算法产生边的序列：(1,3),(3,4),(4,6),(6,5),(5,2)克鲁斯卡尔算法产生边的序列：(4,6),(1,3),(4,3),(6,5),(2,5)04、v1,v2,v3,v4v1,v3,v2,v4v2,v1,v3,v405、(1) 每个顶点的入/出度 (2) 邻接矩阵 (3) 邻接表 (4) 逆邻接表 06、(1)邻接矩阵为：VbcdefghUV-UVexlowcosta4a3aaaaaab,c,d,e,f,g,hVexlowcosta40c5aaac5a,cb,d,e,f,g,hVexlowcost00c5b9aac5a,c,bd,e,f,g,hVexlowcost000d7d6d5d4a,c,b,de,f,g,hVexlowcost000d7d6d50a,c,b,d,he,f,gVexlowcost000d7g200a,c,b,d,h,gf,eVexlowcost000f3000a,c,b,d,h,g,feVexlowcost0000000a,c,b,d,h,g,f,e 最小生成树07、邻接表为：fg(2)ac(3)fe(3)ab(4)dh(4)bd(5)dg(5)08、09、ac：2(a,c)af：6(a,c,f)ae：10(a,c,e)ad：11(a,c,f,d)ag：14(a,c,f,d,g)ab：15(a,b)10、和上题类似，求解过程略。11、1，2，3，6，5，41，3，2，6，5，41，3，6，2，5，412、FALSE /初始化为未访问DSFTree(G, p-adjvex) /从相邻结点往下继续深度搜索p=p-next /下一个未访问的相邻结点四、算法设计题01、编写编历算法，完成对图的深度优先搜索和广度优先搜索。深度优先搜索：课本P169算法7.4和算法7.5广度优先搜索：课本P170算法7.602、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。解：Status Build_AdjList(ALGraph &G) /输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 InitALGraph(G); scanf(%d,&v); if(v0) return ERROR; /顶点数不能为负 G.vexnum=v; scanf(%d,&a); if(a0) return ERROR; /边数不能为负 G.arcnum=a; for(m=0;mv;m+) G.verticesm.data=getchar(); /输入各顶点的符号 for(m=1;m=a;m+) t=getchar();h=getchar(); /t为弧尾,h为弧头 if(i=LocateVex(G,t)0) return ERROR; if(j=LocateVex(G,h)nextarc;q=q-nextarc); q-nextarc=p; p-adjvex=j;p-nextarc=NULL; /while return OK; /Build_AdjList 03、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。(如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 )解：/本题中的图G均为有向无权图。 Status Delete_Arc(MGraph &G,char v,char w)/在邻接矩阵表示的图G上删除边(v,w) if(i=LocateVex(G,v)0) return ERROR; if(j=LocateVex(G,w)0) return ERROR; if(G.arcsij.adj) G.arcsij.adj=0; G.arcnum-; return OK; /Delete_Arc 04、有n个顶点的有向图的邻接表定义如下：(本题答案见实验部分)#define MaxNum 80typedef struct ArcNode int adjvex; /邻接点域 struct ArcNode *nextarc; /链指针域 ArcNode; /边表结点结构描述typedef struct VNode VertexType data; /顶点域 ArcNode *firstedge; /边表头指针 VNode,AdjListMaxNum; /顶点向量结点结构描述typedef struct AdjList vertices; /邻接表 int vexnum,arcnum; AlGraph; /邻接表结构描述设计算法分别实现以下要求(1)求出图G中每个顶点的出度；(2)求出图G中出度最大的一个顶点，输出该顶点号及其信息；(3)计算图G中出度为0的顶点数；(4)判断图G中是否存在弧。05、试基于图的深度优先搜索策略写一算