厦门理工数据结构期末复习题8

厦门理工数据结构期末复习题8 单元练习8 一(判断题(下列各题，正确的请在前面的括号内打?;错误的打? ) (?)(1)图可以没有边，但不能没有顶点。 (ㄨ)(2)在无向图中，(V，V)与(V，V)是两条不同的边。 1221 (ㄨ)(3)邻接表只能用于有向图的存储。 (?)(4)一个图的邻接矩阵表示是唯一的。 (ㄨ)(5)用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。 (ㄨ)(6)有向图不能进行广度优先遍历。 (?)(7)若一个无向图的以顶点V为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一1 确定该图。 (?)(8)存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。 (ㄨ)(9)用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。 (?)(10)若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。 二(填空题 (1) 图常用的存储方式有邻接矩阵和 邻接表 等。 (2) 图的遍历有: 深度优先搜 和广度优先搜等方法。 (3) 有n条边的无向图邻接矩阵中，1的个数是 _2n____。 (4) 有向图的边也称为 _ 弧___ 。 (5) 图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。 (6) 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。 2(7) n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为: O(n) 。 (8) n个顶点e条边的图若采用邻接表存储，则空间复杂度为: O(n+e) 。 (9) 设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。 (10) 设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。 (11) 图的逆邻接表存储结构只适用于 __有向____图。 (12) n个顶点的完全无向图有 n(n-1)/2_ 条边。 (13) 有向图的邻接表表示适于求顶点的 出度 。 (14) 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V的 入度 。 i (15) 对于具有n个顶点的图，其生成树有且仅有 n-1 条边。 (16) 对n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结点。 (17) 从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图 的 遍历 。 (18) 无向图的邻接矩阵一定是 对称 矩阵。 (19) 一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。 (20) 若要求一个稠密图G的最小生成树，最好用 Prim 算法来求解。 三(选择题 (1)在一个图中，所有顶点的度数之和等于图的边数的( C )倍。 A(1/2 B. 1 C. 2 D. 4 (2)在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。 A(1/2 B. 1 C. 2 D. 4 (3)对于一个具有n个顶点的有向图的边数最多有( B )。 A(n B(n(n-1) C(n(n-1)/2 D(2n (4)在一个具有n个顶点的无向图中，要连通全部顶点至少需要( C )条边。 A(n B(n+1 C( n-1 D(n/2 (5)有8个结点的有向完全图有( C )条边。 A(14 B. 28 C. 56 D. 112 (6)深度优先遍历类似于二叉树的( A )。 A(先序遍历 B(中序遍历 C(后序遍历 D(层次遍历 (7)广度优先遍历类似于二叉树的( D )。 A(先序遍历 B(中序遍历 C(后序遍历 D(层次遍历 (8)任何一个无向连通图的最小生成树( A )。 A(只有一棵 B(一棵或多棵 C(一定有多棵 D(可能不存在 (9)无向图顶点v的度是关联于该顶点( B )的数目。 A(顶点 B(边 C(序号 D(下标 (10)有n个顶点的无向图的邻接矩阵是用( B )数组存储。 A(一维 B(n行n列 C(任意行n列 D(n行任意列 (11)对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为( C )。 A(n-1 B(n+1 C(n D(n+e (12)在图的表示法中，表示形式唯一的是( A )。 A(邻接矩阵表示法 B(邻接表表示法 C(逆邻接表表示法 D(邻接表和逆邻接表表示法 (13)在一个具有n个顶点e条边的图中，所有顶点的度数之和等于( C )。 A(n B(e C( 2n D(2e (14)下列图中，度为3的结点是( B )。 1 2 3 5 4 A(V B. V C. V D. V 1234(15)下列图是( A )。 1 2 3 5 4 A(连通图 B. 强连通图 C. 生成树 D. 无环图 (16)如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为( D )。 a A( a，b，e，c，d，f b B( a，c，f，e，b，d c e C. a，e，b，c，f，d D. a，e，d，f，c，b f d (17)如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为( A )。 a A. a，b，e，c，d，f b B. a，b，e，c，f，d c e C. a，e，b，c，f，d D. a，e，d，f，c，b f d (18)最小生成树的构造可使用( A )算法。 A(prim算法 B(卡尔算法 C(哈夫曼算法 D(迪杰斯特拉算法 (19)下面关于图的存储结构的叙述中正确的是( A )。 A( 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关 B( 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关 C( 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关 D( 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关 (20)连通分量是( C )的极大连通子图。 A(树 B(图 C(无向图 D(有向图 四(应用题(30分) 1(有向图如下图所示，画出邻接矩阵和邻接表 ? ?? ?? ?? ? ? ?? ??解: ??(1)邻接矩阵 ? ? 1 2 3 4 5 101101,,,,200010,, ,, 300001,, 410000,, ,,500010,, (2)邻接表 1 2 3 5 ? 2 4 ? 3 5 ? 4 1 ? 5 4 ? 2( 已知一个无向图有6个结点，9条边，这9条边依次为(0，1),(0，2),(0，4),(0，5)， (1，2)，(2，3)，(2，4)，(3，4)，(4，5)。试画出该无向图，并从顶点0出发，分别 写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。(5分) 解: 0 15 2 4 D 3 从顶点0出发的深度优先搜索遍历的结点序列:0 1 2 3 4 5(答案不唯一) 从顶点0出发的广度优先搜索遍历的结点序列:0 1 2 4 5 3(答案不唯一) 3( 已知一个无向图的顶点集为:{a，b，c，d，e}，其邻接矩阵如下，画出草图，写出顶点a出 发按深度优先搜索进行遍历的结点序列。(5分) 01001，， ,, 10010,, ,,00011 ,,01101,, ,,10110，， 解: (1) (2)深度优先搜索: a a b d c e (答案不唯一) 广度优先搜索: c e b a b e d c (答案不唯一) d 4(网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 0810110，， ,,803013 ,, ,,103040 ,,110407 ,, ,, 013070，， 解: 最小生成树: 1 1 8 11 10 8 3 4 3 4 2 3 4 2 13 7 3 4 7 5 5 5. 已知某图G的邻接矩阵如图， 0101，，(1)画出相应的图; ,,1010(2)要使此图为完全图需要增加几条边。 ,, ,,0101 ,, 1010，， 解: (1) 1 22 1 D 4 3 3 4 (2) 完全无向图应具有的边数为:n*(n-1)1/2=4*(4-1)/2=6，所以还要增加2条边(如右图)。 6(已知如图所示的有向图，请给出该图的: (1) 每个顶点的入/出度; (2) 邻接表; (3) 邻接矩阵。 解: (1) (2) 顶点 1 2 3 4 5 6 入度 3 2 1 1 2 2 出度 0 2 2 3 1 3 (3) 7(如图，请完成以下操作: (2) 写出无向带权图的邻接矩阵; (3) 设起点为a，求其最小生成树。 解: (1)邻接矩阵为: (2)起点为a，可以直接由原 始图画出最小生成树 043,,,,,，， 40559,,,,, ,,3505,,,5 ,,,5507654 ,,,9,703,, ,,,,,6302, ,,,,,5,206 ,,,,54,,60 ，， 8(给定下列网G: (1) 画出网G的邻接矩阵; (2) 画出网G的最小生成树。 解: (1)邻接矩阵 (2)最小生成树 ,12,,4,,，， ,,12,20,89,,,A B C ,20,15,,12,, ,, ,,15,,,10,,EF D G ,,48,,,6,D ,,,9,,6,,,, ,,,,1210,,,，， 五(程序题填空题 图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边(v,w)的操作:DeleteArc(G,v,w)。 若无顶点v或w，返回“ERROR”;若成功删除，则边数减1，并返回“OK”。 (提示:删除一条边的操作，可以将邻接矩阵的第i行全部置0 ) 解: Status DeleteArc(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.arcs[i][j].adj) { G.arcs[i][j].adj= 0 ; G.arcnum -- ; (或 G.arcnum=G.arcnum-1 ) } return OK ; } 六(算法题 1( 编写一个无向图的邻接矩阵转换成邻接表的算法。 2( 以知有n个顶点的有向图邻接表，设计算法分别实现以下功能: (1)求出图G中每个顶点的出度、入度。 (2)求出G中出度最大的一个顶点，输出其顶点序号。 (3)计算图中度为0的顶点数。 1( 解:本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接表的 第i个单链表上增加一个j结点。 void trans(int edges[n][n],Adjlist adj) { int i,j; edgenode *p; for (i=0;iadjvex=j; p->next=adj[i].link; adj[i].link=p; } } } 2( (1)求出度的思想:计算出邻接表中第i个单链表的结点数即可。 int outdegree(adjlist adj,int v) { int degree=0; edgenode *p; p=adj[v].link; while (p!=NULL) { degree++; p=p->next; } return degree; } void printout(adjlist adj,int n) { int i,degree; printf("The Outdegree are:\n"); for(i=0;iadjvex==v) degree++; p=p->next; } } return degree; } void printin(adjlist adj,int n) { int i,degree; printf("The Indegree are:\n"); for (i=0;imaxdegree) { maxdegree=degree; maxv=i; } } printf("maxoutdegree %d,maxvertex=%d",maxdegree,maxv); } (3)求度为0的顶点数的算法 int outzero(adjlist adj,int n) { int num=0,i; for (i=0;ilink ; while ( p!=NULL ) { if (visited[p->adjvex]== 0 ) // 从v的未访问过的邻接点出发进行深度优先搜索 dfs(adjlist, p->adjvex ); p= p->next ; // 找v的下一个邻接点 } }