1、计算机学科专业基础综合数据结构-图(三)及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：34，分数：34.00)1.下面是一个求最小生成树的算法，其中 G是连通无向图，T 是所求的生成树。T:=G;While T中存在回路 dobegin在 T中找一条权值最大的边 e；T:=T-e; (T中去掉 e边)EnD.试问该算法是哪一种求最小生成树的算法?_ A.Prim(普里姆)算法 B.Kruskal(克鲁斯卡尔算法) C.罗巴赫算法 D.其他算法（分数：1.00）A.B.C.D.2.邻接表是图的一种_。 A.顺序存储结构 B.链接存储结构 C.索引存储结构 D
2、.散列存储结构（分数：1.00）A.B.C.D.3.下面试图对图中路径进行定义，说法正确的是_。 A.由顶点和相邻顶点序列构成的边所形成的序列 B.由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是（分数：1.00）A.B.C.D.4.无向图中顶点个数为 n，那么边数最多为_。 A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.n2（分数：1.00）A.B.C.D.5.在一个具有 n(n0)个顶点的连通无向图中，至少需要的边数是_。 A.n B.n+1 C.n-1 D.n/2（分数：1.00）A.B.C.D.6.以下叙述中正确的是_。对有向图 G，如果以任一顶点出发
3、进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点图的深度优先搜索中一般要采用栈来暂存访问过的顶点 A. ， B.， C.， D.，（分数：1.00）A.B.C.D.7.带权有向图 G用邻接矩阵 A存储，则顶点 i的入度等于 A中_。 A.第 i行非的元素之和 B.第 i列非的元素之和 C.第 i行非且非 0的元素个数 D.第 i列非且非 0的元素个数（分数：1.00）A.B.C.D.8.在一个无向图中，所有顶点的度之和等于边数的_倍。 A.1/2 B.1 C.2 D.4（分数：1.00）A.B.C.D.9.采用邻接表存储的
4、图的深度优先遍历算法类似于二叉树的_算法。 A.前序遍历 B.中序遍历 C.后序遍历 D.按层遍历（分数：1.00）A.B.C.D.10.任何一个无向连通图_最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在（分数：1.00）A.B.C.D.11.判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是_。 A.求关键路径的方法 B.求最短路径的迪杰斯特拉方法 C.深度优先遍历算法 D.广度优先遍历算法（分数：1.00）A.B.C.D.12.有 n个顶点 e条边的无向图，采用邻接表存储时，有_个表头结点，有_个链表结点。 A.n，2e B.n，2e+1 C.
5、n-1，2e D.n-1，2e+1（分数：1.00）A.B.C.D.13.对于由 n个顶点组成的有向完全图来说，图中共包含_条边，对于由 n个顶点组成的无向完全图来说，图中共包含_条边。 A.n，n(n-1) B.n，n(n-1)/2 C.2n，n(n-1) D.n(n-1)，n(n-1)/2（分数：1.00）A.B.C.D.14.在一个_图中寻找拓扑序列的过程称为_。 A.有向，拓扑排序 B.无向，拓扑排序 C.有向，最短路径搜索 D.无向，最短路径搜索（分数：1.00）A.B.C.D.15.用邻接矩阵 A表示图，判定任意两个顶点 vi和 vj之间是否有长度为 m的路径相连，则只要检查_的第
6、 i行第 j列的元素是否为零即可。 A.mA B.A C.Am D.Am-1（分数：1.00）A.B.C.D.16.当各边上的权值_时，BFS 算法可用来解决单源最短路径问题。 A.均相等 B.均互不相等 C.不一定相等 D.不确定（分数：1.00）A.B.C.D.17.下面关于图的存储结构的叙述中正确的是_。 A.用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关 B.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关 C.用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关 D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关（分数：1.00）A.B.C.D.1
7、8.在有向图 G的拓扑序列中，若顶点 vi在顶点 vj之前，则下列情形不可能出现的是_。 A.G中有弧v i,vj B.G中有一条从 vi到 vj的路径 C.G中没有弧v i,vj D.G中有一条从 vj到 vi的路径（分数：1.00）A.B.C.D.19.以下关于图的说法中正确的是_。一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的 A.， B.， C.， D.仅有（分数：1.00）A.B.C.D.20.下列关于 AOE网的叙述中，不正确的是_。 A.关键活
8、动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动提前完成，那么整个工程将会提前完成（分数：1.00）A.B.C.D.21.一个二部图的邻接矩阵 A是一个_类型的矩阵。 A.nn矩阵 B.分块对称矩阵 C.上三角矩阵 D.下三角矩阵（分数：1.00）A.B.C.D.22.求解最短路径的 Floyd算法的时间复杂度为_。 A.O(n) B.O(n+c) C.O(n2) D.O(n3)（分数：1.00）A.B.C.D.23.下列 4组含 C1C7 的结点序列中，_是下图所示的有向图的
9、拓扑序列。（分数：1.00）A.B.C.D.24.如果具有 n个顶点的图是一个环，则它有_棵生成树。 A.n2 B.n C.n-1 D.1（分数：1.00）A.B.C.D.25.如下图所示，在下面的 5个序列中，符合深度优先遍历的序列有_个。aebfdc acfdeb aedfcb aefdbc aecfdb（分数：1.00）A.B.C.D.26.无向图 G有 23条边，度为 4的顶点有 5个，度为 3的顶点有 4个，其余都是度为 2的顶点，则图 G最多有_个顶点。 A.11 B.12 C.15 D.16（分数：1.00）A.B.C.D.27.对 AOE网络中有关关键路径的叙述中，正确的是_。
10、 A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间 B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间 C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间 D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间（分数：1.00）A.B.C.D.28.以下关于图的叙述中，正确的是_。 A.强连通有向图的任何顶点到其他所有顶点都有弧 B.图与树的区别在于图的边数大于或等于顶点数 C.无向图的连通分量指无向图中的极大连通子图 D.假设有图 G=V,E，顶点集
11、VV，EE，则 V和E构成 G的子图（分数：1.00）A.B.C.D.29.假设有 n个顶点 e条边的有向图用邻接表表示，则删除与某个顶点 v相关的所有边的时间复杂度为_。 A.O(n) B.O(e) C.O(n+e) D.O(ne)（分数：1.00）A.B.C.D.30.若 G是一个具有 36条边的非连通无向图(不含自回路和多重边)，则图 G的结点数至少是_。 A.11 B.10 C.9 D.8（分数：1.00）A.B.C.D.31.已知有向图 G=(V，A)，其中 V=a，b，c，d，e，A=a,b，a,c，d,c，d,e，b,e，c,e。对该图进行拓扑排序，下面序列中不是拓扑排序的是_。
12、 A.a，d，c，b，e B.d，a，b，c，e C.a，b，d，c，e D.a，b，c，d，e（分数：1.00）A.B.C.D.32.用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为_。 A.5 B.6 C.8 D.9（分数：1.00）A.B.C.D.33.邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：（分数：1.00）A.B.C.D.34.以下关于十字链表的说法中，不正确的是_。 A.十字链表是有向图的另一种链式存储结构 B.行指针 row为矩阵中的行位置，列指针 col为矩阵中的列位置
13、 C.数值 val为矩阵中的值 D.right指针指向矩阵中的行位置，down 指针指向矩阵中的列位置（分数：1.00）A.B.C.D.二、B综合应用题/B(总题数：15，分数：66.00)35.证明：具有 n个顶点和多于 n-1条边的无向连通图 G一定不是树。（分数：5.00）_36.证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全 0的充要条件是该图为无环图。（分数：5.00）_37.关于图(Graph)的一些问题： (1)有 n个顶点的有向强连通图最多有多少条边?最少有多少条边? (2)表示有 1000个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为
14、稀疏矩阵?（分数：5.00）_38.如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 1都集中到对角线以上?（分数：5.00）_39.假定图 G=(V，E)是有向图，V=1，2，N，N1，G 以邻接矩阵方式存储，G 的邻接矩阵为 A，即A是一个二维数组。如果 i到 j有边，则 Ai，j=1，否则 Ai，j=0。请给出一个算法思想，该算法能判断 G是否是非循环图(即 G中是否存在回路)，要求算法的时间复杂性为 O(n2)。（分数：4.00）_40.对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?（分数：4.00）_41.G=(V，E)是一个带有权的连通
15、图，如图所示。 (1)什么是 G的最小生成树? (2)G 如图所示，请找出 G的所有最小生成树。 （分数：4.00）_42.对于如下的加权有向图，给出算法 Dijkstra产生的最短路径的支撑树，设顶点 A为源点，并写出生成过程。（分数：4.00）_43.(1)对于有向无环图，叙述求拓扑有序序列的步骤。 (2)对于以下的图，写出它的 4个不同的拓扑有序序列。 （分数：4.00）_44.试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点 Ui到顶点 Vj的路径(ij)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)（分数：4.00）_45.假设以邻接矩阵作为图的存储结构，编写算法
16、判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)（分数：4.00）_46.已有邻接表表示的有向图，请编程判断从第 u顶点至第 v顶点是否有简单路径，若有则打印出该路径上的顶点。（分数：4.00）_47.“破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)（分数：4.00）_48.设计一个算法求图的中心点。设 v是有向图 G的一个顶点，把 v的偏心度定义为： MA
17、X从 w到 v的最短距离|w 属于 V(G) 如果 v是有向图 G中具有最小偏心度的顶点，则称顶点 v是 G的中心点。（分数：5.00）_49.对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减 1，并对其未访问的、入度为 0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2)定义在算法中使用的全局辅助数组。 (3)写出在遍历图的同时进行拓扑排序的算法。（分数：5.00）_计算机学科专业基础综合数据结构-图(三)答案解析(总分：100.00，做题时间：90 分钟)一
18、、B单项选择题/B(总题数：34，分数：34.00)1.下面是一个求最小生成树的算法，其中 G是连通无向图，T 是所求的生成树。T:=G;While T中存在回路 dobegin在 T中找一条权值最大的边 e；T:=T-e; (T中去掉 e边)EnD.试问该算法是哪一种求最小生成树的算法?_ A.Prim(普里姆)算法 B.Kruskal(克鲁斯卡尔算法) C.罗巴赫算法 D.其他算法（分数：1.00）A.B. C.D.解析：由算法可以看出使用的是 Kruskal算法。2.邻接表是图的一种_。 A.顺序存储结构 B.链接存储结构 C.索引存储结构 D.散列存储结构（分数：1.00）A.B. C
19、.D.解析：图的邻接表存储结构是一种链接存储结构。3.下面试图对图中路径进行定义，说法正确的是_。 A.由顶点和相邻顶点序列构成的边所形成的序列 B.由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是（分数：1.00）A. B.C.D.解析：由图的定义可知，B 与 C是错误的。4.无向图中顶点个数为 n，那么边数最多为_。 A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.n2（分数：1.00）A.B. C.D.解析：无向图中有 n个顶点，如果每两个顶点之间均是相互连通的，那么此时无向图中的边数最多，为n(n-1)/2。5.在一个具有 n(n0)个顶点的连通无向图中
20、，至少需要的边数是_。 A.n B.n+1 C.n-1 D.n/2（分数：1.00）A.B.C. D.解析：在无向图中，如果从一个顶点 vi到另一个顶点 vj(ij)有路径，则称顶点 vi和 vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以具有 n个顶点的连通无向图至少有 n-1条边。6.以下叙述中正确的是_。对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点图的深度优先搜索中一般要采用栈来暂存访问过的顶点 A. ， B.， C.， D.，（分数：1.00）A.B. C.D.
21、解析：的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图。、的叙述显然是正确的。7.带权有向图 G用邻接矩阵 A存储，则顶点 i的入度等于 A中_。 A.第 i行非的元素之和 B.第 i列非的元素之和 C.第 i行非且非 0的元素个数 D.第 i列非且非 0的元素个数（分数：1.00）A.B.C.D. 解析：有向图的邻接矩阵中，0 和表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的。8.在一个无向图中，所有顶点的度之和等于边数的_倍。 A.1/2 B.1 C.2 D.4（分数：1.00）A.B.C. D.解析：在无向图中，一条边计入两
22、个顶点的度数。9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_算法。 A.前序遍历 B.中序遍历 C.后序遍历 D.按层遍历（分数：1.00）A. B.C.D.解析：由图的深度优先遍历算法和二叉树的前序遍历可知选 A。10.任何一个无向连通图_最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在（分数：1.00）A.B. C.D.解析：无向连通图应有一棵或多棵最小生成树。11.判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是_。 A.求关键路径的方法 B.求最短路径的迪杰斯特拉方法 C.深度优先遍历算法 D.广度优先遍历算法（分数：1.00）A
23、.B.C. D.解析：当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出 DFSTraverse算法)即为逆向的拓扑序列。12.有 n个顶点 e条边的无向图，采用邻接表存储时，有_个表头结点，有_个链表结点。 A.n，2e B.n，2e+1 C.n-1，2e D.n-1，2e+1（分数：1.00）A. B.C.D.解析：根据邻接表的结构，无向图对应的邻接表有 n个表头结点，有 2e个链表结点(每条边对应两个链表结点)。13.对于由 n个顶点组成的有向完全图来说，图中共包含_条边，对于由 n个顶点组成的无向完全图来说，图中共包含_条边。 A.n，n(n-1) B.n，n(n-1
24、)/2 C.2n，n(n-1) D.n(n-1)，n(n-1)/2（分数：1.00）A.B.C.D. 解析：由完全图的定义可知本题答案为 D。14.在一个_图中寻找拓扑序列的过程称为_。 A.有向，拓扑排序 B.无向，拓扑排序 C.有向，最短路径搜索 D.无向，最短路径搜索（分数：1.00）A. B.C.D.解析：寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序。15.用邻接矩阵 A表示图，判定任意两个顶点 vi和 vj之间是否有长度为 m的路径相连，则只要检查_的第 i行第 j列的元素是否为零即可。 A.mA B.A C.Am D.Am-1（分数：1.00）A.B.C. D.解析：此题考查
25、的知识点是图的邻接矩阵存储。在图的邻接矩阵中，两点之间有边，则值为 1，否则为0。本题只要考虑 Am=AAA(m个 A矩阵相乘后的乘积矩阵)中(i，j)的元素值是否为 0就行了。16.当各边上的权值_时，BFS 算法可用来解决单源最短路径问题。 A.均相等 B.均互不相等 C.不一定相等 D.不确定（分数：1.00）A. B.C.D.解析：此题考查的知识点是图的 BFS算法。BFS 是从根结点开始，沿着树的宽度遍历树的结点，如果所有结点均被访问，则算法中止。当各边上的权值相等时，计算边数即可，所以选 A。17.下面关于图的存储结构的叙述中正确的是_。 A.用邻接矩阵存储图占用空间大小只与图中顶
26、点数有关，与边数无关 B.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关 C.用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关 D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关（分数：1.00）A. B.C.D.解析：邻接矩阵法的基本思想是对于有 n个顶点的图，用一维数组 vexsn存储顶点信息，用二维数组Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在 vexs数组中的下标代表项点，邻接矩阵中的元素 Aij存放的是顶点 i到顶点 j之间关系的信息。 邻接矩的特点无向图邻接矩阵是对称方阵；在具体存放邻接矩阵时只需存放上(或下)三角矩阵
27、的元素即可。对于顶点vi，其度数是第i行的非0元素的个数。无向图的边数是上(或下)三角形矩阵中非0元素个数。有向图对于顶点vi，第i行的非0元素的个数是其出度OD(vi)。第i列的非0元素的个数是其入度ID(vi)。邻接矩阵中非0元素的个数就是图的弧的数目。邻接表法的基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。 第 i个单链表表示依附于顶点 Vi的边(对有向图是以顶点 Vi为头或尾的弧)。 邻接表法的特点表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目。在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间
28、。在无向图中，顶点Vi的度是第i个链表的结点数。对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度(即为弧的起点)而建立的邻接表。逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表。在有向图中，第i个链表中的结点数是顶点Vi的出(或入)度；求入(或出)度，须遍历整个邻接表。在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点。18.在有向图 G的拓扑序列中，若顶点 vi在顶点 vj之前，则下列情形不可能出现的是_。 A.G中有弧v i,vj B.G中有一条从 vi到 vj的路径 C.G中没有弧v i,vj D.G中有一条从 vj到 vi的路径（分数：1.00）A.B.C.D
29、. 解析：此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点 vi与顶点 vj有一条弧，则拓扑序列中顶点 vi必在顶点 vj之前。若有一条从 vj到 vi的路径，则顶点 vi不可能在顶点 vj之前。所以应选D。19.以下关于图的说法中正确的是_。一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的 A.， B.， C.， D.仅有（分数：1.00）A. B.C.D.解析：说法是正确的，邻接表和逆邻接表的区别仅在于出边和入边，边表的结点个数都等于有向图中的边
30、的个数。说法是正确的，邻接矩阵的空间复杂度为 O(n2)，与边的个数无关。说法是错误的，有向图的邻接矩阵不一定是不对称的，例如，有向完全图的邻接矩阵就是对称的。20.下列关于 AOE网的叙述中，不正确的是_。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动提前完成，那么整个工程将会提前完成（分数：1.00）A.B. C.D.解析：此题考查的知识点是图的关键路径。在 AOE网中，从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并且
31、不只一条。关键路径上的活动称为关键活动。A、C、D 的说法都正确。但任何一个关键活动提前完成，不一定会影响关键路径，所以根据题意应选 B。21.一个二部图的邻接矩阵 A是一个_类型的矩阵。 A.nn矩阵 B.分块对称矩阵 C.上三角矩阵 D.下三角矩阵（分数：1.00）A.B. C.D.解析：此题考查的知识点是二部图的定义与存储。二部图定义为：若能将无向图 G=V，E的顶点集 V划分成两个子集 V1和 V2(V1V2)=*使得 G中任何一条边的两个端点一个属于 V1，另一个属于 V2，则称 G为二部图。由于其特点，其存储矩阵必为分块对称的，所以选 B。22.求解最短路径的 Floyd算法的时间
32、复杂度为_。 A.O(n) B.O(n+c) C.O(n2) D.O(n3)（分数：1.00）A.B.C.D. 解析：23.下列 4组含 C1C7 的结点序列中，_是下图所示的有向图的拓扑序列。（分数：1.00）A.B.C.D. 解析：考查拓扑排序的算法。 以 1开头的拓扑排序过程，如下图所示： * 以 5开头的拓扑排序过程，答案中的过程如下图所示： *24.如果具有 n个顶点的图是一个环，则它有_棵生成树。 A.n2 B.n C.n-1 D.1（分数：1.00）A.B. C.D.解析：因为 n个顶点构成的环共有 n条边，去掉其中任意一条便是一棵生成树，共有 n种情况，所以可以有 n棵不同的生
33、成树。25.如下图所示，在下面的 5个序列中，符合深度优先遍历的序列有_个。aebfdc acfdeb aedfcb aefdbc aecfdb（分数：1.00）A.B.C.D. 解析：本题中，符合深度优先遍历顺序的是 1和 5，其他三个序列均不符合。26.无向图 G有 23条边，度为 4的顶点有 5个，度为 3的顶点有 4个，其余都是度为 2的顶点，则图 G最多有_个顶点。 A.11 B.12 C.15 D.16（分数：1.00）A.B.C.D. 解析：由于在具有 n个顶点 e条边的无向图中，有*，故可求得度为 2的顶点数为 7个，从而最多有 16个顶点。27.对 AOE网络中有关关键路径的
34、叙述中，正确的是_。 A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间 B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间 C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间 D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间（分数：1.00）A. B.C.D.解析：本题考查关键路径的定义。 关键路径：从起点到终点的最长路径长度(路径上各活动持续时间之和)。关键活动：关键路径上的活动称为关键活动。28.以下关于图的叙述中，正确的是_。 A.强连通有向
35、图的任何顶点到其他所有顶点都有弧 B.图与树的区别在于图的边数大于或等于顶点数 C.无向图的连通分量指无向图中的极大连通子图 D.假设有图 G=V,E，顶点集 VV，EE，则 V和E构成 G的子图（分数：1.00）A.B.C. D.解析：强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A 错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若 E中的边对应的顶点不是 V中的元素时，则V和E无法构成图，D 错误。29.假设有 n个顶点 e条边的有向图用邻接表表示，则删除与某个顶点 v相关的所有边的时间复杂度为_。 A.O(n) B.O(e) C.O(n+e) D
36、.O(ne)（分数：1.00）A.B.C. D.解析：删除与某顶点 v相关的所有边的过程如下：先删除下标为 v的顶点表结点的单链表，出边数最多为n-1，对应时间复杂度为 O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为 D(e)。故总的时间复杂度为 O(n+e)。30.若 G是一个具有 36条边的非连通无向图(不含自回路和多重边)，则图 G的结点数至少是_。 A.11 B.10 C.9 D.8（分数：1.00）A.B. C.D.解析：n 个顶点构成的无向图中，边数n(n-1)/2，将 e=36代入，有 n9，现已知无向图是非连通的，则 n至少为 10。31.已知有向图 G=(V，
37、A)，其中 V=a，b，c，d，e，A=a,b，a,c，d,c，d,e，b,e，c,e。对该图进行拓扑排序，下面序列中不是拓扑排序的是_。 A.a，d，c，b，e B.d，a，b，c，e C.a，b，d，c，e D.a，b，c，d，e（分数：1.00）A.B.C.D. 解析：选项 D中，删去 a、b 及其对应的出边后，c 的入度不为 0，因此有边d，c，故不是拓扑序列。选项 A、B、C 均为拓扑序列。解答本类题时，建议读者根据边集合画出草图。32.用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为_。 A.5 B.6 C.8 D.9（分数：1.00）A. B.C.D.解析
38、：此题考查的知识点是有向无环图的定义。有向无环图是一个无环的有向图，可以用来表示公共子表达式，本题中出现的 5个字符作为 5个顶点，其中 A+B和 A可共用，所以至少 5个即可，选 A。33.邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：（分数：1.00）A.B.C. D.解析：顶点表由两个域组成，vertex 域存储和该顶点相关的信息，firstedge 域指示第一条依附于该顶点的边。边表结点由六个域组成：mark 为标记域，用以标记该条边是否被搜索过；ivex 和 jvex为该边依附的两个顶点在图中的位置；il
39、ink 指向下一条依附于顶点 ivex的边；jlink 指向下一条依附于顶点 jvex的边；info 为指向和边相关的各种信息的指针域。34.以下关于十字链表的说法中，不正确的是_。 A.十字链表是有向图的另一种链式存储结构 B.行指针 row为矩阵中的行位置，列指针 col为矩阵中的列位置 C.数值 val为矩阵中的值 D.right指针指向矩阵中的行位置，down 指针指向矩阵中的列位置（分数：1.00）A.B.C.D. 解析：right 指向右侧的一个非零元素，down 指向下侧的一个非零元素。二、B综合应用题/B(总题数：15，分数：66.00)35.证明：具有 n个顶点和多于 n-1
40、条边的无向连通图 G一定不是树。（分数：5.00）_正确答案：(此题考查的知识点是图的定义。具有 n个顶点 n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于 n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。)解析：36.证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全 0的充要条件是该图为无环图。（分数：5.00）_正确答案：(此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(Aij=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为 0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)解析：37.关于图(Graph)的一些问题： (1)有 n个顶点的有向强连通图最多有多少条边?最少有多少条边? (2)表示有 1000个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?（分数：5.00）_
