2020 数据结构（石连栓）(天津职业技术师范大学) 最新满分章节测试答案

文章目录[隐藏]

第七章图第七章图单元测试
第一章绪论第一章绪论单元测试
第二章线性表第二章线性表单元测试
第六章树与二叉树第六章树单元测试
第九章查找第九章查找单元测试
第十章内部排序第十章内部排序单元测试
第三章栈和队列第三章栈和队列单元测试

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-12-10到2021-02-24
本篇答案更新状态:已完结

第七章图第七章图单元测试

1、问题:设有5个结点的无向图，该图至少应有___条边才能确保是一个连通图。
选项：
A:5
B:6
C:7
D:8
答案: 【7】

2、问题:设图G=(V,VR)，其中: V={A,B,C,D,G}，VR={(A,C),(A,D),( B,C),(B,D) ,(G,C),(B,G)}，则对应的图形为___。
选项：
A:
B:
C:
D:
答案: 【】

3、问题:设某有向图中有n个顶点，则该有向图对应的邻接表中有___个表头结点。
选项：
A:n-1
B:n
C:n+1
D:n+2
答案: 【n】

4、问题:在一个无向图中所有顶点的度数之和等于所有边数的___倍。
选项：
A:1
B:2
C:3
D:1/2
答案: 【2】

5、问题:一个无向连通图的生成树是该连通图的_____。
选项：
A:极大连通子图
B:连通子图
C:极小连通子图
D:强连通子图
答案: 【极小连通子图】

6、问题:设某无向图中有n个顶点，则该无向图邻接矩阵的大小是___。
选项：
A:
B:
C:
D:n(n+1)/2
答案: 【】

7、问题:设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi关联的所有边算法的时间复杂度为___。
选项：
A:O()
B:O(n*e）
C:O(n+e）
D:O(n）
答案: 【O(n）】

8、问题:设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为___。
选项：
A:O()
B:O(n*e）
C:O(n+e）
D:O(n）
答案: 【O(n+e）】

9、问题:设无向图G=(V,E)和G’=(V’,E’)，如果G’是G的生成树，则下列说法中错误的是_____。
选项：
A:G’是G的子图
B:G’是G的一个无环子图
C:G’是G的极小连通子图且V=V’
D:G’是G的连通分量
答案: 【G’是G的连通分量】

10、问题:设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。
选项：
A:5
B:6
C:7
D:8
答案: 【6】

11、问题: n个顶点的有向图为强连通图时，至少含有__。
选项：
A:n-1条弧
B:n条弧
C:n(n-1)/2条弧
D:n(n-1)条弧
答案: 【n条弧】

12、问题:如果从无向图的一个顶点出发，进行一次深度优先搜索能访问所有顶点，则该无向图是一个__。
选项：
A:连通图
B:强连通图
C:完全图
D:DAG图
答案: 【连通图】

13、问题:如图所示的有向图，共有__个强连通分量。
选项：
A:1
B:2
C:3
D:4
答案: 【2】

14、问题:在下图中，从顶点A出发进行深度优先遍历可得到的序列是___。
选项：
A:ADCBG
B:ACDBG
C:ADGBC
D:ABDCG
答案: 【ABDCG】

15、问题:对图进行深度优先搜索遍历，需要借助的数据结构为__。
选项：
A:栈
B:队列
C:线索二叉树
D:广义表
答案: 【栈】

16、问题:对图进行广度优先搜索遍历，需要借助的数据结构为__。
选项：
A:栈
B:队列
C:线索二叉树
D:广义表
答案: 【队列】

17、问题:最小生成树是指__。
选项：
A:连通网的所有生成树中权值之和最小的生成树
B:由连通网得到的边数最少的生成树
C:由连通网得到的顶点数相对较少的生成树
D:连通网的极小连通子图
答案: 【连通网的所有生成树中权值之和最小的生成树】

18、问题:在下图中，从顶点A出发进行广度优先遍历可得到的序列是___。
选项：
A:ADCBG
B:ACDGB
C:ADGBC
D:AGBDC
答案: 【ADCBG】

19、问题:对如图所示的无向连通网，从顶点A出发，使用Prim算法得到的最小生成树是__。
选项：
A:
B:
C:
D:
答案: 【】

20、问题:可借助于___判别有向图中是否存在回路。
选项：
A:迪杰斯特拉算法
B:FLOYD算法
C:拓扑排序算法
D:PRIM算法
答案: 【拓扑排序算法】

21、问题:如图所示的DAG图，其拓扑排序序列为___。
选项：
A:ADBGC
B:ACDGB
C:ADGBC
D:AGBDC
答案: 【ADBGC】

22、问题:下列关于工程计划的AOE网的叙述中，不正确的是___。
选项：
A:关键活动不按期完成，会影响整个工程的完成时间
B:任何一个关键活动的提前完成，整个工程的完成时间都会提前
C:所有关键活动都提前完成，会提前整个工程的完成时间
D:某个关键活动提前完成，可能会提前整个工程的完成时间
答案: 【任何一个关键活动的提前完成，整个工程的完成时间都会提前】

23、问题:使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为__。
选项：
A:O()
B:O(n log n)
C:
D: