数据结构第7章-答案.doc

一、单选题
C０1、在一个图中，所有顶点得度数之与等于图得边数得 　 倍。
　　Ａ）1/2 　B）1 Ｃ）2 D)４
B02、在一个有向图中,所有顶点得入度之与等于所有顶点得出度之与得 倍。
Ａ)1/2 　 　B）1 　 C）２　　 Ｄ）4
Ｂ０３、有8个结点得无向图最多有　 条边。
　 A)１4 　B）２8 　 C）56 　 D）１1２
Ｃ04、有８个结点得无向连通图最少有 条边.
　　　A）5 B）6 　 C）7 　　 D)８
C０5、有８个结点得有向完全图有 　 条边。
　 A)1４ 　 　Ｂ)2８ 　　C）56 　D）11２
B06、用邻接表表示图进行广度优先遍历时，通常就是采用 　 来实现算法得。
　A)栈 B）队列 　　 C）树 D）图
A07、用邻接表表示图进行深度优先遍历时，通常就是采用　 来实现算法得。
A）栈 　Ｂ)队列 　C)树　　　 D）图
Ａ0８、一个含ｎ个顶点与e条弧得有向图以邻接矩阵表示法为存储结构,则计算该有向图中某个顶点出度得时间复杂度为　　 。
　Ａ）Ｏ(n) B）O(e) 　 C)Ｏ(n+e) 　 　D)O（ｎ２)
C09、已知图得邻接矩阵，根据算法思想,则从顶点０出发按深度优先遍历得结点序列就是 .

A）0 2 ４ ３ 1　5 6 　 Ｂ）0 １ 3 ６ 5 ４　2 　　C)0 1 ３ 4 2 5　6 D）0　３ 6 1 5 4 ２
B10、已知图得邻接矩阵同上题，根据算法,则从顶点０出发,按广度优先遍历得结点序列就是 .
A）0 2 ４ 3 6 ５　1 　 B)０　1 2　3 4 6 5 　C）0 ４　2 ３　1　5 ６ Ｄ)0 １ 3 4 ２ ５ 6
Ｄ１1、已知图得邻接表如下所示，根据算法,则从顶点０出发按深度优先遍历得结点序列就是　　 。

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

　 A)0 3　2 １　 Ｂ)0 1 2 ３ 　 C）0 1 3 2　 D）0 3　１ ２
A13、图得深度优先遍历类似于二叉树得 　。
Ａ）先序遍历 B)中序遍历 C）后序遍历 D）层次遍历
D1４、图得广度优先遍历类似于二叉树得 。
　A)先序遍历 　B）中序遍历 C）后序遍历 D）层次遍历
B１5、任何一个无向连通图得最小生成树 　。
　 A)只有一棵 B)一棵或多棵 　　 C)一定有多棵 Ｄ)可能不存在
A１6、对于一个具有n个结点与ｅ条边得无向图，若采用邻接表表示,则顶点表得大小为　 ，所有边链表中边结点得总数为 　。
A）n、2e 　 B)n、e　 　 C)n、n+ｅ Ｄ）2n、2ｅ
Ｃ1７、判断有向图就是否存在回路,可以利用＿_＿算法。
　 A)关键路径　 　 Ｂ）最短路径得Dijｋsｔｒa 　 C)拓扑排序 D）广度优先遍历
A18、若用邻接矩阵表示一个有向图,则其中每一列包含得“1”得个数为　 。
　 　Ａ)图中每个顶点得入度 B)图中每个顶点得出度 　Ｃ）图中弧得条数 　　D)图中连通分量得数目
C１9、求最短路径得Dｉjkｓｔｒa算法得时间复杂度就是_＿_.
　 　A）Ｏ（n) 　B)O(ｎ+e) 　 C）Ｏ（n2) 　 　D)O（ｎ＊e)
B２0、设图Ｇ采用邻接表存储,则拓扑排序算法得时间复杂度为　 .
A)O(n） B)O（n+e）　 　C）O(n2） 　　D）O（n＊e）
Ｄ２１、带权有向图Ｇ用邻接矩阵A存储,则顶点ｉ得入度等于A中　 .
　 　　A）第i行非∞得元素之与 B）第i列非∞得元素之与
Ｃ）第ｉ行非∞且非0得元素个数　 　Ｄ）第i列非∞且非0得元素个数
C22、一个有n个顶点得无向图最多有 条边。
　　 Ａ）n B）ｎ（n－１) 　Ｃ）n（ｎ－1)/２　　 Ｄ)2n
D23、对于一个具有n个顶点得无向图，若采用邻接矩阵表示，则该矩阵得大小就是 。
　Ａ)n　 B）(n—1）2 　 C）n-1 Ｄ）n2
Ａ24、对某个无向图得邻接矩阵来说， .
　 A)第ｉ行上得非零元素个数与第i列得非零元素个数一定相等
B)矩阵中得非零元素个数等于图中得边数
　 　C)第ｉ行上，第ｉ列上非零元素总数等于顶点vi得度数
D）矩阵中非全零行得行数等于图中得顶点数
D25、已知图得表示如下,若从顶点ａ出发按深度搜索法进行遍历，则可能得到得一种顶点序列为 。

　 　Ａ）abecdｆ　 　　B）aｃfebd　 Ｃ)aebcfd　 　 Ｄ）ａedfcb
Ｂ26、已知图得表示如上题，若从顶点ａ出发按广度搜索法进行遍历，则可能得到得一种顶点序列为　 　。
　 Ａ）abcedf Ｂ）aｂceｆｄ 　 C)aｅbcfd　 D）aｃfdeb
Ｃ27、有向图得邻接表存储结构如下图所示，则根据有向图得深度遍历算法，从顶点ｖ１出发得到得顶点序列就是 。

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

B４2、下列说法不正确得就是_＿_。
A）图得遍历就是从给定得源点出发每一个顶点仅被访问一次 B)图得深度遍历不适用于有向图
　 C）遍历得基本算法有两种:深度遍历与广度遍历 D）图得深度遍历就是一个递归过程
D43、无向图G=（V,E),其中：Ｖ=｛a,b,c,d，ｅ，f｝,E=｛（a,b),(a,e）,(a，c），（b,e）,(c，f），（f，d)，（ｅ，d）｝，对该图进行深度优先遍历,得到得顶点序列正确得就是___.
　 　 A)abｅｃdｆ 　 B)acfｅbｄ C）aebcfd D)aedfcb
D44、如图所示，在5个序列“aebｄfc、ａcfdeｂ、aedfcb、aefdｃb、aｅfdbc”，符合深度优先遍历得序列有＿＿_个。

　 　 A）5　 　B）４ Ｃ)３　　　 D）2
ＣC45、图中给出由7个顶点组成得无向图。从顶点1出发，对它进行深度优先遍历得到得序列就是 ① ，进行广度优先遍历得到得顶点序列就是 ②　。

　① A）1354267 B） 　　C)1534276 D）１24７653 　E）以上答案均不正确
　 ② A） 　　B)1７2６45３ 　 C）l35４276　 　 D)1２47653 E)以上答案均不正确
Ｂ46、在图采用邻接表存储时，求最小生成树得Pｒim算法得时间复杂度为＿＿＿.
　 A)O(ｎ)　 B）O（n＋ｅ） 　　　C）O（n2） D)O（ｎ３)
CAＢA47、下面就是求连通网得最小生成树得pｒｉm算法：集合VT，EＴ分别放顶点与边,初始为 ① ，下面步骤重复n—1次： ② ；　③　；最后： ④　。
　 ①　A）VＴ，ＥT　为空　 Ｂ）VT为所有顶点，EＴ为空
　 C)VT为网中任意一点，ET为空 　 D)VT为空，ET为网中所有边
② A)选i属于VT,ｊ不属于VＴ,且(i，j）上得权最小　 　 Ｂ）选i属于ＶT，ｊ不属于VT,且（i,j)上得权最大
　 Ｃ）选i不属于VT，j不属于VT，且（ｉ，j)上得权最小 　D)选i不属于ＶT,ｊ不属于VＴ,且(i,ｊ）上得权最大
③ A)顶点ｉ加入ＶT，(i，ｊ）加入ＥT 　 B）顶点j加入ＶT,（i,j)加入ＥT
　 Ｃ）顶点j加入ＶT，（ｉ，j）从ET中删去 D)顶点i，j加入VT,(i，j）加入ET
　　　　④ A)EＴ中为最小生成树 B）不在EＴ中得边构成最小生成树
　 　 C)EＴ　中有n－1条边时为生成树，否则无解　 　 D）ET中无回路时，为生成树,否则无解
Ａ４８、下面不正确得就是__＿.
　①求从指定源点到其余各顶点得Dｉjkｓtra最短路径算法中弧上权不能为负得原因就是在实际应用中无意义;
②利用Dijｋsｔra求每一对不同顶点之间得最短路径得算法时间就是O（n3）;（图用邻接矩阵表示）
　 ③Ｆlｏｙd求每对不同顶点对得算法中允许弧上得权为负，但不能有权与为负得回路。
　　　 A）①②③　　 Ｂ)①　 C）①③　　 　D)②③
A49、已知有向图G=(V，E）,其中Ｖ={V1,V2，V3,V４,V5，V6，V７｝,E＝{＜V1,V２>， <Ｖ1，V3〉， 〈V１，V4〉， ＜V2,V5〉, <V3，Ｖ5>， ＜V3,V6〉, <V4，V6〉， 〈Ｖ5，V7>， ＜V6,V7＞｝，则G得拓扑序列就是___.
A)Ｖ1,V3，V４，V6，V2,Ｖ5，V7 　　B）V１，V３，Ｖ2，V６，V4，V5，Ｖ７ C)V1,V３，V4,Ｖ5，V2,V6，V7 D)Ｖ1，Ｖ2，Ｖ５，Ｖ3,V4，Ｖ6，V７
Ｄ５０、在有向图G得拓扑序列中，若顶点Vi在顶点Vｊ之前，则下列情形不可能出现得就是__＿。
A）Ｇ中有弧<Vｉ，Vj〉　 B）G中有一条从Ｖｉ到Vj得路径
　 　　C）Ｇ中没有弧〈Vｉ，Vj>　 D）G 中有一条从Vｊ到Vi得路径
Ａ51、关键路径就是事件结点网络中_＿＿。
　 Ａ)从源点到汇点得最长路径 　B）从源点到汇点得最短路径 　 　C）最长回路 D）最短回路
C52、下面关于求关键路径得说法不正确得就是_＿_。
　　A）求关键路径就是以拓扑排序为基础得
B）一个事件得最早开始时间同以该事件为尾得弧得活动最早开始时间相同
　 C）一个事件得最迟开始时间为以该事件为尾得弧得活动最迟开始时间与该活动得持续时间得差
　 　D)关键活动一定位于关键路径上
Ｂ53、下列关于AOE网得叙述中，不正确得就是___。
　A)关键活动不按期完成就会影响整个工程得完成时间
Ｂ)任何一个关键活动提前完成,那么整个工程将会提前完成
C）所有得关键活动提前完成,那么整个工程将会提前完成
　　D)某些关键活动提前完成,那么整个工程将会提前完成
二、填空题
01、在有向图中，以顶点v为终点得边得数目称为v得入度.
0２、含n个顶点得无向连通图中至少含有n-1条边.
0３、图得存储结构表示有邻接矩阵、邻接表、十字链表、邻接多重表等多种存储结构.
０4、图得存储结构中,十字链表可以瞧成就是有向图得邻接表与逆邻接表结合起来得到得一种链表。
05、遍历图得2种常见方法就是深度遍历与广度遍历。
0６、有向图Ｇ用邻接表矩阵存储，其第i行得所有元素之与等于顶点i得出度。
０7、如果n个顶点得图就是一个环,则它有n棵生成树。
０8、n个顶点e条边得图，若采用邻接矩阵存储，则空间复杂度为O（n2)。若采用邻接表存储，则空间复杂度为O(n+e）。
09、图得逆邻接表存储结构只适用于有向图。
10、已知一个图得邻接矩阵表示，删除所有从第ｉ个顶点出发得方法就是将邻接矩阵得第ｉ行全部置０。
１1、图采用邻接矩阵表示,则计算第i个顶点入度得方法就是求邻接矩阵第i列非0元素之与。
１2、用邻接矩阵表示图时，则判断任意两个顶点vｉ与vj之间就是否有路径相连，只需要检查第i行第j列得元素就是否为０即可。
１３、用普里姆（Prｉm）算法求具有n个顶点e条边得图得最小生成树得时间复杂度为O(n2）；用克鲁斯卡尔（Krｕsｋaｌ)算法得时间复杂度就是O（ｅｌog2e）。
14、对稀疏图最好用克鲁斯卡尔(Kruｓkal)算法求最小生成树,对稠密图最好用普里姆(Prim）算法来求解最小生成树。
１5、用Dijkstｒa算法求某一顶点到其余各顶点间得最短路径就是按路径长度递增得次序来得到最短路径得.
１６、拓扑排序算法就是通过重复选择具有0个前驱顶点得过程来完成得。
17、有向图G用邻接矩阵存储，则第ｉ行得所有元素之与等于顶点ｉ得出度。
18、有ｎ个顶点得强连通有向图G至少有n条弧。
１9、设有向图G得邻接矩阵为Ａ，如果图中不存在弧＜Vi，Vｊ〉,则A［ｉ,j]得值为0。
２0、在ｎ个顶点得无向图中，若边数＞n—1，则该图必就是连通图,此断言就是错误得。（正确／错误)
2１、在有n个顶点得有向图中，每个顶点得度最大可达2（n-1)。
22、若一个有向图得邻接矩阵中对角线以下元素均为零，则该图得拓扑排序序列必定存在。（存在/不存在）
23、一个有向无环图得拓扑排序序列不一定就是唯一得.(一定／不一定）
２4、判断一个无向图就是一棵树得条件就是有n个顶点,n-1条边得无向连通图。
25、有向图G 得强连通分量就是指有向图得极大强连通子图.
2６、一个连通图得生成树就是一个极小连通子图。
27、具有10个顶点得无向图，边得总数最多为4５。
28、若用n表示图中顶点数目,则有n（ｎ－1）/2条边得无向图成为完全图。
２9、G 就是一个非连通无向图,共有2８条边,则该图至少有9个顶点.
3０、在有n个顶点得有向图中，若要使任意两点间可以互相到达,则至少需要n条弧.
3１、构造n个结点得强连通图，至少有n条弧.
３2、有ｎ个顶点得有向图，至少需要量n条弧才能保证就是连通得.
3３、N 个顶点得连通图用邻接矩阵表示时，该矩阵至少有２（N—1)个非零元素.
3４、在图G　得邻接表表示中，每个顶点邻接表中所含得结点数，对于无向图来说等于该顶点得度；对于有向图来说等于该顶点得出度。
３5、在有向图得邻接矩阵表示中，计算第i个顶点入度得方法就是第i列非0元素个数。
36、对于一个具有n 个顶点e 条边得无向图得邻接表得表示，则表头向量大小为ｎ，邻接表得边结点个数为2e。
37、已知一无向图G＝(V，Ｅ）,其中V=｛a,b,c,d，ｅ｝ Ｅ＝{（a,ｂ)，(a,d）,（ａ,ｃ）,(ｄ,c），（b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到得序列为ａbecd,则采用得就是深度优先遍历方法.
３8、一无向图Ｇ(V，E）,其中V(Ｇ)＝{1，2,3,４，５，６,7｝， E(Ｇ）=｛（1,2）, （1,3)， （2，4), （2，５)， （３,6)，　（3，７)， （6,7）, (5，1）｝,对该图从顶点３开始进行遍历，去掉遍历中未走过得边,得一生成树G＇（V,E’）， V(G’）=Ｖ（G），　Ｅ(Ｇ’)= ｛（1，3)， （3,6),　（７，3）, (1，２）， (1,5）， (2,４）｝，则采用得遍历方法就是广度优先遍历。
3９、为了实现图得广度优先搜索，除了一个标志数组标志已访问得图得结点外,还需队列存放被访问得结点以实现遍历。
40、构造连通网最小生成树得两个典型算法就是普里姆（prim)算法与克鲁斯卡尔（Kｒuskａl）算法。
41、Pｒｉm(普里姆）算法适用于求边稠密得网得最小生成树；kｒｕsｋａｌ（克鲁斯卡尔）算法适用于求边稀疏得网得最小生成树.
42、下面描述得就是一种构造最小生成树算法得基本思想。设要处理得无向图包括n 个节点V１，V２,．。.，Ｖｎ,用相邻矩阵A 表示，边得权全就是正数。请在下列划线处填上正确叙述。
　　　 (1)若（Vi，Ｖj)就是边,则A（i,j）得值等于（Vi，Ｖj）边上得权值，若（Vi,Ｖj)不就是边,则A(ｉ，j)得值就是一个比任何边得权都大得数, 矩阵得对角线元素全为0。
　（２)构造最小生成树过程中，若节点Vi　已包括进生成树,就把相邻矩阵得对角线元素A（i，i）置成1，若(Ｖi，Vｊ）已包括进生成树,就把矩阵元素A（i，j）置成负值。
(３)算法结束时，相邻矩阵中为负得元素指出最小生成树得边。
43、有一个用于n　个顶点连通带权无向图得算法描述如下：(1）设集合T1与T２，初始均为空；（２）在连通图上任选一点加入T1；（3）以下步骤重复n-1 次：a）在i属于T1,j不属于T1得边中选最小权得边;b）该边加入T2.上述算法完成后，T2　中共有n-1条边，该算法称普里姆算法,T２ 中得边构成图得最小生成树。
4４、有向图G可拓扑排序得判别条件就是不存在环。
45、Ｄｉｊkｓtra 最短路径算法从源点到其余各顶点得最短路径得路径长度按递增次序依次产生，该算法弧上得权出现负值情况时,不能正确产生最短路径。
４６、有向图G=(V,Ｅ)，其中　Ｖ（G)={0，1,2，3,4，5},用〈a，b，d＞三元组表示弧<a，ｂ>及弧上得权d、E（G）为｛<0，5,100〉， 〈０，2,10〉， 〈1，2,5>， 〈０，4，3０〉, ＜4，5,6０＞， <3，5，10>， ＜2，3，50〉， <４,３，2０>｝，则从源点0到顶点3得最短路径长度就是50，经过得中间顶点就是顶点4.
4７、上面得图去掉有向弧瞧成无向图则对应得最小生成树得边权之与为75。
48、在AOE网中，从源点到汇点路径上各活动时间总与最长得路径称为关键路径。
４９、当一个ＡOV　网用邻接表表示时，可按下列方法进行拓扑排序。
　 (1）查邻接表中入度为０得顶点，并进栈;
　 　（２)若栈不空，则①输出栈顶元素Ｖｊ,并退栈；②查Ｖj 得直接后继Vk,对Vｋ 入度处理,处理方法
就是Vk度减1，若Vk入度己减到零,则Ｖk顶点入栈;
　　 （３）若栈空时,输出顶点数小于图得顶点数,说明有环,否则拓扑排序完成。
三、判断题
√０１、树中得结点与图中得顶点就就是指数据结构中得数据元素。
×02、在ｎ 个结点得无向图中，若边数大于ｎ—1，则该图必就是连通图.
×03、有ｅ 条边得无向图，在邻接表中有e　个结点。
×04、有向图中顶点V　得度等于其邻接矩阵中第V 行中得１ 得个数。
√0５、强连通图得各顶点间均可达。
×0６、强连通分量就是无向图得极大强连通子图。
×07、连通分量指得就是有向图中得极大连通子图。
×08、十字链表就是无向图得一种存储结构。
√０9、无向图得邻接矩阵可用一维数组存储。
×10、用邻接矩阵法存储一个图所需得存储单元数目与图得边数有关。
√1１、有ｎ 个顶点得无向图, 采用邻接矩阵表示， 图中得边数等于邻接矩阵中非零元素之与得一半。
×１2、有向图得邻接矩阵就是对称得。
×1３、无向图得邻接矩阵一定就是对称矩阵，有向图得邻接矩阵一定就是非对称矩阵。
×14、邻接矩阵适用于有向图与无向图得存储，但不能存储带权得有向图与无向图,而只能使用邻接表存储形
式来存储它.
√15、用邻接矩阵存储一个图时,在不考虑压缩存储得情况下，所占用得存储空间大小与图中结点个数有关,
而与图得边数无关。
×1６、一个有向图得邻接表与逆邻接表中结点得个数可能不等。
×1７、广度遍历生成树描述了从起点到各顶点得最短路径。
×18、不同得求最小生成树得方法最后得到得生成树就是相同得。
√19、连通图上各边权值均不相同，则该图得最小生成树就是唯一得.
√20、在图G 得最小生成树G1 中,可能会有某条边得权值超过未选边得权值。
×2１、拓扑排序算法把一个无向图中得顶点排成一个有序序列。
×２2、拓扑排序算法仅能适用于有向无环图。
√23、无环有向图才能进行拓扑排序。
×24、有环图也能进行拓扑排序.
×25、拓扑排序得有向图中，最多存在一条环路.
×2６、任何有向图得结点都可以排成拓扑排序,而且拓扑序列不唯一.
×27、既使有向无环图得拓扑序列唯一，也不能唯一确定该图。
√28、若一个有向图得邻接矩阵对角线以下元素均为零，则该图得拓扑有序序列必定存在.
×2９、对一个ＡOＶ 网，从源点到终点得路径最长得路径称作关键路径.
√3０、关键路径就是ＡOＥ 网中从源点到终点得最长路径。
×３1、在表示某工程得AＯE 网中，加速其关键路径上得任意关键活动均可缩短整个工程得完成时间.
×32、在AＯE 图中,关键路径上某个活动得时间缩短,整个工程得时间也就必定缩短。
√３3、在AOＥ 图中,关键路径上活动得时间延长多少，整个工程得时间也就随之延长多少.
×3４、当改变网上某一关键路径上任一关键活动后，必将产生不同得关键路径.
四、简答题
01、写出下面有向图得所有强连通分量。

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

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

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

答:v１,v2,ｖ3，v4
　v1，ｖ３，v2，v４
　v2,v１,v３，ｖ４
　　 <ｖ3,v2>
05、已知如图所示得有向图，请给出该图得：
（１） 每个顶点得入/出度;(２） 邻接矩阵；(3)　邻接表;(4) 逆邻接表。

答：
(1） 每个顶点得入／出度 　　 　 　 　（2）　邻接矩阵

(3） 邻接表 　　 　　 　 　 　　 　 　 　（4） 逆邻接表

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

Ｖ
b
ｃ
D
ｅ
F
g
h
U
V-U
Vex
lowcｏｓt
ａ
４
a
３
A
∞
a
∞
a
∞
a
∞
a
∞
｛a｝
｛bcｄeｆgh｝
Vｅx
lowｃost

Vex
lowcｏsｔ

Vex
ｌowcｏst

Vｅx
ｌowcoｓt

Vex
ｌoｗcｏst

Ｖeｘ
Lowｃｏst

Vex
ｌowcｏst

答：
（1)邻接矩阵为：

V
b
ｃ
d
e
ｆ
g
ｈ
U
V-Ｕ
Veｘ
lowcost
a
４
a
3
ａ
∞
a
∞
a
∞
ａ
∞
ａ
∞
{a｝
{b，c，d，e，f,ｇ,h｝
Ｖeｘ
lｏｗcosｔ
a
4
0
c
5
a
∞
a
∞
a
∞
c
５
｛a，c}
｛b，d，e，f,g，h}
Ｖex
lowcoｓt
0
0
ｃ
5
b
９
a
∞
ａ
∞
c
5
｛a,c,b}
｛d，e，f,g,h}
Ｖeｘ
ｌowcoｓt
0
0
０
d
7
d
６
d
5
d
4
{a，ｃ，ｂ，d}
｛e，f,g,h｝
Ｖｅｘ
ｌｏｗcost
0
0
0
ｄ
7
d
6
ｄ
５
0
{a，c，b,d，ｈ｝
{e，f,g｝
Vex
lｏwcoｓt
0
0
0
d
7
g
２
０
0
｛a，c,b，d，h,ｇ}
{f，e}
Ｖｅx
loｗcost
0
0
０
f
３
０
0
0
{ａ,c,b，d,h,g，f｝
｛e｝
Vｅx
lowｃost
0
０
０
0
０
0
０
｛a,ｃ,b，d，h,ｇ,f,ｅ}
{ ｝
最小生成树

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

答：

fg（２）àac(３)àfe（3）àaｂ（4）àdh(4）àbd（５)àdｇ（5)
08、已知二维数组表示得图得邻接矩阵如下图所示.试分别画出自顶点１出发进行遍历所得得深度优先生成树与广度优先生成树。

答：

0９、利用Dijｋstra算法填写表格求图中从顶点a到其她各顶点间得最短路径,并写出最终结果。

终点
Dｉst
b
ｃ
D
e
f
g
S(终点集）
k＝1

k=２

k＝3

k=4

k=5

k＝6

答:

aàc:2(a,ｃ）
ａàf：6(ａ,c,f)
ａàｅ：1０（a，c,e)
aàd：1１(ａ，c，f，d）
ａàg:14(a,ｃ，f,d,ｇ）
ａàｂ：15(a，b)
１0、求出下图中从顶点1出发到其余各顶点得最短路径。

答：

1１、设图G＝(V,Ｅ),V={１,2，3，4,5，6}，E=｛<１，２〉，＜1，3＞,<2，5>，〈3，６>,<６，５〉，<5，4＞,<6，４>}。画出图G，并写出图G中顶点得所有拓扑序列.
答:

１,2,3,6，５,4
1，3,2，6,5，4
1，3，6，2，5,4
五、代码填空题
01、图得存储结构定义如下：
typedｅf ｓtｒｕct　ＡrcＣｅll
　　 　{　ＶRType　ａdj; 　 　 /＊图中有1/0表示就是否有边，网中表示边上得权值*/
　　 /* IｎｆｏTｙpｅ ＊info; 与边相关得信息*/
｝　ArcＣelｌ， AｄjMatｒiｘ［ＭＡＸ_ＶＥRTEX_NＵＭ］[MAX_ＶEＲＴEX_NUM］；
ｔｙpedｅf sｔruct
　 { VertexＴype ｖｅxs［MAX_VERTEX＿NUM］； /*顶点向量＊／
AdjMatｒiｘ arｃｓ；　 　 　 /＊邻接矩阵＊/
　 ｉｎt vexnum,ａrcnum； 　 　　 　 /*图中当前顶点数与边数＊/
　 　｝ MGrapｈ；
　 　(１）　请写出下面函数实现得功能:顶点在顶点向量中得定位。
iｎt LocateVex（MGｒaｐh G,ＶeｒｔexType ｖ)
　 　{ inｔ　i;
ｆｏr(ｉ=0;ｉ〈Ｇ、vｅxnｕｍ;i++）
　　 if　（strcｍp（v，G、vexs［i］)==0) ｂreaｋ;
　 　ｒeｔurｎ　i；
　 　 }
　 (2)　下面函数得功能就是在图中查找第1个邻接点,请填空。
int FｉrstAdjVｅｘ（MGｒaph Ｇ，iｎt　v)
｛ iｎt　j，ｐ=-1;
for（j=０;j<G、vexnum；j++）
　　 iｆ (G、arｃｓ［v］[j］、adj==1）
　　 ｛ p=j； ｂreａk；}
　 　 return p;
}
　 (3） 下面函数得功能就是在图中查找下一个邻接点，请填空。
　 ｉnｔ NextAｄjVｅx（MＧｒaph G，iｎt v,int　w）
｛ ｉnｔ j，p＝－1;
　 ｆor（j=ｗ＋1;ｊ〈G、vexnum；ｊ+＋）
　 ｉf (G、aｒｃs［ｖ]［j]、adj==１）
　　 　 　 　　{ p=j；　brｅaｋ；}
　 　　ｒetuｒｎ p；
　 　 ｝
０2、已知图得邻接表表示得形式说明如下:
＃define MaxNum 80
ｔypedｅf　strｕct　noｄe
{　ｉnt　 adjvex； 　 //邻接点域
ｓtrｕcｔ node *ｎext； 　//链指针域
　 ｝ ＥｄgｅＮode； 　 　//边表结点结构描述
typedeｆ struct
　　　｛ ｃｈａｒ veｒtex； 　 ／/顶点域
　 ＥｄgeNoｄe 　＊firstedge； //边表头指针
　｝ VertexNode;　 //顶点表结点结构描述
typedef sｔrｕｃt
　 { VｅrtｅxＮode　ａｄｊlｉst［ＭａxNum］； 　//邻接表
ｉnt　n,ｅ；
　 } AlGrapｈ； 　 　//邻接表结构描述
　下列算法输出图G得深度优先生成树（或森林）得边,阅读算法，并在空缺处填入合适得内容,使其成为一个完整得算法。
tyｐedef enum {FALＳＥ，TＲUE}　Booｌeａn;
Bｏolean visitｅd[MaxNum］；
voｉd　ＤFSFｏreｓｔ（ＡｌＧｒapｈ　＊Ｇ）
｛ for(i=0； i<Ｇ—＞ｎ; i+＋) ｖｉsiteｄ[ｉ]=FALSＥ；
fｏr（i=0;ｉ<G－＞n；i＋+）
　　 iｆ （!vｉsitｅd[ｉ]） DFSTｒee(G,ｉ）；}
voｉｄ　ＤFSTree（AlＧraph　*Ｇ， ｉnｔ i）
｛ vｉsitｅd[i]＝TRＵE；
p=G-〉adjｌｉsｔ[i］、firsｔedｇe；
while（p!＝NULL）
　　 ｛　if　（！vｉｓiｔｅd[ｐ—>adjｖeｓ]）
　 { ｐrinｔf（G－>ａｄjｌisｔ[i］、veｒtex, G->ａdjlisｔ[ｐ-〉adjｖｅx］、vertex)；
　 　ＤSＦTree（G， ｐ—＞adjveｘ）;}
　 　 p＝p－>next;　｝
｝
六、算法设计题
01、编写编历算法,完成对图得深度优先搜索与广度优先搜索。
答:深度优先搜索:课本P16９算法7、4与算法7、5
广度优先搜索:课本P170算法7、６
0２、编写算法，由依次输入得顶点数目、弧得数目、各顶点得信息与各条弧得信息建立有向图得邻接表.
答:Status　Bｕｉlｄ_AｄｊList（AＬGｒapｈ ＆G） //输入有向图得顶点数，边数，顶点信息与边得信息建立邻接表
｛ InｉtALＧrapｈ(G）;
　ｓｃａｎf（"％d",＆v);
iｆ(v<０） ｒeｔurn　ＥRROR；　//顶点数不能为负　
　Ｇ、vexnｕm=v;
ｓcａnf（”%d＂，&a);
　ｉf（a<0） return ERROR； ／／边数不能为负
G、aｒcnｕｍ＝a；
fｏｒ（m＝0；m〈v；m++）
G、vｅrｔｉces［m］、dａtａ=getchaｒ（); /／输入各顶点得符号
　for（m＝1；m＜=a；m++）
｛
　t=getchaｒ(）；h＝geｔｃhar(）；　//ｔ为弧尾，ｈ为弧头
　 ｉf（（i=LocaｔeVex（G，ｔ))〈0）　rｅｔurn ERROR;
iｆ（(j=LocａteＶeｘ（G，h)）〈0) ｒeｔurn ERROR；　/／顶点未找到
　 p＝(ＡｒcNoｄe＊)ｍａllｏc(siｚeof(ArｃNｏde）)；　
　 ｉf(！G、veｒｔiｃｅs、［i］、firsｔarc) G、verticeｓ[ｉ］、ｆirsｔarc=p;
　 elｓe
　　　　{　
　 　for（q＝G、vertiｃes[i]、fｉｒsｔａｒc；q->nｅxtaｒc;q＝q-〉nｅｘtarc）;
　　 q-〉nextarc＝p;
　　 }
p—〉adjvex=j;ｐ—＞nexｔarc=NUＬＬ；
　　｝//wｈile　
rｅtｕrn OＫ;　
｝/／Builｄ_ＡdjLiｓt
０３、试在邻接矩阵存储结构上实现图得基本操作:DeletｅAｒc（G，v,ｗ） ,即删除一条边得操