数据结构1800试题-第7章 图

*
V0
V7
V6
V5
V4
V3
V2
V1
若图的存储结构为邻接表，则 访问邻接点的顺序不唯一， 深度优先序列不是唯一的
V0
V1
V3
V2
V7
V6
V5
V4
V0,V1,V3,V4,V7,V2,V5,V6,
※求图G以V0为起点的的深度优先序列（设存储结构为邻接矩阵）
void DFSAL(ALGraph G, int i) {/*从第v个顶点出发，递归地深度优先遍历图G*/ /* v是顶点的序号，假设G是用邻接表存储*/ EdgeNode *p; int w; visited[i] =1; Visit(i); /*访问第v个顶点*/ for (p=G.vertices[i].firstarc;p;p=p->nextarc) {w=p->adjvex; /*w是v的邻接顶点的序号*/ if (!visited[w]) DFSAL(G, w); /*若w尚未访问, 递归调用DFS*/ } }/*DFSAL*/
在邻接表存储结构上的广度优先搜索
*
Q
V0
V1
V2
V3
V4
V7
V5
V6
V1
V2
V3
V0
V4
V7
V5
V6
V0
V7
V6
V5
V4
V3
V2
V1
7.3 图的遍历
7
0
1
2
V0
V2
V3
V1
data
firstarc
0
1
^
^
adjvex
next
3

数据结构测试（长春理工大学精品课）第7章图一、选择题1．设无向图的顶点个数为n，则该图最多有（）条边。

查看答案A．n-1 B．n(n-1)/2C．n(n+1)/2 D．n2正确答案是B解释: n个顶点相互都有关系，即边数最多。

边数=（n-1）+（n-2）+......+0=n(n-1)/2收起2．要连通具有n个顶点的有向图，至少需要（）条边。

查看答案A．n-l B．nC．n+l D．2n正确答案是B解释:有向图要连通边数最少为n条，形成环。

收起3．一个有n个结点的图，最少有（）个连通分量查看答案A．0 B．1C．n-1 D．N正确答案是B解释:图是连通图连通分量最少，即1个。

收起4．已知有向图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,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7正确答案是A收起5. 关键路径是事件结点网络中（）。

查看答案A．从源点到汇点的最长路径 B．从源点到汇点的最短路径C．最长回路 D．最短回路正确答案是A解释:关键路径是由关键顶点和关键活动组成的。

收起6. 求解最短路径的Floyd算法的时间复杂度为( )。

查看答案A．O（n） B. O（n+c）C. O（n*n）D. O（n*n*n）正确答案是D收起7. 下列说法不正确的是（）。

查看答案A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程正确答案是B解释:图的深度遍历同样适用于有向图，算法中每个顶点均出发一次。

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)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)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)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)最短路径的 Dijkstra C)拓扑排序 D)广度优先遍历 A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为 。

第七章 图 习题解答7.5 已知以二维数组表示的图的邻接矩阵如下图所示。

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

18562739104（2）求得的广度优先生成树为：31791062487.7 请对下面的无向带权图，（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2）写出它的邻接表，并按克鲁期卡尔算法求其最小生成树。

bacedfgh4455 555336 6792解：（1）图的邻接矩阵为：按普里姆构造最小生成树的过程如下：ac3（1）b ac43（2）b acd453（3）b acdh4453（5）b acdgh445532 b（1）（2）图的邻接表如下：按克鲁期卡尔算法构造最小生成树的过程如下：b acd fgh44 5 53 2（6） b acedfgh4455332（7）0 1 23 4 5 6 7（2）b 32b d332（3）（4）bacd h4332b acedfgh4455332（7）b acedfgh445332（6）baced fgh44332（5）。

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

A. 1/2B. 1C. 2D. 42．任何一个无向连通图的最小生成树。

A.只有一棵B3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

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所示。

图7.2 一个有向图的邻接表存储结构⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

一、选择题1、有6个结点的有向完全图有（）条弧。

A、36B、28C、30D、152、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。

A、栈B、队列C、树D、图3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。

A、栈B、队列C、树D、图4、任何一个无向连通图的最小生成树（）A、只有一棵B、一棵或多棵C、一定有多棵D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。

A、1/2B、1C、2D、46、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A、1/2B、1C、2D、47、一个有n个顶点的无向图最多有（）条边。

A、nB、n(n-1)C、n(n-1)/2D、2n8、具有5个顶点的无向完全图有（）条边。

A、6B、8C、10D、209、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。

A、nB、n+1C、n-1D、n/210、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、nD、n*n11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（）(1)A、n B、n+1 C、n-1 D、n+e(2)A、e/2 B、e C、2e D、n+e12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）A、先序遍历B、中序遍历C、后序遍历D、按层遍历13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）A、先序遍历B、中序遍历C、后序遍历D、按层遍历14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法C、宽度优先遍历算法D、深度优先遍历算法15、关键路径是AOE网中的（）A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最短的回路D、活动的最早开始时间与最迟发生时间相等二、填空题1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。

第7章图部分答案解释如下。

2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上权值之和相等26. 是自由树，即根结点不确定35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。

42. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。

45. 能求出关键路径的AOE网一定是有向无环图46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩短工期。

48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。

自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

三．填空题1.有n个顶点，n-1条边的无向连通图2.有向图的极大强连通子图3. 生成树4. 455. n(n-1)/2 6 . 7. 9 8. n9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n15. N16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同(5)队列和栈22. 深度优先 23.宽度优先遍历 24.队列25.因未给出存储结构，答案不唯一。

本题按邻接表存储结构，邻接点按字典序排列。

25题（1） 25题（2）26.普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法 27.克鲁斯卡尔28.边稠密边稀疏 29. O(eloge）边稀疏 30.O(n2） O(eloge)31.(1）（V i，V j）边上的权值都大的数（2）1 负值（3）为负边32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增负值35.16036.O(n2） 37. 50，经过中间顶点④ 38. 75 39.O(n+e）40.(1）活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间41.关键路径 42.（1）某项活动以自己为先决条件（2）荒谬（3）死循环43.（1）零（2）V k度减1，若V k入度己减到零，则V k顶点入栈（3）环44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout(5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti(9)p<>nil (10)p^.vexj=j(11)firstadj(g,v0) (12)not visited[w] (13)nextadj(g,v0,w)46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1(8)indegree[i]==047.(1)p^.link:=ch[u].head (2)ch[u].head:=p (3)top<>0 (4)j:=top(5)top:=ch[j].count(6)t:=t^.link48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。

第七章图试题一、单项选择题1.在无向图中定义顶点的度为与它相关联的（）的数目。

A. 顶点B. 边C. 权D. 权值2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。

A. 顶点序列B. 边序列C. 权值总和D. 边的条数3.图的简单路径是指（）不重复的路径。

A. 权值B. 顶点C. 边D. 边与顶点均4.设无向图的顶点个数为n，则该图最多有（）条边。

A. n-1B. n(n-1)/2C. n(n+1)/2D. n(n-1)5.n个顶点的连通图至少有（）条边。

A. n-1B. nC. n+1D. 06.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。

A. 3B. 2C. 1D. 1/27.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。

A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵8.图的深度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次9.图的广度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构，判断一条边的两个端点是否在同一个连通分量上。

A. 位向量B. 堆C. 并查集D. 生成树顶点集合11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（）。

A. 重边B. 有向环C. 回路D. 权值重复的边12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（）。

A. 非零B. 非整C. 非负D. 非正13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少有（）子女。

A. 1B. 2C. 3D. 014.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。

第七章图
1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索
算法写出从C开始的深度优先搜索序列。

0A13^
1B35^
2C30^
3D4^
4E^
5F4^
【解答】
A B F
C D E
C开始的深度优先搜索序列：CDEABF（唯一的结果）
2．假定要在某县所辖六个镇（含县城）之间修公路，若镇I和镇J之间有可能通
过道路连接，则Wij表示这条路的长度。

要求每个镇都通公路且所修公路总里程
最短，那么应选择哪些线路来修。

I11112233445 J23564546566 W ij1239102626474
(1).画出该图。

(2).用C语言描述该图的数组表示法存储结构，并注明你所使用变量的实际含义。

(3).图示你所定义的数据结构。

(4).标识出你选择的线路。

【解答】
（1）
（2）
#define MAX 6
char vexs[MAX];
出该图的所有强连通分量。

(2).在图中删除弧<2,1>，然后写出从顶点1开始的拓扑有序序列。

【解答】
(1) 共4个强连通分量：
(2) 1,3,2,6,5,4
5 4
6 1 3 2
4
15 10
2
15 20 30 4 10
10。

1第七章 数据结构作业第七章 图选择题1．设无向图的顶点个数为n ，则该图最多有（，则该图最多有（ ）条边。

）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n 22．一个n 个顶点的连通无向图，其边的个数至少为（个顶点的连通无向图，其边的个数至少为（ ）。

）。

A ．n-1B ．nC ．n+1D ．nlogn nlogn；； 3．一个有n 个结点的图，最少有（个结点的图，最少有（ ）个连通分量，最多有（）个连通分量，最多有（ ）个连通分量。

）个连通分量。

A ．0B ．1C ．n-1D ．n4．在一个无向图中，所有顶点的度数之和等于所有边数（．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（等于所有顶点出度之和的（）倍。

A ．1/2 B ．2 C ．1 D ．45．下列哪一种图的邻接矩阵是对称矩阵？（．下列哪一种图的邻接矩阵是对称矩阵？（） A ．有向图．有向图 B B ．无向图．无向图 C C．AOV 网 D ．AOE 网 6．当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是（的度是（ ）。

A ．å=n i j i A 1],[ B ．[]å=n1j j ,i A C ．å=n i i j A 1],[ D ．å=n i j i A 1],[+ []å=n 1j i ,j A 7．下面哪一方法可以判断出一个有向图是否有环（回路）：A ．深度优先遍历．深度优先遍历 B. B. 拓扑排序拓扑排序 C. C. 求最短路径求最短路径 D. D. 广度优先遍历广度优先遍历8. 在图采用邻接表存储时，求最小生成树的在图采用邻接表存储时，求最小生成树的 Prim Prim 算法的时间复杂度为算法的时间复杂度为算法的时间复杂度为( )( )。

A. O(n) B. O(n+e) C. O(n 2) D. O(n 3)9. 求解最短路径的Floyd 算法的时间复杂度为算法的时间复杂度为( )( )。

7.3 图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点， 并且使图中的每个顶点仅被访问一次的过程。 一、深度优先搜索 从图中某个顶点V0 出发，访问此顶点，然后依次 从V0的各个未被访问的邻接点出发深度优先搜索遍 历图，直至图中所有和V0有路径相通的顶点都被访 问到，若此时图中尚有顶点未被访问，则另选图中 一个未曾被访问的顶点作起始点，重复上述过程， 直至图中所有顶点都被访问到为止。
void BFSTraverse(Graph G, Status (*Visit)(int v)) { // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组 visited。 for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; InitQueue(Q); // 置空的辅助队列Q for ( v=0; v<G.vexnum; ++v ) if ( !visited[v]) { // v尚未访问 EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q)) { DeQueue(Q, u); // 队头元素出队并置为u visited[u] = TRUE; Visit(u); // 访问u for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) ) if ( ! visited[w]) EnQueue(Q, w); // u的尚未访问的邻接顶点w入队列Q
4。邻接多重表
边结点
mark ivex
顶点结点
ilink
jvex
jlink
info
data
firstedge
#define MAX_VERTEX_NUM 20 typedef emnu {unvisited, visited} VisitIf; typedef struct Ebox { VisitIf mark; // 访问标记 int ivex, jvex; // 该边依附的两个顶点的位置 struct EBox *ilink, *jlink; // 分别指向依附这两个顶点的下一条 边 InfoType *info; // 该边信息指针 } EBox; typedef struct VexBox { VertexType data; EBox *firstedge; // 指向第一条依附该顶点的边 } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; // 无向图的当前顶点数和边数 } AMLGraph;

17.第七章图试题单项选择题1.在无向图中定义顶点得度为与它相尖联得（）得数目。

A '顶点i 与 B 、边C 、权D 、权值2.在无向图中定义顶点vVj 之间得路径为从Vi 到达Vj 得一个 0OA 、顶点序列B 、边序列C 、权值总与D ■ 边得条数3.图得简单路怪就是指（) 不重复得路怪。

权值B 、顶点C 、边D ■ 边与顶点均4. 设无向图得顶点个数为n,则该图最多有（） 条边。

5.A ' rdB 、n(n1)/2C ' n(n+1)/2D ' n(n1)n 个顶点得连通图至少有(）条边。

6.A ' rdB 、 nC 、n+1D ■ 0在一个无向图中，所有顶点得度数之与等于所有边数得（）倍。

7. 3B 、2D 、1/2若采用邻接矩阵法存储一个n 个顶点得无向图 ,则该邻接矩阵就是 —个（）。

8. 上三角矩阵B 、 桶疏矩阵C 、对角矩阵D ■ 对称矩阵图得深度优先搜索类似于树得 （）次序遍历。

9. A 、先根B 、中根C 、后根D 、层次 图得广度优先搜索类似于树得 （）次序遍历。

40. A 、先根 B 、中根C 、后根D 、层次在用Kruskal 算法求解带权连通图得最小（代价）生成树时，通常采用一个（）辅助结构，判断一条边得两个端点 就是否在同一个连通分量上。

11. A 、位向量 B 、堆 C 、并查集 D 、生成树顶点集合在用Kruskal 在算法求解带权连通图得最小（代价）生成树时，选择权值最小得边得原则就是该边不能在一个连通图中逬行深度优先搜索得到棵深度优先生成树 至少有0子女。

A ' 1设有向图有n 个顶煮与彳）。

C 、3A ・O （nlog 2e ）设有向品楝牛虞驹利表作为其存储表示有向图得一个顶点得度为该顶点得（A 、入度B 、A * O(nlog 设 G1 =(V1,E1)B ' O(n+e)C • O(ne)9D 、0(n z)A 、G1就是条边，采用邻接矩阵作为其存储表示.在进行拓扑排序时，总得计算时间为C 、G1就是2e)B 、O(n+e)C ・ O(ne)D 、0(n 2)与G2 =(V2, E2) G2为两个图，如果WV2,E1 E2,则称()o得了图G2得连通分量B 、G2就是G1得子图15.16.图中构成（12- A 、重边在用 Dijkstra （）-A 、非零13.B 、有向环C 、冋路 算法求解带权有向图得最短路径问题时C 、非负D 、权值重复得边,要求图中每条边所带得权值必须就是D 、非正.树根结点就是矢节点得充要条件就是它D 、0，在进行拓扑排序时，总得计算时间为出度D 、（入度+出度））/2C、入度与出度之与一个连通图得生成树就是包含图中所有顶点得一个17.8.A 、极小B 、连通19.n(n> 1)个顶点得强连通图中至少含有 20. 21. A 、 在一个带权连通图G 中，权值最小得边一定包含在 A 、某个锻小 B 、任何最小 对于具有e 条边得无向图，它得邻接表中有( A ' e1 B ' e C 、极小连通 条有向边。

第7章图一、单项选择题1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。

A．l/2 B．1C．2 D．42．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。

A．l/2 B．1C．2 D．43．一个具有n个顶点的无向图最多包含______条边。

A．n B．n＋1C．n-1 D．n(n-1)/24．一个具有n个顶点的无向完全图包含______条边。

A．n(n-l) B．n(n+l)C．n(n-l)/2 D．n(n-l)/25．一个具有n个顶点的有向完全图包含______条边。

A．n(n-1) B．n(n+l)C．n(n-l)/2 D．n(n+l)/26．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。

A．nB．n×nC．n-1 D．(n-l)×(n-l)7．无向图的邻接矩阵是一个______。

A．对称矩阵B．零矩阵C．上三角矩阵D．对角矩阵8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。

A．n B．eC．2n D．2e9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。

A．n B．eC．2n D．2e10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。

A．入边B．出边C．入边和出边D．不是入边也不是出边11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。

A．入边B．出边C．入边和出边D．不是人边也不是出边12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。

A．完全图B．连通图C．有回路D．一棵树13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。

A．先序遍历B．中序遍历C．后序遍历 D．按层遍历14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。

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

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

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

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

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

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

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

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

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

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

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表【北京工业大学 2001 一、3 (2分)】11．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网12．从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。

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

A、由顶点和相邻顶点序偶构成的边所形成的序列B、由不同顶点所形成的序列C、由不同边所形成的序列D、上述定义都不对2、设无向图的顶点个数为n，则该图最多有（）条边。

A、n– 1B、n (n– 1)/2C、n (n+1)/2D、n23、一个n个顶点的连通无向图，其边的个数至少为（）。

A、n– 1B、nC、n+1D、n log n4、下面结构中最适于表示稀疏无向图的是（）。

A、邻接矩阵B、逆邻接表C、邻接多重表D、十字链表5、下列哪一种图的邻接矩阵是对称矩阵？（）A、有向图B、无向图C、AOV网D、AOE网6、当一个有N个顶点的图用邻接矩阵A表示时，顶点V i的度是（）。

A、第j列所有元素之和B、第i行所有元素之和C、不确定D、第j列所有元素之和+第i行所有元素之和7、下面哪一方法可以判断出一个有向图是否有环（回路）（）。

A、深度优先遍历B、拓扑排序C、求最短路径D、求关键路径8、在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。

A、O(n)B、O(n+e)C、O(n2)D、O(n3)9、求解最短路径的Floyd算法的时间复杂度为( )。

A、O(n)B、O(n+e)C、O(n2)D、O(n3)10、已知有向图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,v7B、v1,v3,v2,v6,v4,v5,v7C 、v 1,v ,v 4,v 5,v 2,v 6,v 7D 、v 1,v 2,v 5,v 3,v 4,v 6,v 711、在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

【解答】(1)邻接矩阵如下：
0 10 ∞ ∞
15 0 6 ∞
3 ∞ 0 4
∞ 8 2 0
(2)采用弗洛伊德算法求最短路径的过程如下：
7．对于有向无环图，
(1)叙述求拓扑有序序列的步骤。
(2)对于题图7-6所示的有向图，写出它的4个不同的拓扑有序序列。
【解答】(1)参见7.6节的介绍。
(2)它的4个不同的拓扑有序序列是：12345678，12354678，12347856，12347568。
(6)在V-S中找出最近的顶点5，加入S中，即s口={l，3，2，6，4，5}。此时S中包含了图的所有顶点，算法结束。最终dist[]={0，19，15，29，29，25），path[]={1，3，l，6，2， 3}。
由此得到：
从顶点1到顶点2的最短路径长度为：19 最短路径为：2<-3<-1
从顶点l到顶点3的最短路径长度为：15 最短路径为：3<-1
dist[4]=min{dist[4], dist[6]+cost[6][4])=min{∞..,25+4}=29,
则有dist[]={0, 19, 15, 29, 29, 25}, path[]={l,3,1,6,2,3}。
(5)在V-S中找出最近的顶点4，加入S中，即s[]：{l，3，2，6，4}，并重新计算顶点l到达顶点5的距离，此时不需要修改dist值，则有dist[]={0，19，15，29，29，25），path[]={l，3， l，6，2， 3}。
(1)有n个顶点的无向连通图最多需要多少条边？最少需要多少条边？
(2)表示一个具有1000个顶点、1000条边的无向图的邻接矩阵有多少个矩阵元素？有多少非零元素？是否为稀疏矩阵？

}
V2V4V6
a2=3a9=4a12=4
a1=5a7=5
a11=5V9V10
V1a4=6V7a14=2
a3=6a13=2
a5=3a10=4
V3V5V8
顶点Ve Vl
活动e l l-e
V10 0
V2 5 9
V3 6 6
V4 12 12
V5 15 16
V6 16 20
V7 17 17
V8 19 20
V9 22 22
a7 12 12 4
a8 15 16 0
a9 12 16 4
a10 15 16 1
a11 17 17 0
a12 16 20 4
a13 19 20 1
a14 22 22 0
关键途径V1->V3->V4->V7->V9->V10长22
关键活动a3,a4,a7,a114
顶点Ve Vl
活动e l l-e
V10 0
V259
V366
V4 12 12
V5 15 16
V6 16 20
V7 17 17
V8 19 20
V9 22 22
V10 24 24
a1 0 0 0
a2 5 9 4
a3 0 0 0
a4 6 6 0
a5 6 13 7
a6 12 13 1
if(w= =k)
{ found=1;exit(0);}
用邻接表存储结构，邻接点逆序即编号大的排在前面。入度为0极点用栈结构存储，初始时从极点1到极点N扫描，入度为0的极点进栈，得V5在栈顶。
7．11
void toposort_dfs（graph g；vtptr v）