大学MOOC 数据结构与算法2（张淼 2020年秋）(大连理工大学)1460924164 最新慕课完整章节测试答案

第一课测验

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: 15
C: 16
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? ()​‎​
选项：
A: Dijkstra algorithm
B: Kruskal algorithm
C: Depth-First-Search algorithm
D: Topological-Sort algorithm
答案: 【 Dijkstra algorithm】

3、单选题：
‏The time complexity of Floyd algorithm which solves the problem of shortest path is ().​
选项：
A: O(n)
B: O(n+e)
C: O(n*n)
D: O(n*n*n)
答案: 【 O(n*n*n)】

4、单选题：
‍任何一个无向连通图的最小生成树（）。‌
选项：
A: 有一棵或多棵
B: 只有一棵
C: 一定有多棵
D: 可能不存在
答案: 【 有一棵或多棵】

5、单选题：
‌下列关于最小生成树的叙述中，正确的是（）。​Ⅰ  最小生成树的代价唯一​Ⅱ  所有权值最小的边一定会出现在所有的最小生成树中​Ⅲ  使用Prim算法从不同顶点开始得到的最小生成树一定相同​IV  使用Prim算法和Kruskal算法得到最小生成树总不相同​‌      ​
选项：
A: 仅Ⅰ
B: 仅Ⅱ
C: 仅Ⅰ、Ⅲ
D: 仅Ⅱ、Ⅳ
答案: 【 仅Ⅰ】

6、单选题：
‏以下叙述中，正确的是（）。​
选项：
A: 只要无向连通图中没有权值相同的边，则其最小生成树唯一
B: 只要无向图中有权值相同的边，则其最小生成树一定不唯一
C: 从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树
D: 设连通图G含有n个顶点，则含有n个顶点、n-1条边的子图一定是G的生成树
答案: 【 只要无向连通图中没有权值相同的边，则其最小生成树唯一】

7、单选题：
‏以下叙述中，正确的是（）。​
选项：
A: 最短路径一定是简单路径
B: Dijkstra算法不适合求有回路的带权图的最短路径
C: Dijkstra算法不适合求任意两个顶点的最短路径
D: Floyd算法求两个顶点的最短路径时，一定是的子集
答案: 【 最短路径一定是简单路径】

8、单选题：

​Given the undirected graph  and . If  is the spanning tree of , the false one in the following statement is ().

‎选项：
A:  is a subgraph of 
B:  is a connected component of
C:  is a minimal connected subgraph of  and 
D:  is an acyclic subgraph of 
答案: 【  is a connected component of】

9、单选题：

‏Given the adjacency matrix of a weighted un