1、计算机专业基础综合（图）-试卷 2 及答案解析(总分：54.00，做题时间：90 分钟)一、单项选择题(总题数：18，分数：36.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.下面是一个求最小生成树的算法，其中 G 是连通无向图，T 是所求的生成树。 T：=G： While T 中存在回路 do begin 在 T 中找一条权值最大的边 e； T：=T 一e； (T 中去掉 e 边) EnD 试问该算法是哪一种求最小生成树的算法?( )（分数：2.00）A.Prim(普里姆)算法B.Kruskal(克鲁斯卡尔算法)C.罗
2、巴赫算法D.其他算法3.邻接表是图的一种( )。（分数：2.00）A.顺序存储结构B.链接存储结构C.索引存储结构D.散列存储结构4.下面试图对图中路径进行定义，说法正确的是( )。（分数：2.00）A.由顶点和相邻顶点序列构成的边所形成的序列B.由不同顶点所形成的序列C.由不同边所形成的序列D.上述定义都不是5.无向图中顶点个数为 n，那么边数最多为( )。（分数：2.00）A.n 一 1B.n(n 一 1)2C.n(n+1)2D.n 26.在一个具有 n(n0)个顶点的连通无向图中，至少需要的边数是( )。（分数：2.00）A.nB.n+1C.n 一 1D.n27.以下叙述中正确的是( )
3、。 对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图 连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点 图的深度优先搜索中一般要采用栈来暂存访问过的顶点（分数：2.00）A.，B.，C.，D.，8.带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中( )。（分数：2.00）A.第 i 行非的元素之和B.第 i 列非的元素之和C.第 i 行非且非 0 的元素个数D.第 i 列非且非 0 的元素个数9.在一个无向图中，所有顶点的度之和等于边数的( )倍。（分数：2.00）A.12B.1C.2D.410.采用邻接表存储的图的深
4、度优先遍历算法类似于二叉树的( )算法。（分数：2.00）A.前序遍历B.中序遍历C.后序遍历D.按层遍历11.任何一个无向连通图( )最小生成树。（分数：2.00）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在12.判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。（分数：2.00）A.求关键路径的方法B.求最短路径的迪杰斯特拉方法C.深度优先遍历算法D.广度优先遍历算法13.有 n 个顶点 e 条边的无向图，采用邻接表存储时，有( )个表头结点，有( )个链表结点。（分数：2.00）A.n2eB.n2e+1C.n 一 12eD.n 一 12e+114.对于
5、由 n 个顶点组成的有向完全图来说，图中共包含( )条边，对于由 n 个顶点组成的无向完全图来说，图中共包含( )条边。（分数：2.00）A.n，n(n 一 1)B.n，n(n 一 1)2C.2n，n(n 一 1)D.n(n 一 1)，n(n 一 1)215.在一个( )图中寻找拓扑序列的过程称为( )。（分数：2.00）A.有向，拓扑排序B.无向，拓扑排序C.有向，最短路径搜索D.无向，最短路径搜索16.用邻接矩阵 A 表示图，判定任意两个顶点 v i 和 v j 之间是否有长度为 m 的路径相连，则只要检查( )的第 i 行第 j 列的元素是否为零即可。（分数：2.00）A.mAB.AC.
6、A mD.Am-117.当各边上的权值( )时，BFS 算法可用来解决单源最短路径问题。（分数：2.00）A.均相等B.均互不相等C.不一定相等D.不确定18.下面关于图的存储结构的叙述中正确的是( )。（分数：2.00）A.用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关B.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关C.用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关二、综合应用题(总题数：8，分数：18.00)19.综合应用题 41-47 小题。_20.证明：具有 n 个顶点和多于 n 一 1 条
7、边的无向连通图 G 一定不是树。（分数：2.00）_21.证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全 O 的充要条件是该图为无环图。（分数：2.00）_关于图(Graph)的一些问题：（分数：4.00）(1).有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?（分数：2.00）_(2).表示有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?（分数：2.00）_22.如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 1 都集中到对角线以上?（分数：2.00）_23.假定图 G=(V，E)是有向图，V=1，2，N
8、，N1，G 以邻接矩阵方式存储，G 的邻接矩阵为 A，即A 是一个二维数组。如果 i 到 j 有边，则 Ai，j=l，否则 Ai，j=0。请给出一个算法思想，该算法能判断 G 是否是非循环图(即 G 中是否存在回路)，要求算法的时间复杂性为 O(n 2 )。（分数：2.00）_24.对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?（分数：2.00）_G=(V，E)是一个带有权的连通图，如图所示。 （分数：4.00）(1).什么是 G 的最小生成树?（分数：2.00）_(2).G 如图所示，请找出 G 的所有最小生成树。（分数：2.00）_计算机专业基础综合（图
9、）-试卷 2 答案解析(总分：54.00，做题时间：90 分钟)一、单项选择题(总题数：18，分数：36.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.下面是一个求最小生成树的算法，其中 G 是连通无向图，T 是所求的生成树。 T：=G： While T 中存在回路 do begin 在 T 中找一条权值最大的边 e； T：=T 一e； (T 中去掉 e 边) EnD 试问该算法是哪一种求最小生成树的算法?( )（分数：2.00）A.Prim(普里姆)算法B.Kruskal(克鲁斯卡尔算法) C.罗巴赫算法D.其他
10、算法解析：解析：由算法可以看出使用的是 Kruskal 算法。3.邻接表是图的一种( )。（分数：2.00）A.顺序存储结构B.链接存储结构 C.索引存储结构D.散列存储结构解析：解析：图的邻接表存储结构是一种链接存储结构。4.下面试图对图中路径进行定义，说法正确的是( )。（分数：2.00）A.由顶点和相邻顶点序列构成的边所形成的序列 B.由不同顶点所形成的序列C.由不同边所形成的序列D.上述定义都不是解析：解析：由图的定义可知，B 与 C 是错误的。5.无向图中顶点个数为 n，那么边数最多为( )。（分数：2.00）A.n 一 1B.n(n 一 1)2 C.n(n+1)2D.n 2解析：解
11、析：无向图中有 n 个顶点，如果每两个顶点之间均是相互连通的，那么此时无向图中的边数最多，为 n(n1)2。6.在一个具有 n(n0)个顶点的连通无向图中，至少需要的边数是( )。（分数：2.00）A.nB.n+1C.n 一 1 D.n2解析：解析：在无向图中，如果从一个顶点 v i 到另一个顶点 v j (ij)有路径，则称顶点 v i 和 v j 是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以具有 n 个顶点的连通无向图至少有n 一 1 条边。7.以下叙述中正确的是( )。 对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
12、连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点 图的深度优先搜索中一般要采用栈来暂存访问过的顶点（分数：2.00）A.，B.， C.，D.，解析：解析：的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图。、的叙述显然是正确的。8.带权有向图 G 用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中( )。（分数：2.00）A.第 i 行非的元素之和B.第 i 列非的元素之和C.第 i 行非且非 0 的元素个数D.第 i 列非且非 0 的元素个数 解析：解析：有向图的邻接矩阵中，0 和表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出
13、来的。9.在一个无向图中，所有顶点的度之和等于边数的( )倍。（分数：2.00）A.12B.1C.2 D.4解析：解析：在无向图中，一条边计入两个顶点的度数。10.采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )算法。（分数：2.00）A.前序遍历 B.中序遍历C.后序遍历D.按层遍历解析：解析：由图的深度优先遍历算法和二叉树的前序遍历可知选 A。11.任何一个无向连通图( )最小生成树。（分数：2.00）A.只有一棵B.有一棵或多棵 C.一定有多棵D.可能不存在解析：解析：无向连通图应有一棵或多棵最小生成树。12.判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是(
14、)。（分数：2.00）A.求关键路径的方法B.求最短路径的迪杰斯特拉方法C.深度优先遍历算法 D.广度优先遍历算法解析：解析：当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出 I)FSTraverse 算法)即为逆向的拓扑序列。13.有 n 个顶点 e 条边的无向图，采用邻接表存储时，有( )个表头结点，有( )个链表结点。（分数：2.00）A.n2e B.n2e+1C.n 一 12eD.n 一 12e+1解析：解析：根据邻接表的结构，无向图对应的邻接表有 n 个表头结点，有 2e 个链表结点(每条边对应两个链表结点)。14.对于由 n 个顶点组成的有向完全图来说，图中共包
15、含( )条边，对于由 n 个顶点组成的无向完全图来说，图中共包含( )条边。（分数：2.00）A.n，n(n 一 1)B.n，n(n 一 1)2C.2n，n(n 一 1)D.n(n 一 1)，n(n 一 1)2 解析：解析：由完全图的定义可知本题答案为 D。15.在一个( )图中寻找拓扑序列的过程称为( )。（分数：2.00）A.有向，拓扑排序 B.无向，拓扑排序C.有向，最短路径搜索D.无向，最短路径搜索解析：解析：寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序。16.用邻接矩阵 A 表示图，判定任意两个顶点 v i 和 v j 之间是否有长度为 m 的路径相连，则只要检查( )的第 i
16、 行第 j 列的元素是否为零即可。（分数：2.00）A.mAB.AC.A m D.Am-1解析：解析：此题考查的知识点是图的邻接矩阵存储。在图的邻接矩阵中，两点之间有边，则值为 1，否则为 0。本题只要考虑 A m =AAA(m 个 A 矩阵相乘后的乘积矩阵)中(i，j)的元素值是否为 0 就行了。17.当各边上的权值( )时，BFS 算法可用来解决单源最短路径问题。（分数：2.00）A.均相等 B.均互不相等C.不一定相等D.不确定解析：解析：此题考查的知识点是图的 BFS 算法。BFS 是从根结点开始，沿着树的宽度遍历树的结点，如果所有结点均被访问，则算法中止。当各边上的权值相等时，计算边
17、数即可，所以选 A。18.下面关于图的存储结构的叙述中正确的是( )。（分数：2.00）A.用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关 B.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关C.用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关解析：解析：邻接矩阵法的基本思想是对于有 n 个顶点的图，用一维数组 vexsn存储顶点信息，用二维数组 Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在 vexs 数组中的下标代表顶点，邻接矩阵中的元素 Aij存放的是顶点 i 到顶点
18、j 之间关系的信息。 邻接表法的基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第 i 个单链表表示依附于顶点 V i 的边(对有向图是以顶点 V i 为头或尾的弧)。 二、综合应用题(总题数：8，分数：18.00)19.综合应用题 41-47 小题。_解析：20.证明：具有 n 个顶点和多于 n 一 1 条边的无向连通图 G 一定不是树。（分数：2.00）_正确答案：(正确答案：此题考查的知识点是图的定义。具有 n 个顶点 n 一 1 条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于 n 一 1 条，因一条边
19、要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。)解析：21.证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全 O 的充要条件是该图为无环图。（分数：2.00）_正确答案：(正确答案：此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为 0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(Aij=1)自然是落到下三角矩阵中；命题的必
20、要条件是要使上三角为 0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)解析：关于图(Graph)的一些问题：（分数：4.00）(1).有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?（分数：2.00）_正确答案：(正确答案：n(n1)，n)解析：(2).表示有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?（分数：2.00）_正确答案：(正确答案：10 6 ，不一定是稀疏矩阵 提示：此题考查的知识点是图的相关术语。 (1)在有向图 G 中，如果对于每一对 v i ，v
21、j 属于 V，v i 不等于 v j ，从 v i 到 v j 和从 v j 到 v i 都存在路径，则称 G 是强连通图。最多边是所有的顶点每对之间都有边，边数为 n(n 一 1)；最少只有一个方向有边，为 n。 (2)元素个数为矩阵的大小，即 10 6 ，稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律，不一定稀疏。)解析：22.如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 1 都集中到对角线以上?（分数：2.00）_正确答案：(正确答案：此题考查的知识点是图顶点度数。可以按各顶点的出度进行排序。n 个顶点的有向图，其顶点最大出度是 n 一 1，最小出度为 0。这样
22、排序后，出度最大的顶点编号为 1，出度最小的顶点编号为 n 之后，进行调整，即若存在弧i，j，而顶点，的出度大于顶点 i 的出度，则将 j 的编号排在顶点 i 的编号之前。)解析：23.假定图 G=(V，E)是有向图，V=1，2，N，N1，G 以邻接矩阵方式存储，G 的邻接矩阵为 A，即A 是一个二维数组。如果 i 到 j 有边，则 Ai，j=l，否则 Ai，j=0。请给出一个算法思想，该算法能判断 G 是否是非循环图(即 G 中是否存在回路)，要求算法的时间复杂性为 O(n 2 )。（分数：2.00）_正确答案：(正确答案：此题考查的知识点是图的遍历。采用深度优先遍历算法，在执行 DFS(v
23、)时，若在退出 DFS(v)前碰到某顶点 v，其邻接点是已经访问的顶点 v，则说明 v 的子孙 u 有到 v 的回边，即说明有环；否则，无环。)解析：24.对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?（分数：2.00）_正确答案：(正确答案：此题考查的知识点是图的遍历。遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。)解析：G=(V，E)是一个带有权的连通图，如图所示。 （分数：4.00）(1).什么是 G 的最小生成树?（分数：2.00）_正确答案：(正确答案：无向连通图的生成树包含图中全部 n 个顶点，以及足以使图连通的 n 一 1 条边。而最小生成树则是各边权值之和最小的生成树。)解析：(2).G 如图所示，请找出 G 的所有最小生成树。（分数：2.00）_正确答案：(正确答案：最小生成树有两棵。下面给出顶点集合和边集合，编以三元组(V i ，V j ，W)形式，其中 W 代表权值。 V(G)=1，2，3，4，5 E1(G)=(4，5，2)，(2，5，4)，(2，3，5)，(1，2，7)；E2(G)=(4，5，2)，(2，4，4)，(2，3，5)，(1，2，7)解析：
