《数据结构》第06章在线测试

《数据结构》第06章在线测试
剩余时间：
59:12

答题须知：1、本卷满分20分。
2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。
3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。
第一题、单项选择题（每题1分，5道题共5分）
1、一个有n个顶点的无向图若是连通图，则至少有＿＿＿A＿＿＿＿＿条边。
A、n-1
B、n
C、n+1
D、(n+1)/2
2、4个顶点的无向完全图有＿＿＿＿A＿＿＿＿条边。
A、6
B、12
C、16
D、20
3、无向图的邻接矩阵是一个＿＿＿＿A＿＿＿＿。
A、对称矩阵
B、零矩阵
C、对角矩阵
D、上三角矩阵
4、一个无向连通图的生成树是含有该连通图所有顶点的＿＿＿＿C＿＿＿＿。
A、极大连通子图
B、极大子图
C、极小连通子图
D、极小子图
5、对＿＿＿＿＿D＿＿＿，用Prim算法求最小生成树较为合适。
A、非连通图
B、连通图
C、稀疏图
D、稠密图
第二题、多项选择题（每题2分，5道题共10分）
1、下列说法中正确的是＿＿＿＿AB＿＿＿＿。
A、无向图中的极大连通子图称为连通分量。
B、图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。
C、图的深度优先搜索中一般要采用队列来暂存刚访问过的顶点。
D、有向图的遍历不能采用广度优先搜索方法。
2、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿ABCD＿＿＿＿＿。
A、计算邻接矩阵中第i行的元素之和
B、计算邻接矩阵中第i列的元素之和
C、计算邻接矩阵中第i行的非零元个数
D、计算邻接矩阵中第i列的非零元个数
3、对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿＿＿＿CD＿＿。
A、一定相同
B、一定不同
C、不一定相同
D、可能相同
4、下列关于最短路径的说法中，正确的有＿＿＿ACD＿＿＿＿＿。
A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。
B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。
C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n^3)。
D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。
5、有向图中顶点之间关系的特征是：每个顶点可以有＿＿＿＿CD＿＿＿＿。
A、一个前驱
B、一个后继
C、多个前驱
D、多个后继
第三题、判断题（每题1分，5道题共5分）
1、若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。
正确 T
错误
2、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。
正确 F
错误
3、对稀疏图，用Prim算法求最小生成树较为合适
正确 F
错误
4、利用拓扑排序，可检测一个有向图中是否存在环
正确 T
错误
5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。
正确 T
错误