MOOC 数据结构与算法2(张淼 2021年秋)(大连理工大学)1464533217 最新慕课完整章节测试答案
第一课
第一课单元测验
1、单选题：
设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是 。
选项：
A: n/2
B: n(n+1)
C: nk-2m
D: n(k+1)-2m
答案: 【 n(k+1)-2m】
2、单选题：
设无向图的顶点个数为n，则该图最多有 条边。
选项：
A: n-1
B: n(n-1)/2
C: n(n+1)/2
D: n^2
答案: 【 n(n-1)/2 】
3、单选题：
图中有关路径的定义是
选项：
A: 由顶点和相邻顶点序偶构成的边所形成的序列
B: 由不同顶点形成的序列
C: 由不同边形成的序列
D: 上述定义都不是
答案: 【 由顶点和相邻顶点序偶构成的边所形成的序列】
4、单选题：
若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）
选项：
A: 强连通图
B: 连通图
C: 有回路
D: 一棵树
答案: 【 连通图】
5、单选题：
下列关于图的叙述中，正确的是（）①回路是简单路径②存储稀疏图，用邻接矩阵比邻接表更省空间③若有向图中存在拓扑序列，则该图不存在回路
选项：
A: 仅②
B: 仅①、②
C: 仅③
D: 仅①、③
答案: 【 仅③】
6、单选题：
下列关于无向连通图特性的叙述中，正确的是（）①所有顶点的度之和是偶数②边数大于顶点个数减1③至少有一个顶点的度为1
选项：
A: 仅①
B: 仅②
C: 仅①、②
D: 仅①、③
答案: 【 仅①】
7、单选题：
以下关于图的叙述中，正确的是()
选项：
A: 强连通有向图的任何顶点到其他所有顶点都有弧
B: 图的任意顶点的入度等于出度
C: 有向完全图一定是强连通有向图
D: 有向图的边集的子集和顶点集的子集可构成原有向图的子图
答案: 【 有向完全图一定是强连通有向图】
8、单选题：
对于一个有n个顶点的图，若是连通无向图，其边的个数至少为（）；若是强连通有向图，其边的个数至少为（）
选项：
A: n-1，n
B: n-1, n(n-1)
C: n, n
D: n, n(n-1)
答案: 【 n-1，n】
9、单选题：
无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有（）个顶点
选项：
A: 11
B: 12
C: 15
D: 16
答案: 【 16】
10、单选题：
在有n个顶点的有向图中，每个顶点的度最大可达()
选项：
A: n
B: n-1
C: 2n
D: 2n-2
答案: 【 2n-2】
第二课
第二课单元测验
1、单选题：
In a undirected graph with n vertexs, the maximum edges is ().
选项：
A: n(n+1)/2
B: n(n-1)/2
C: n(n-1)
D: n*n
答案: 【 n(n-1)/2】
2、单选题：
In a directed graph with n vertexs, the maximum degree of each vertex is ().
选项：
A: n
B: n-1
C: 2n
D: 2n-2
答案: 【 2n-2】
3、单选题：
In a graph with n vertexs and e edges, the space complexity represented by the adjacency matrix is ().
选项：
A: O(n)
B: O(e)
C: O(n+e)
D: O(n*n)
答案: 【 O(n*n)】
4、单选题：
In the adjacency matrix of an undirected graph with n vertexs and e edges, the number of zero elements is ().
选项：
A: e
B: 2e
C: n*n-e
D: n*n-2e
答案: 【 n*n-2e】
5、单选题：
In a directed graph, the sum of in-degrees of all vertexs is equal to () times the sum of out-degrees of all vertexs.
选项：
A: 1/2
B: 1
C: 2
D: 4
答案: 【 1】
6、单选题：
Assuming that a directed graph with n vertexs and e edges is represented by an adjacency list, the time complexity of deleting all edges related to a certain vertex v is ().
选项：
A: O(n)
B: O(e)
C: O(n+e)
D: O(n*e)
答案: 【 O(n+e)】
7、单选题：
The undirected graph G=(V,E), where V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}, performs DFS of the graph, which of the following vertex sequence is correct? ()
选项：
A: a,b,e,c,d,f
B: a,c,f,e,b,d
C: a,e,b,c,f,d
D: a,e,d,f,c,b
答案: 【 a,e,d,f,c,b】
8、单选题：
一个有n个顶点和n条边的无向图一定是（）。
选项：
A: 连通的
B: 不连通的
C: 无环的
D: 有环的
答案: 【 有环的】
9、单选题：
若无向图G=(V, E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（）
选项：
A: 6
B: 16
C: 15
D: 21
答案: 【 16】
10、单选题：
若邻接表中有奇数个边表结点，则一定是（）
选项：
A: 图中有奇数个结点
B: 图中有偶数个结点
C: 图为无向图
D: 图为有向图
答案: 【 图为有向图】
11、单选题：
n个顶点的无向图的邻接表最多有（）个边表结点。
选项：
A: n*n
B: n(n-1)
C: n(n+1)
D: n(n-1)/2
答案: 【 n(n-1) 】
12、单选题：
用邻接表存储的图的深度优先遍历算法类似于树的（）
选项：
A: 中序遍历
B: 先序遍历
C: 后序遍历
D: 层次遍历
答案: 【 先序遍历】
13、单选题：
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）。
选项：
A: h,c,a,b,d,e,g,f
B: e,a,f,g,b,h,c,d
C: d,b,c,a,h,e,f,g
D: a,b,c,d,h,e,f,g
答案: 【 a,b,c,d,h,e,f,g】
14、单选题：
下列选项中，不是下图深度优先搜索序列的是（）
选项：
A: v1,v5,v4.v3,v2
B: v1,v3,v2,v5,v4
C: v1,v2,v5,v4,v3
D: v1,v2,v3,v4,v5
答案: 【 v1,v2,v3,v4,v5】
15、单选题：
设有向图G=(V, E)，顶点集V={V0,V1,V2,V3}，边集 E={<v0,v1>,<v0,v2>,<v0,v3>,<v1,v3>}。 若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）
选项：
A: 2
B: 3
C: 4
D: 5
答案: 【 5】
第三课
第三课单元测验
1、单选题：
If a graph with n vertexes is an annulus, then it has () spanning trees.
选项：
A: n*n
B: n
C: n-1
D: 1
答案: 【 n】
2、单选题：
Which of the following algorithms is most suitable to solve the problem of finding the most economical flight route between given two cities when a directed graph is used to represent the routes of all flights of an airline? ()&l