数据结构第7章答案.doc

一、单选题
C01、在一个图中，所有顶点的度数之和等于图的边数的 倍。
A)1/2 B)1 C)2 D)4
B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A)1/2 B)1 C)2 D)4
B03、有8个结点的无向图最多有 条边。
A)14 B)28 C)56 D)112
C04、有8个结点的无向连通图最少有 条边。
A)5 B)6 C)7 D)8
C05、有8个结点的有向完全图有 条边。
A)14 B)28 C)56 D)112
B06、用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A)栈 B)队列 C)树 D)图
A07、用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A)栈 B)队列 C)树 D)图
A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 。
A)O(n) B)O(e) C)O(n+e) D)O(n2)
C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 。

A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2
B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是 。
A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6
D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 。

A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3
A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 。

A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2
A13、图的深度优先遍历类似于二叉树的 。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历
D14、图的广度优先遍历类似于二叉树的 。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历
B15、任何一个无向连通图的最小生成树 。
A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在
A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为 ，所有边链表中边结点的总数为 。
A)n、2e B)n、e C)n、n+e D)2n、2e
C17、判断有向图是否存在回路，可以利用___算法。
A)关键路径 B)最短路径的Dijkstra C)拓扑排序 D)广度优先遍历
A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为 。
A)图中每个顶点的入度 B)图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目
C19、求最短路径的Dijkstra算法的时间复杂度是___。
A)O(n) B)O(n+e) C)O(n2) D)O(n*e)
B20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为 。
A)O(n) B)O(n+e) C)O(n2) D)O(n*e)
D21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 。
A)第i行非∞的元素之和 B)第i列非∞的元素之和
C)第i行非∞且非0的元素个数 D)第i列非∞且非0的元素个数
C22、一个有n个顶点的无向图最多有 条边。
A)n B)n(n-1) C)n(n-1)/2 D)2n
D23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。
A)n B)(n-1)2 C)n-1 D)n2
A24、对某个无向图的邻接矩阵来说， 。
A)第i行上的非零元素个数和第i列的非零元素个数一定相等
B)矩阵中的非零元素个数等于图中的边数
C)第i行上，第i列上非零元素总数等于顶点vi的度数
D)矩阵中非全零行的行数等于图中的顶点数
D25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 。

A)abecdf B)acfebd C)aebcfd D)aedfcb
B26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为 。
A)abcedf B)abcefd C)aebcfd D)acfdeb
C27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1出发得到的顶点序列是 。

A)v1,v2,v3,v5,v4 B)v1,v2,v3,v4,v5 C)v1,v3,v4,v5,v2 D)v1,v4,v3,v5,v2
B28、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是 。
A)v1,v2,v3,v4,v5 B)v1,v3,v2,v4,v5 C)v1,v2,v3,v5,v4 D)v1,v4,v3,v5,v2
A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用 次深度优先遍历算法。
A)k B)1 C)n-k D)n
D30、以下不正确的说法是 。
A)无向图中的极大连通子图称为连通分量
B)连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C)图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D)有向图的遍历不可采用广度优先搜索方法
A31、图中有关路径的定义是___。
A)由顶点和相邻顶点序偶构成的边所形成的序列 B)由不同顶点所形成的序列
C)由不同边所形成的序列 D)上述定义都不是
B32、设无向图的顶点个数为n，则该图最多有___条边。
A)n-1 B)n(n-1)/2 C)n(n+1)/2 D)n
A33、一个n 个顶点的连通无向图，其边的个数至少为___。
A)n-1 B)n C)n+1 D)nlogn
B34、要连通具有n 个顶点的有向图，至少需要___条边。
A)n-l B)n C)n+l D)2n
B35、在一个无向图中，所有顶点的度数之和等于所有边数___倍。
A)1/2 B)2 C)1 D)4
C36、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的___倍。
A)1/2 B)2 C)1 D)4
A37、用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为___。
A)5 B)6 C)8 D)9
A38、用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是___。
A)逆拓扑有序 B)拓扑有序 C)无序的 D)原顺序
B39、下列___的邻接矩阵是对称矩阵。
A)有向图 B)无向图 C)AOV网 D)AOE网
BBD40、从邻接阵矩 可以看出，该图共有 ① 个顶点；如果是有向图该图共有 ② 条弧；如果是无向图，则共有 ③ 条边。
① A)9 B)3 C)6 D)1 E)以上答案均不正确
② A)5 B)4 C)3 D)2 E)以上答案均不正确
③ A)5 B)4 C)3 D)2 E)以上答案均不正确
B41、当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是___。

B42、下列说法不正确的是___。
A)图的遍历是从给定的源点出发每一个顶点仅被访问一次 B)图的深度遍历不适用于有向图
C)遍历的基本算法有两种：深度遍历和广度遍历 D)图的深度遍历是一个递归过程
D43、无向图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)abecdf B)acfebd C)aebcfd D)aedfcb
D44、如图所示，在5个序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”，符合深度优先遍历的序列有___个。

A)5 B)4 C)3 D)2
CC45、图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是 ① ，进行广度优先遍历得到的顶点序列是 ② 。

① A)1354267 B)1347652 C)1534276 D)1247653 E)以上答案均不正确
② A)1534267 B)1726453 C)l354276 D)1247653 E)以上答案均不正确
B46、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为___。
A)O(n) B)O(n+e) C)O(n2) D)O(n3)
CABA47、下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为 ① ，下面步骤重复n-1次： ② ； ③ ；最后： ④ 。
① A)VT，ET 为空 B)VT为所有顶点，ET为空
C)VT为网中任意一点，ET为空 D)VT为空，ET为网中所有边
② A)选i属于VT，j不属于VT，且(i,j)上的权最小 B)选i属于VT，j不属于VT，且(i,j)上的权最大
C)选i不属于VT，j不属于VT，且(i,j)上的权最小 D)选i不属于VT，j不属于VT，且(i,j)上的权最大
③ A)顶点i加入VT，(i,j)加入ET B)顶点j加入VT，(i,j)加入ET
C)顶点j加入VT，(i,j)从ET中删去 D)顶点i,j加入VT，(i,j)加入ET
④ A)ET中为最小生成树 B)不在ET中的边构成最小生成树
C)ET 中有n-1条边时为生成树，否则无解 D)ET中无回路时，为生成树，否则无解
A48、下面不正确的是___。
①求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
②利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；(图用邻接矩阵表示)
③Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
A)①②③ B)① C)①③ D)②③
A49、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>, <V1,V3>, <V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>, <V4,V6>, <V5,V7>, <V6,V7>}，则G的拓扑序列是___。
A)V1,V3,V4,V6,V2,V5,V7 B)V1,V3,V2,V6,V4,V5,V7 C)V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V7
D50、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是___。
A)G中有弧<Vi，Vj> B)G中有一条从Vi到Vj的路径
C)G中没有弧<Vi,Vj> D)G 中有一条从Vj到Vi的路径
A51、关键路径是事件结点网络中___。
A)从源点到汇点的最长路径 B)从源点到汇点的最短路径 C)最长回路 D)最短回路
C52、下面关于求关键路径的说法不正确的是___。
A)求关键路径是以拓扑排序为基础的
B)一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C)一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D)关键活动一定位于关键路径上
B53、下列关于AOE网的叙述中，不正确的是___。
A)关键活动不按期完成就会影响整个工程的完成时间
B)任何一个关键活动提前完成，那么整个工程将会提前完成
C)所有的关键活动提前完成，那么整个工程将会提前完成
D)某些关键活动提前完成，那么整个工程将会提前完成
二、填空题
01、在有向图中，以顶点v为终点的边的数目称为v的入度。
02、含n个顶点的无向连通图中至少含有n-1条边。
03、图的存储结构表示有邻接矩阵、邻接表、十字链表、邻接多重表等多种存储结构。
04、图的存储结构中，十字链表可以看成是有向图的邻接表和逆邻接表结合起来得到的一种链表。
05、遍历图的2种常见方法是深度遍历和广度遍历。
06、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。
07、如果n个顶点的图是一个环，则它有n棵生成树。
08、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)。若采用邻接表存储，则空间复杂度为O(n+e)。
09、图的逆邻接表存储结构只适用于有向图。
10、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。
11、图采用邻接矩阵表示，则计算第i个顶点入度的方法是求邻接矩阵第i列非0元素之和。
12、用邻接矩阵表示图时，则判断任意两个顶点vi和vj之间是否有路径相连，只需要检查第i行第j列的元素是否为0即可。
13、用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e)。
14、对稀疏图最好用克鲁斯卡尔(Kruskal)算法求最小生成树，对稠密图最好用普里姆(Prim)算法来求解最小生成树。
15、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。
16、拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。
17、有向图G用邻接矩阵存储，则第i行的所有元素之和等于顶点i的出度。
18、有n个顶点的强连通有向图G至少有n条弧。
19、设有向图G的邻接矩阵为A，如果图中不存在弧<Vi,Vj>，则A[i,j]的值为0。
20、在n个顶点的无向图中，若边数>n-1，则该图必是连通图，此断言是错误的。(正确/错误)
21、在有n个顶点的有向图中，每个顶点的度最大可达2(n-1)。
22、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定存在。(存在/不存在)
23、一个有向无环图的拓扑排序序列不一定是唯一的。(一定/不一定)
24、判断一个无向图是一棵树的条件是有n个顶点，n-1条边的无向连通图。
25、有向图G 的强连通分量是指有向图的极大强连通子图。
26、一个连通图的生成树是一个极小连通子图。
27、具有10个顶点的无向图，边的总数最多为45。
28、若用n表示图中顶点数目，则有n(n-1)/2条边的无向图成为完全图。
29、G 是一个非连通无向图，共有28条边，则该图至少有9个顶点。
30、在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n条弧。
31、构造n个结点的强连通图，至少有n条弧。
32、有n个顶点的有向图，至少需要量n条弧才能保证是连通的。
33、N 个顶点的连通图用邻接矩阵表示时,该矩阵至少有2(N-1)个非零元素。
34、在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度；对于有向图来说等于该顶点的出度。
35、在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是第i列非0元素个数。
36、对于一个具有n 个顶点e 条边的无向图的邻接表的表示，则表头向量大小为n，邻接表的边结点个数为2e。
37、已知一无向图G=(V,E)，其中V={a,b,c,d,e} E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是深度优先遍历方法。
38、一无向图G(V,E)，其中V(G)={1,2,3,4,5,6,7}， E(G)={(1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (6,7), (5,1)}，对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G'(V,E'), V(G')=V(G), E(G')= {(1,3), (3,6), (7,3), (1,2), (1,5), (2,4)}，则采用的遍历方法是广度优先遍历。
39、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需队列存放被访问的结点以实现遍历。
40、构造连通网最小生成树的两个典型算法是普里姆(prim)算法和克鲁斯卡尔(Kruskal)算法。
41、Prim(普里姆)算法适用于求边稠密的网的最小生成树；kruskal(克鲁斯卡尔)算法适用于求边稀疏的网的最小生成树。
42、下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个节点V1，V2，．．．，Vn，用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若(Vi,Vj)是边，则A(i,j)的值等于(Vi,Vj)边上的权值，若(Vi,Vj)不是边，则A(i,j)的值是一个比任何边的权都大的数， 矩阵的对角线元素全为0。
(2)构造最小生成树过程中，若节点Vi 已包括进生成树，就把相邻矩阵的对角线元素A(i,i)置成1，若(Vi,Vj)已包括进生成树，就把矩阵元素A(i,j)置成负值。
(3)算法结束时，相邻矩阵中为负的元素指出最小生成树的边。
43、有一个用于n 个顶点连通带权无向图的算法描述如下：(1)设集合T1与T2，初始均为空；(2)在连通图上任选一点加入T1；(3)以下步骤重复n-1 次：a)在i属于T1，j不属于T1的边中选最小权的边；b)该边加入T2。上述算法完成后，T2 中共有n-1条边，该算法称普里姆算法，T2 中的边构成图的最小生成树。
44、有向图G可拓扑排序的判别条件是不存在环。
45、Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生，该算法弧上的权出现负值情况时，不能正确产生最短路径。
46、有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用<a,b,d>三元组表示弧<a,b>及弧上的权d.E(G)为{<0,5,100>, <0,2,10>, <1,2,5>, <0,4,30>, <4,5,60>, <3,5,10>, <2,3,50>, <4,3,20>}，则从源点0到顶点3的最短路径长度是50，经过的中间顶点是顶点4。
47、上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为75。
48、在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为关键路径。
49、当一个AOV 网用邻接表表示时，可按下列方法进行拓扑排序。
(1)查邻接表中入度为0的顶点，并进栈；
(2)若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj 的直接后继Vk，对Vk 入度处理，处理方法
是Vk度减1，若Vk入度己减到零，则Vk顶点入栈；
(3)若栈空时，输出顶点数小于图的顶点数，说明有环，否则拓扑排序完成。
三、判断题
√01、树中的结点和图中的顶点就是指数据结构中的数据元素。
×02、在n 个结点的无向图中，若边数大于n-1,则该图必是连通图。
×03、有e 条边的无向图，在邻接表中有e 个结点。
×04、有向图中顶点V 的度等于其邻接矩阵中第V 行中的1 的个数。
√05、强连通图的各顶点间均可达。
×06、强连通分量是无向图的极大强连通子图。
×07、连通分量指的是有向图中的极大连通子图。
×08、十字链表是无向图的一种存储结构。
√09、无向图的邻接矩阵可用一维数组存储。
×10、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。
√11、有n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。
×12、有向图的邻接矩阵是对称的。
×13、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
×14、邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形
式来存储它。
√15、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，
而与图的边数无关。
×16、一个有向图的邻接表和逆邻接表中结点的个数可能不等。
×17、广度遍历生成树描述了从起点到各顶点的最短路径。
×18、不同的求最小生成树的方法最后得到的生成树是相同的。
√19、连通图上各边权值均不相同，则该图的最小生成树是唯一的。
√20、在图G 的最小生成树G1 中，可能会有某条边的权值超过未选边的权值。
×21、拓扑排序算法把一个无向图中的顶点排成一个有序序列。
×22、拓扑排序算法仅能适用于有向无环图。
√23、无环有向图才能进行拓扑排序。
×24、有环图也能进行拓扑排序。
×25、拓扑排序的有向图中，最多存在一条环路。
×26、任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。
×27、既使有向无环图的拓扑序列唯一，也不能唯一确定该图。
√28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。
×29、对一个AOV 网，从源点到终点的路径最长的路径称作关键路径。
√30、关键路径是AOE 网中从源点到终点的最长路径。
×31、在表示某工程的AOE 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。
×32、在AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。
√33、在AOE 图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。
×34、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。
四、简答题
01、写出下面有向图的所有强连通分量。

答：3个，分别是：a,bce,dfg
02、已知图的邻接表如下，画出图G的所有连通分量。

答：
03、如下图，分别用普里姆算法和克鲁斯卡尔算法从顶点1开始求最小生成树，写出按次序产生边的序列。说明：边用(i,j)方式表示。

答：普里姆算法产生边的序列：(1,3),(3,4),(4,6),(6,5),(1,2)
克鲁斯卡尔算法产生边的序列：(4,6),(1,3),(4,3),(6,5),(1,2)
04、如下图，写出所有的拓扑序列，并求在添加什么边之后仅可能有惟一的拓扑序列。

答：v1,v2,v3,v4
v1,v3,v2,v4
v2,v1,v3,v4
<v3,v2>
05、已知如图所示的有向图，请给出该图的:
(1) 每个顶点的入/出度；(2) 邻接矩阵；(3) 邻接表；(4) 逆邻接表。

答：
(1) 每个顶点的入/出度 (2) 邻接矩阵

(3) 邻接表 (4) 逆邻接表

06、写出无向带树图的邻接矩阵，并按普里姆算法填写表格中的内容，最后画出最小生成树；

V
b
c
D
e
F
g
h
U
V-U
Vex
lowcost
a
4
a
3
A
∞
a
∞
a
∞
a
∞
a
∞
{a}
{bcdefgh}
Vex
lowcost

Vex
lowcost

Vex
lowcost

Vex
lowcost

Vex
lowcost

Vex
Lowcost

Vex
lowcost

答：
(1)邻接矩阵为：

V
b
c
d
e
f
g
h
U
V-U
Vex
lowcost
a
4
a
3
a
∞
a
∞
a
∞
a
∞
a
∞
{a}
{b,c,d,e,f,g,h}
Vex
lowcost
a
4
0
c
5
a
∞
a
∞
a
∞
c
5
{a,c}
{b,d,e,f,g,h}
Vex
lowcost
0
0
c
5
b
9
a
∞
a
∞
c
5
{a,c,b}
{d,e,f,g,h}
Vex
lowcost
0
0
0
d
7
d
6
d
5
d
4
{a,c,b,d}
{e,f,g,h}
Vex
lowcost
0
0
0
d
7
d
6
d
5
0
{a,c,b,d,h}
{e,f,g}
Vex
lowcost
0
0
0
d
7
g
2
0
0
{a,c,b,d,h,g}
{f,e}
Vex
lowcost
0
0
0
f
3
0
0
0
{a,c,b,d,h,g,f}
{e}
Vex
lowcost
0
0
0
0
0
0
0
{a,c,b,d,h,g,f,e}
{ }
最小生成树

07、按克鲁斯卡尔算法写出下面无向带权图求最小生成树产生的边序列。

答：

fg(2)àac(3)àfe(3)àab(4)àdh(4)àbd(5)àdg(5)
08、已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

答：

09、利用Dijkstra算法填写表格求图中从顶点a到其他各顶点间的最短路径，并写出最终结果。

终点
Dist
b
c
D
e
f
g
S(终点集)
k=1

k=2

k=3

k=4

k=5

k=6

答：

aàc：2(a,c)
aàf：6(a,c,f)
aàe：10(a,c,e)
aàd：11(a,c,f,d)
aàg：14(a,c,f,d,g)
aàb：15(a,b)
10、求出下图中从顶点1出发到其余各顶点的最短路径。

答：

11、设图G=(V，E)，V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}。画出图G，并写出图G中顶点的所有拓扑序列。
答：

1，2，3，6，5，4
1，3，2，6，5，4
1，3，6，2，5，4
五、代码填空题
01、图的存储结构定义如下：
typedef struct ArcCell
{ VRType adj; /*图中有1/0表示是否有边，网中表示边上的权值*/
/* InfoType *info; 与边相关的信息*/
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{ VertexType vexs[MAX_VERTEX_NUM]; /*顶点向量*/
AdjMatrix arcs; /*邻接矩阵*/
int vexnum,arcnum; /*图中当前顶点数和边数*/
} MGraph;
(1) 请写出下面函数实现的功能：顶点在顶点向量中的定位。
int LocateVex(MGraph G,VertexType v)
{ int i;
for(i=0;i<G.vexnum;i++)
if (strcmp(v,G.vexs[i])==0) break;
return i;
}
(2) 下面函数的功能是在图中查找第1个邻接点，请填空。
int FirstAdjVex(MGraph G,int v)
{ int j,p=-1;
for(j=0;j<G.vexnum;j++)
if (G.arcs[v][j].adj==1)
{ p=j; break;}
return p;
}
(3) 下面函数的功能是在图中查找下一个邻接点，请填空。
int NextAdjVex(MGraph G,int v,int w)
{ int j,p=-1;
for(j=w+1;j<G.vexnum;j++)
if (G.arcs[v][j].adj==1)
{ p=j; break;}
return p;
}
02、已知图的邻接表表示的形式说明如下：
#define MaxNum 80
typedef struct node
{ int adjvex; //邻接点域
struct node *next; //链指针域
} EdgeNode; //边表结点结构描述
typedef struct
{ char vertex; //顶点域
EdgeNode *firstedge; //边表头指针
} VertexNode; //顶点表结点结构描述
typedef struct
{ VertexNode adjlist[MaxNum]; //邻接表
int n,e;
} AlGraph; //邻接表结构描述
下列算法输出图G的深度优先生成树(或森林)的边，阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。
typedef enum {FALSE,TRUE} Boolean;
Boolean visited[MaxNum];
void DFSForest(AlGraph *G)
{ for(i=0; i<G->n; i++) visited[i]=FALSE;
for(i=0;i<G->n;i++)
if (!visited[i]) DFSTree(G,i);}
void DFSTree(AlGraph *G, int i)
{ visited[i]=TRUE;
p=G->adjlist[i].firstedge;
while(p!=NULL)
{ if (!visited[p->adjves])
{ printf(G->adjlist[i].vertex, G->adjlist[p->adjvex].vertex);
DSFTree(G, p->adjvex);}
p=p->next; }
}
六、算法设计题
01、编写编历算法，完成对图的深度优先搜索和广度优先搜索。
答：深度优先搜索：课本P169算法7.4和算法7.5
广度优先搜索：课本P170算法7.6
02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
答：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{ InitALGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //顶点数不能为负
G.vexnum=v;
scanf("%d",&a);
if(a<0) return ERROR; //边数不能为负
G.arcnum=a;
for(m=0;m<v;m++)
G.vertices[m].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))<0) return ERROR; //顶点未找到
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->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均为有向无权图。
Statu