2021 数据结构与算法2(张淼 2021年秋)(大连理工大学) 最新满分章节测试答案
本答案对应课程为:点我自动跳转查看
本课程起止时间为:2021-09-06到2021-11-07
本篇答案更新状态:已完结
第一课 第一课单元测验
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、 问题:图G是一个非连通无向图，共有28条边，该图至少有几个顶点？
评分规则: 【 9
】
第二课 第二课单元测验
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: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:层次遍历
本文章不含期末不含主观题！！
本文章不含期末不含主观题！！
支付后可长期查看
有疑问请添加客服QQ 2356025045反馈
如遇卡顿看不了请换个浏览器即可打开
请看清楚了再购买哦，电子资源购买后不支持退款哦
