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 分）】