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

一、单选题C1、在一个图中，所有顶点得度数之与等于图得边数得 倍。 ）1/2 B）1 ）2 D)B02、在一个有向图中,所有顶点得入度之与等于所有顶点得出度之与得 倍。 )1/2 B）1 C） ）4、有8个结点得无向图最多有 条边。 A)4 B）8 C）56 D）104、有个结点得无向连通图最少有 条边. A）5 B）6 C）7 D)C5、有个结点得有向完全图有 条边。 A)1 )2 C）56 D）11B06、用邻接表表示图进行广度优先遍历时，通常就是采用 来实现算法得。 A)栈 B）队列 C）树 D）图A07、用邻接表表示图进行深度优先遍历时，通常就是采用 来实现算法得。 A）栈 )队列 C)树 D）图0、一个含个顶点与e条弧得有向图以邻接矩阵表示法为存储结构,则计算该有向图中某个顶点出度得时间复杂度为 。 ）(n) B）O(e) C)(n+e) D)O（)C09、已知图得邻接矩阵，根据算法思想,则从顶点出发按深度优先遍历得结点序列就是 . A）0 2 15 6 ）0 3 5 2 C)0 1 4 2 56 D）0 6 1 5 4 B10、已知图得邻接矩阵同上题，根据算法,则从顶点出发,按广度优先遍历得结点序列就是 . A）0 2 3 6 1 B)1 23 4 6 5 C）0 2 15 )0 3 4 61、已知图得邻接表如下所示，根据算法,则从顶点出发按深度优先遍历得结点序列就是 。 A）0 3 2 B) 2 1 C) 321 D）01 2 3A12、已知图得邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历得结点序列就是 . A)0 32 )0 1 2 C）0 1 3 2 D）0 3 A13、图得深度优先遍历类似于二叉树得 。 ）先序遍历 B)中序遍历 C）后序遍历 D）层次遍历D1、图得广度优先遍历类似于二叉树得 。 A)先序遍历 B）中序遍历 C）后序遍历 D）层次遍历B5、任何一个无向连通图得最小生成树 。 A)只有一棵 B)一棵或多棵 C)一定有多棵 )可能不存在A6、对于一个具有n个结点与条边得无向图，若采用邻接表表示,则顶点表得大小为 ，所有边链表中边结点得总数为 。 A）n、2e B)n、e C)n、n+ ）2n、21、判断有向图就是否存在回路,可以利用_算法。 A)关键路径 ）最短路径得Dijsa C)拓扑排序 D）广度优先遍历A18、若用邻接矩阵表示一个有向图,则其中每一列包含得“1”得个数为 。 )图中每个顶点得入度 B)图中每个顶点得出度 ）图中弧得条数 D)图中连通分量得数目C9、求最短路径得Djka算法得时间复杂度就是_. A）（n) B)O(+e) C）（n2) D)O（e)B0、设图采用邻接表存储,则拓扑排序算法得时间复杂度为 . A)O(n） B)O（n+e） C）O(n2） D）O（ne）、带权有向图用邻接矩阵A存储,则顶点得入度等于A中 . A）第i行非得元素之与 B）第i列非得元素之与 ）第行非且非0得元素个数 ）第i列非且非0得元素个数C22、一个有n个顶点得无向图最多有 条边。 ）n B）（n) ）n（1)/ )2nD23、对于一个具有n个顶点得无向图，若采用邻接矩阵表示，则该矩阵得大小就是 。 )n B）(n1）2 C）n-1 ）n224、对某个无向图得邻接矩阵来说， . A)第行上得非零元素个数与第i列得非零元素个数一定相等 B)矩阵中得非零元素个数等于图中得边数 C)第行上，第列上非零元素总数等于顶点vi得度数 D）矩阵中非全零行得行数等于图中得顶点数D25、已知图得表示如下,若从顶点出发按深度搜索法进行遍历，则可能得到得一种顶点序列为 。 ）abecd B）afebd )aebcfd ）edfcb26、已知图得表示如上题，若从顶点出发按广度搜索法进行遍历，则可能得到得一种顶点序列为 。 ）abcedf ）ace C)abcfd D）afdeb27、有向图得邻接表存储结构如下图所示，则根据有向图得深度遍历算法，从顶点出发得到得顶点序列就是 。 A)v,2，v3，v5,v4 B）v1,v2，3,v4,v5 )v1，v3，v4,5，v2 D)v1，4，v,v5，v2B2、有向图得邻接表存储结构如上题所示,则根据有向图得广度遍历算法,从顶点1出发得到得顶点序列就是 。 A）1,2,v3，v4,v5 )v1,v3，2，4,v C）,v2,v3,5，4 D)v1,v4,v3，v5，2A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用 次深度优先遍历算法. ）k B) C)n )n0、以下不正确得说法就是 。 ）无向图中得极大连通子图称为连通分量 B)连通图得广度优先搜索中一般要采用队列来暂存刚访问过得顶点 C)图得深度优先搜索中一般要采用栈来暂存刚访问过得顶点 ）有向图得遍历不可采用广度优先搜索方法A31、图中有关路径得定义就是_。 A）由顶点与相邻顶点序偶构成得边所形成得序列 ）由不同顶点所形成得序列 C）由不同边所形成得序列 D)上述定义都不就是B32、设无向图得顶点个数为n,则该图最多有_条边。 )n-1 B）n(n-)/ C）n(n+1)/2 D）nA33、一个个顶点得连通无向图,其边得个数至少为_. A)n B) )+1 D）nlognB4、要连通具有n 个顶点得有向图,至少需要_条边. A）n ）n C）n+l D）n3、在一个无向图中,所有顶点得度数之与等于所有边数_倍. A）1/2 )2 C)1 D）C、在一个有向图中,所有顶点得入度之与等于所有顶点出度之与得_倍。 A）1/ B）2 C） D）、用有向无环图描述表达式(A+B)*（(+)A）,至少需要顶点得数目为_。 A）5 B）6 ）8 D)9A38、用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得度就是_。 B2、下列说法不正确得就是_。 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)abd B)acfb C）aebcfd D)aedfcbD44、如图所示，在5个序列“aebfc、cfde、aedfcb、aefdb、afdbc”，符合深度优先遍历得序列有_个。 A）5 B） ) D）2C45、图中给出由7个顶点组成得无向图。从顶点1出发，对它进行深度优先遍历得到得序列就是 ，进行广度优先遍历得到得顶点序列就是 。 A）1354267 B） C)1534276 D）24653 E）以上答案均不正确 A） B)1245 C）l35276 D)147653 E)以上答案均不正确46、在图采用邻接表存储时，求最小生成树得Pim算法得时间复杂度为. A)O() B）O（n） C）O（n2） D)O（)CAA47、下面就是求连通网得最小生成树得pm算法：集合VT，E分别放顶点与边,初始为 ，下面步骤重复n1次： ；最后： 。 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中有n1条边时为生成树，否则无解 D）ET中无回路时，为生成树,否则无解、下面不正确得就是_. 求从指定源点到其余各顶点得Djktra最短路径算法中弧上权不能为负得原因就是在实际应用中无意义; 利用Dijsra求每一对不同顶点之间得最短路径得算法时间就是O（n3）;（图用邻接矩阵表示） ld求每对不同顶点对得算法中允许弧上得权为负，但不能有权与为负得回路。 A） ) C） D)A49、已知有向图G=(V，E）,其中=V1,V2，V3,V,V5，V6，V,EV1,V， 1，V3， V，V4， V2,V5, ， V3,V6, ， 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）中有弧 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列得元素就是否为即可。、用普里姆（Prm）算法求具有n个顶点e条边得图得最小生成树得时间复杂度为O(n2）；用克鲁斯卡尔（Krsa)算法得时间复杂度就是O（og2e）。14、对稀疏图最好用克鲁斯卡尔(Krukal)算法求最小生成树,对稠密图最好用普里姆(Prim）算法来求解最小生成树。5、用Dijksta算法求某一顶点到其余各顶点间得最短路径就是按路径长度递增得次序来得到最短路径得.、拓扑排序算法就是通过重复选择具有0个前驱顶点得过程来完成得。17、有向图G用邻接矩阵存储，则第行得所有元素之与等于顶点得出度。18、有个顶点得强连通有向图G至少有n条弧。9、设有向图G得邻接矩阵为，如果图中不存在弧Vi，V,则A,j得值为0。0、在个顶点得无向图中，若边数n1，则该图必就是连通图,此断言就是错误得。（正确错误)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 个顶点得连通图用邻接矩阵表示时，该矩阵至少有（N1)个非零元素.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)算法与克鲁斯卡尔（Kuskl）算法。41、Pm(普里姆）算法适用于求边稠密得网得最小生成树；ks（克鲁斯卡尔）算法适用于求边稀疏得网得最小生成树.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、ktra 最短路径算法从源点到其余各顶点得最短路径得路径长度按递增次序依次产生，该算法弧上得权出现负值情况时,不能正确产生最短路径。、有向图G=(V,)，其中（G)=0，1,2，3,4，5,用a，b，d三元组表示弧及弧上得权d、E（G）为， ，4，3, 4，5,6， ， 2，3，50， ，则从源点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、在表示某工程得AE 网中，加速其关键路径上得任意关键活动均可缩短整个工程得完成时间.32、在AE 图中,关键路径上某个活动得时间缩短,整个工程得时间也就必定缩短。3、在AO 图中,关键路径上活动得时间延长多少，整个工程得时间也就随之延长多少.3、当改变网上某一关键路径上任一关键活动后，必将产生不同得关键路径.四、简答题01、写出下面有向图得所有强连通分量。答:3个，分别就是:，bce，dfg02、已知图得邻接表如下,画出图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， 05、已知如图所示得有向图，请给出该图得：（） 每个顶点得入/出度;(） 邻接矩阵；(3)邻接表;(4) 逆邻接表。答：(1） 每个顶点得入出度 （2）邻接矩阵 (3） 邻接表 （4） 逆邻接表 6、写出无向带树图得邻接矩阵，并按普里姆算法填写表格中得内容，最后画出最小生成树；bDFghUV-UVexlowctaAaaaaabceghVxlowostVexlowcsVexowcstVxowcotVexocsteLowstVexowcst答：（1)邻接矩阵为：VbdegUV-Velowcostaa3aaab，c，d，e，f,helcosa40c5aaaca，cb，d，e，f,g，hexlowcot005bac5a,c,bd，e，f,g,heowcot00d7dd5d4a，de，f,g,hcost0007d60a，c，b,d，e，f,gVexlwcot000d7g0a，c,b，d，h,f，exlocost00f00,c,b，d,h,g，feVxlowost000a,b，d，h,f, 最小生成树0、按克鲁斯卡尔算法写出下面无向带权图求最小生成树产生得边序列。答：fg（）ac()fe（3）a（4）dh(4）bd（)d（5)08、已知二维数组表示得图得邻接矩阵如下图所示.试分别画出自顶点出发进行遍历所得得深度优先生成树与广度优先生成树。答：0、利用Dijstra算法填写表格求图中从顶点a到其她各顶点间得最短路径,并写出最终结果。终点DstbDefgS(终点集）k1k=k3k=4k=5k6答:ac:2(a,）f：6(,c,f)：1（a，c,e)ad：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,，3，,，5，4,。画出图G，并写出图G中顶点得所有拓扑序列.答:,2,3,6，,41，3,2，6,5，41，3，6，2，5,4五、代码填空题01、图得存储结构定义如下：typedf tctrcll RTypedj; /图中有1/0表示就是否有边，网中表示边上得权值*/ /* ITp info; 与边相关得信息*/ Arcel， AjMati_RTEX_NMAX_EEX_NUM；pedf sruct Vertexype xsMAX_VERTEXNUM； /*顶点向量 AdjMati ar； /邻接矩阵/ t vexnum,rcnum； /*图中当前顶点数与边数/ MGrap； (）请写出下面函数实现得功能:顶点在顶点向量中得定位。 it LocateVex（MGah G,eexType ) ini; r(=0;、vxn;i+） if（strcp（v，G、vexsi)=0) rea; euri； (2)下面函数得功能就是在图中查找第1个邻接点,请填空。 int FrstAdjV（MGaph ，itv) itj，=-1; for（j=;jG、vexnum；j+） i (G、arvj、adj=1） p=j； rek； return p; (3） 下面函数得功能就是在图中查找下一个邻接点，请填空。 n NextAjVx（Maph G，it v,intw） n j，p1; or（j=1;G、vexnum；+） f (G、asj、adj=） p=j；bra； etu p； 2、已知图得邻接表表示得形式说明如下:define MaxNum 80ypedfstrctnoe nt adjvex； /邻接点域 trc node *ext； /链指针域 gode； /边表结点结构描述typede struct vetex； /顶点域 geNoe firstedge； /边表头指针 VertexNode; /顶点表结点结构描述typedef srt VrtxodelstxNum； /邻接表 ntn,； AlGrap； /邻接表结构描述 下列算法输出图G得深度优先生成树（或森林）得边,阅读算法，并在空缺处填入合适得内容,使其成为一个完整得算法。tyedef enum FAL，TUEBooen;Bolean visitdMaxNum；vodFSFre（ap） for(i=0； i; i+) site=FALS； fr（i=0;adje） rinf（Gjisi、vetex, G-djlis-adjx、vertex)； STree（G， adjve）; ppnext;六、算法设计题01、编写编历算法,完成对图得深度优先搜索与广度优先搜索。答:深度优先搜索:课本P16算法7、4与算法7、5 广度优先搜索:课本P170算法7、0、编写算法，由依次输入得顶点数目、弧得数目、各顶点得信息与各条弧得信息建立有向图得邻接表.答:StatusBl_AList（AGap G） /输入有向图得顶点数，边数，顶点信息与边得信息建立邻接表 IntALrap(G）; f（d,v); i(v） eurnRROR；/顶点数不能为负 、vexnm=v; cnf（”%d，&a); f（anxtac;qq-ntarc）; q-nextarcp; padjvex=j;nexarc=NU； /wile rtrn O;/Buil_djLit 、试在邻接矩阵存储结构上实现图得基本操作:DeletAc（G，v,） ,即删除一条边得操