2020 数据结构与算法2（张淼 2020年秋）(大连理工大学) 最新满分章节测试答案
本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-09-16到2020-11-10
本篇答案更新状态:已完结
【作业】第一课 第一课作业
1、 问题:
评分规则: 【 
】
第一课 第一课测验
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(nn)
答案: 【O(nn)】
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:nn-e
D:nn-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={
选项：
A:2
B:3
C:4
D:5
答案: 【5】
【作业】第二课 第二课作业
1、 问题:
评分规则: 【 
】
2、 问题:
评分规则: 【 
】
3、 问题:证明在图中边权为负时，Dijkstra算法不能正常运行。
评分规则: 【 
】
4、 问题:如果图中存在负的边权，那么Prim算法或Kruskal算法还能正常运行吗？举例说明。
评分规则: 【 
】
5、 问题:Dijkstra算法如何应用到无向图？
评分规则: 【 
】
第二课 第二课测验
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(nn)
D:O(nnn)
答案: 【O(nn*n)】
4、 问题:任何一个无向连通图的最小生成树（）。
选项：
A:有一棵或多棵
B:只有一棵
C:一定有多棵
D:可能不存在
答案: 【有一棵或多棵】
本文章不含期末不含主观题！！
本文章不含期末不含主观题！！
支付后可长期查看
有疑问请添加客服QQ 2356025045反馈
如遇卡顿看不了请换个浏览器即可打开
请看清楚了再购买哦，电子资源购买后不支持退款哦
