《数据结构》第06章在线测试
《数据结构》第06章在线测试剩余时间：58:08
答题须知：1、本卷满分20分。
2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。
3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。
第一题、单项选择题（每题1分，5道题共5分）
1、一个有n个顶点的无向图若是连通图，则至少有＿＿＿＿A＿＿＿＿条边。
A、n-1B、n
C、n+1D、(n+1)/2
2、图的广度优先遍历算法类似于二叉树的＿＿＿D＿＿＿＿＿。
A、先序遍历B、中序遍历
C、后序遍历D、层序遍历
3、无向图的邻接矩阵是一个＿＿＿＿A＿＿＿＿。
A、对称矩阵B、零矩阵
C、对角矩阵D、上三角矩阵
4、一个无向连通图的生成树是含有该连通图所有顶点的＿＿＿C＿＿＿＿＿。
A、极大连通子图B、极大子图
C、极小连通子图D、极小子图
5、如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点，则该图一定是＿＿＿B＿＿＿＿＿。
A、完全图B、连通图
C、有回路D、一棵树
第二题、多项选择题（每题2分，5道题共10分）
1、如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是＿＿＿ABD＿＿＿＿＿。
A、G肯定不是完全图
B、G肯定不是连通图
C、G中一定有回路
D、G有两个连通分量
2、对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿CD＿＿＿＿＿。
A、一定相同
B、一定不同
C、不一定相同
D、可能相同
3、下列关于最短路径的说法中，正确的有＿＿＿ACD＿＿＿＿＿。
A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。
B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。
C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n^3)。
D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。
4、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿ABCD＿＿＿＿。
A、计算邻接矩阵中第i行的元素之和
B、计算邻接矩阵中第i列的元素之和
C、计算邻接矩阵中第i行的非零元个数
D、计算邻接矩阵中第i列的非零元个数
5、有向图中顶点之间关系的特征是：每个顶点可以有＿＿＿＿CD＿＿＿＿。
A、一个前驱
B、一个后继
C、多个前驱
D、多个后继
第三题、判断题（每题1分，5道题共5分）
1、连通网的最小生成树是唯一的。F
正确错误
2、若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。T
正确错误
3、图的深度优先遍历算法类似于二叉树的先序遍历T
正确错误
4、在对有向无环图执行拓扑排序算法之后，入度数组中所有元素的值均为0。T
正确错误
5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。T
正确错误
