东北大学：《数据结构》课程教学资源（学习资料）第七章图.doc_P6-P9

38.拓扑排序的有向图中,最多存在一条环路。()【大连海事大学2001一、6(1分)】 39.任何有向图的结点都可以排成拓扑排序,而且拓扑序列不唯一。()【上海交通大学 1998 40.既使有向无环图的拓扑序列唯一,也不能唯一确定该图。()【合肥工业大学2001 二、6(1分)】 41.若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在 () 【中科院软件所1997一、5(1分)】 42.AOV网的含义是以边表示活动的网。()【南京航空航天大学1995五、7(1分)】 43.对一个A0V网,从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学1995 五、9(1分)】 44.关键路径是AOE网中从源点到终点的最长路径。()【青岛大学2000四、10(1分)】 45.AOE网一定是有向无环图。()【青岛大学2001一、9(1分)】 46.在表示某工程的AE网中,加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。() 【长沙铁道学院1997一、2(1分)】 47.在AOE图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。() 【大连海事大学2001一、15(1分)】 48.在AOE图中,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少 () 【大连海事大学2001一、16(1分)】 49.当改变网上某一关键路径上任一关键活动后,必将产生不同的关键路径。【上海交通大学1998 14】、填空题 1.判断一个无向图是一棵树的条件是 2.有向图G的强连通分量是指【北京科技大学1997、7】 3.一个连通图的是一个极小连通子图。【重庆大学2000一、1】 4.具有10个顶点的无向图,边的总数最多为【华中理工大学2000一、7(1分)】 5.若用n表示图中顶点数目,则有条边的无向图成为完全图。【燕山大学1998 6(1分)】 6.设无向图G有n个顶点和e条边,每个顶点Vi的度为di(1<=i<=n),则e 【福州大学1998二、2(2分)】 7.G是一个非连通无向图,共有28条边,则该图至少有个顶点。【西安电子科技大2001软件一、8(2分)】 8.在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要_条弧【合肥工业大学2000三、8(2分)】在有n个顶点的有向图中,每个顶点的度最大可达。【武汉大学2000-、3】 10.设G为具有N个顶点的无向连通图,则G中至少有条边。【长沙铁道学院1997二、2(2分)】 11.n个顶点的连通无向图,其边的条数至少为。【哈尔滨工业大学2000 分)】 12.如果含n个顶点的图形形成一个环,则它有棵生成树【西安电子科技大学2001软件一、2(2分)】

38．拓扑排序的有向图中，最多存在一条环路。（）【大连海事大学 2001 一、6（1 分）】 39．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）【上海交通大学 1998 一、13】 40. 既使有向无环图的拓扑序列唯一，也不能唯一确定该图。（）【合肥工业大学 2001 二、6（1 分）】 41．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）【中科院软件所 1997 一、5 （1 分）】 42．AOV 网的含义是以边表示活动的网。（）【南京航空航天大学 1995 五、7 （1 分）】 43．对一个 AOV 网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天大学 1995 五、9(1 分）】 44. 关键路径是 AOE 网中从源点到终点的最长路径。（）【青岛大学 2000 四、10（1 分）】 45. AOE 网一定是有向无环图。（）【青岛大学 2001 一、9 （1 分）】 46. 在表示某工程的 AOE 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（）【长沙铁道学院 1997 一、2 (1 分)】 47．在 AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（）【大连海事大学 2001 一、15 （1 分）】 48．在 AOE 图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（）【大连海事大学 2001 一、16 （1 分）】 49．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通大学 1998 一、14】三、填空题 1.判断一个无向图是一棵树的条件是______。 2．有向图 G 的强连通分量是指______。【北京科技大学 1997 一、7】 3．一个连通图的______是一个极小连通子图。【重庆大学 2000 一、1】 4．具有 10 个顶点的无向图，边的总数最多为______。【华中理工大学 2000 一、7 （1 分）】 5．若用 n 表示图中顶点数目，则有_______条边的无向图成为完全图。【燕山大学 1998 一、 6（1 分）】 6. 设无向图 G 有 n 个顶点和 e 条边，每个顶点 Vi 的度为 di（1<=i<=n〉，则 e=______ 【福州大学 1998 二、2 (2 分)】 7．G 是一个非连通无向图，共有 28 条边，则该图至少有______个顶点。【西安电子科技大 2001 软件一、8 （2 分）】 8. 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。【合肥工业大学 2000 三、8 （2 分）】 9．在有 n 个顶点的有向图中，每个顶点的度最大可达______。【武汉大学 2000 一、3】 10．设 G 为具有 N 个顶点的无向连通图，则 G 中至少有______条边。【长沙铁道学院 1997 二、2 (2 分)】 11．n 个顶点的连通无向图，其边的条数至少为______。【哈尔滨工业大学 2000 二、2（1 分）】 12．如果含 n 个顶点的图形形成一个环，则它有______棵生成树。【西安电子科技大学 2001 软件一、2 （2 分）】

13.N个顶点的连通图的生成树含有条边。【中山大学1998、9(1分)】 14.构造n个结点的强连通图,至少有条弧。【北京轻工业学院2000一、4(2分)】 15.有N个顶点的有向图,至少需要量条弧才能保证是连通的。【西南交通大学2000一、3】 16.右图中的强连通分量的个数为()个【北京邮电大学2001二、5(2分)】 17.N个顶点的连通图用邻接矩阵表示时,该矩阵至少有个非零元素。【中科院计算所1998一、6(1分)】【中国科技大学1998 6(15/6分)】 18.在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的对于有向图来说等于该顶点的【燕山大学2001二、5(3分)】 19.在有向图的邻接矩阵表示中,计算第I个顶点入度的方法是。【青岛大学2002 三、7(2分)】 20.对于一个具有n个顶点e条边的无向图的邻接表的表示,则表头向量大小为,邻接表的边结点个数为【青岛大学2002三、8(2分)】 21.遍历图的过程实质上是 , breath- first search遍历图的时间复杂度 depth- first search遍历图的时间复杂度两者不同之处在于 ,反映在数据结构上的差别是【厦门大学1999、3】 22.已知一无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)} 现用某一种图遍历方法从顶点a开始遍历图,得到的序列为 abcd,则采用的是遍历方法【南京理工大学1996二、2(2分)】 23.一无向图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)},则采用的遍历方法是【南京理工大学1997三、6(1分)】 24.为了实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需存放被访问的结点以实现遍历。【南京理工大学1999二、9(2分)】 25.按下图所示,画出它的广度优先生成树和深度优先生成树【西安电子科技大学1998三、6(5分)】③ 26.构造连通网最小生成树的两个典型算法是。【北京科技大学1998一、5】 27.求图的最小生成树有两种算法,算法适合于求稀疏图的最小生成树【南京理工大学2001二、6(2分)】

13．N 个顶点的连通图的生成树含有______条边。【中山大学 1998 一、9 （1 分）】 14．构造 n 个结点的强连通图，至少有______条弧。【北京轻工业学院 2000 一、4（2 分）】 15．有 N 个顶点的有向图，至少需要量______条弧才能保证是连通的。【西南交通大学 2000 一、3】 16．右图中的强连通分量的个数为（）个。【北京邮电大学 2001 二、5 （2 分）】 17．N 个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。【中科院计算所 1998 一、6（1 分）】【中国科技大学 1998 一、 6（15/6 分）】 18．在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。【燕山大学 2001 二、5 （3 分）】 19. 在有向图的邻接矩阵表示中，计算第 I 个顶点入度的方法是______。【青岛大学 2002 三、7 （2 分）】 20. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。【青岛大学 2002 三、8 （2 分）】 21. 遍历图的过程实质上是______，breath-first search 遍历图的时间复杂度______； depth-first search 遍历图的时间复杂度______，两者不同之处在于______，反映在数据结构上的差别是______。【厦门大学 1999 一、3】 22. 已知一无向图 G=（V，E），其中 V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)} 现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd，则采用的是______遍历方法。【南京理工大学 1996 二、2 （2 分）】 23. 一无向图 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）}，则采用的遍历方法是______。【南京理工大学 1997 三、6 （1 分）】 24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______ 存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2 分）】 25. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。【西安电子科技大学 1998 三、6 （5 分）】 26．构造连通网最小生成树的两个典型算法是______。【北京科技大学 1998 一、5】 27．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。【南京理工大学 2001 二、6（2 分）】

28.Prim(普里姆)算法适用于求的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求的网的最小生成树。【厦门大学1999一、4】 29.克鲁斯卡尔算法的时间复杂度为它对图较为适合。【中科院计算所1999 、3(2分)】对于含N个顶点E条边的无向连通图,利用Prim算法生成最小代价生成树其时间复杂度为利用 Kruskal算法生成最小代价生成树其时间复杂度为【长沙铁道学院1998二、2(4分)】 31.下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点 Ⅵ1,V2,,Ⅶn,用相邻矩阵A表示,边的权全是正数。请在下列划线处填上正确叙述 (1).若(Vi,Vj)是边,则A(i,j)的值等于,若(Vi,Vj)不是边,则A(i, j)的值是一个比任何边的权矩阵的对角线元素全为 (2).构造最小生成树过程中,若节点Vi已包括进生成树,就把相邻矩阵的对角线元素 A(i,i)置成若(vi,Vj)已包括进生成树,就把矩阵元素A(i,j)置成 (3).算法结束时,相邻矩阵中的元素指出最小生成树的【山东工业大学1998 二、4(6分)】 32.有一个用于n个顶点连通带权无向图的算法描述如下: (1).设集合T1与T2,初始均为空; (2).在连通图上任选一点加入T1: (3).以下步骤重复n-1次: a.在i属于T1,j不属于T1的边中选最小权的边 b.该边加入T2 上述算法完成后,T2中共有条边,该算法称算法,T2中的边构成图的。【南京理工大学1999二、7(4分)】有向图G可拓扑排序的判别条件是【长沙铁道学院1998二、9(2分)】 34. Di jkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按次序依次产生,该算法弧上的权出现情况时,不能正确产生最短路径。【南京理工大学1999二、 8(4分)】 35.求从某源点到其余各顶点的 Di jkstra算法在图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40,计算时间约为ms。【南京理工大学2000二、分)】 6.求最短路径的 Dijkstra算法的时间复杂度为【哈尔滨工业大学2001-、5(2 分)】 37.有向图G=(V,E),其中VG)={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的最短路径长度是_,经过的中间顶点是【南京理工大学1998 三、6(4分)】 38.上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为【南京理工大学1998三、7(4分)】 9.设有向图有n个顶点和e条边,进行拓扑排序时,总的计算时间为【西安电子科技大学1999软件一、7(2分)】【武汉大学2000一、7】 40.AOV网中,结点表示边表示。AOE网中,结点表示边表示【北京理工大学2001七、3(2分)】 41.在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为。【重庆大学 2000

28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。【厦门大学 1999 一、4】 29．克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。【中科院计算所 1999 二、3 （2 分）】 30．对于含 N 个顶点 E 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂度为______，利用 Kruskal 算法生成最小代价生成树其时间复杂度为______。【长沙铁道学院 1998 二、2 (4 分)】 31．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括 n 个节点 V1，V2，．．．，Vn，用相邻矩阵 A 表示，边的权全是正数。请在下列划线处填上正确叙述。（1）．若（Vi，Vj）是边，则 A（i，j）的值等于______，若（Vi，Vj）不是边，则 A（i， j）的值是一个比任何边的权______，矩阵的对角线元素全为 0。（2）．构造最小生成树过程中，若节点 Vi 已包括进生成树，就把相邻矩阵的对角线元素 A（i，i）置成______，若（Vi，Vj）已包括进生成树，就把矩阵元素 A（i，j）置成______。（3）．算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。【山东工业大学 1998 二、4(6 分）】 32. 有一个用于 n 个顶点连通带权无向图的算法描述如下：（1）．设集合 T1 与 T2，初始均为空；（2）．在连通图上任选一点加入 T1；（3）．以下步骤重复 n-1 次： a.在 i 属于 T1，j 不属于 T1 的边中选最小权的边； b.该边加入 T2。上述算法完成后，T2 中共有______条边，该算法称______算法，T2 中的边构成图的______。【南京理工大学 1999 二、7 （4 分）】 33. 有向图 G 可拓扑排序的判别条件是______。【长沙铁道学院 1998 二、9(2 分)】 34. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次产生，该算法弧上的权出现______情况时，不能正确产生最短路径。【南京理工大学 1999 二、 8（4 分）】 35. 求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10，用邻接矩阵表示图时计算时间约为 10ms,则在图的顶点数为 40，计算时间约为______ms。【南京理工大学 2000 二、 3 （1.5 分）】 36．求最短路径的 Dijkstra 算法的时间复杂度为______。【哈尔滨工业大学 2001 一、5 （2 分）】 37.有向图 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的最短路径长度是______，经过的中间顶点是______。【南京理工大学 1998 三、6 （4 分）】 38. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。【南京理工大学 1998 三、7（4 分）】 39．设有向图有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为______。【西安电子科技大学 1999 软件一、7 （2 分）】【武汉大学 2000 一、7】 40．AOV 网中,结点表示______,边表示______。AOE 网中,结点表示______,边表示______。【北京理工大学 2001 七、3 （2 分）】 41．在 AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为______。【重庆大学 2000 一、2】

东北大学：《数据结构》课程教学资源（学习资料）第七章 图

东北大学：《数据结构》课程教学资源（学习资料）第七章图