云南开放大学数据结构网上作业6

一、单项选择题(共23题,共100分)
第1 题（5分）：
在一个无向图中，所有顶点的度之和等于边数的（         ）倍。
A.1/2    B.1      C.2     D.4
正确答案: C
答案解析：无向图中，一条边计入两个顶点的度数。
第2 题（5分）：
有n个顶点的无向图，最多有（     ）条边。
A.n   B.n (n-1)   C. n（n-1）/2   D.2n
正确答案: C
答案解析：完全无向图的边数最多。有n个顶点的完全无向图有n（n-1）/2条边。
第3 题（5分）：
在一个具有n个顶点的无向图中，要连通全部顶点至少需要（     ）条边。
A.n   B. n+1   C. n-1     D.n/2
正确答案: C
答案解析：成为树图是边最少。
第4 题（5分）：
在无向图中，定义顶点i到顶点j的路径，是从顶点i到顶点j的一个（     ）。
A.顶点序列   B. 顶点个数   C. 权值之和     D. 边的条数
正确答案: A
答案解析：路径是由顶点序列构成的。
第5 题（5分）：
在n个顶点的连通图中，任意一条简单的路径，其长度不可能超过（     ）。
A.1   B. n/2   C. n-1     D. n
正确答案: C
答案解析：若路径长度超过n-1,则其中必存在重复的顶点。
第6 题（5分）：
以说法错误的是（          ）。
A. 图和树的区别在于图的边数大于等于顶点数
B. 无向图的连通分量是指无向图中极大连通子图
C. 一个强连通图只有一个强连通分量
D. 一个图中所有顶点的度之和等于边数的两倍
正确答案: A
答案解析：一个有向图可以有很多顶点没有边。
第7 题（5分）：
对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是（     ）。
A. n      B.(n-1)*(n-1)     C. n-1      D. n*n
正确答案: D
答案解析：含有n个顶点的图采用邻接矩阵存储，矩阵大小为n*n。
第8 题（5分）：
对于一个具有n个顶点e条边的无向图存储在邻接矩阵中，则非零元素的个数是（     ）。
A. n      B.2e        C. e      D. n+e
正确答案: B
答案解析：无向图的邻接矩阵中，每个非零元素记2次，即非零元素个数为2e。
第9 题（4分）：
对于一个具有n个顶点e条边的有向图存储在邻接矩阵中，则非零元素的个数是（     ）。
A. n      B.2e        C. e      D. n+e
正确答案: C
答案解析：有向图的邻接矩阵中，每个非零元素记1次，即非零元素个数为e。
第10 题（4分）：
如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有的顶点。则该图一定是一个（          ）。
A. 完全图    B.连通图        C. 有回路    D. 一棵树
正确答案: B
答案解析：只有连通图才能一次深度优先遍历即可访问所有顶点。
第11 题（4分）：
一个无向连通图的生出树是含有该连通图的全部顶点的（          ）。
A. 极小连通子图    B.极小连通图        C. 极大连通子图    D. 极大子图
正确答案: A
答案解析：生成树是含有全部顶点的极小连通子图。
第12 题（4分）：
最小生成树是指（          ）。
A. 由连通图所得到的边数最少的生成树
B. 由连通图所得到的顶点数相对较少的生成树
C. 由连通图所有生成树中权值之和为最小的生成树
D. 连通图的极小连通子图
正确答案: A
第13 题（4分）：
求最短路径的Dijkstra算法的时间复杂度为（    ）。
A. O(n)    B. O(n+e)        C. O(n2)    D. O(ne)
正确答案: C
第14 题（4分）：
求最短路径的Floyd算法的时间复杂度为（    ）。
A. O(n)    B. O(n+e)        C. O(n2)    D. O(n3)
正确答案: D
第15 题（4分）：
在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（     ）。
A. s　　　B.s-1　　　C. s+1　　　D. n
正确答案: A
第16 题（4分）：
一个有向图有n个顶点，则每个顶点的度可能的最大值是（     ）。
A. n-1　　　B. 2(n-1)　　　　C. n　　D. 2n
正确答案: B
第17 题（4分）：
具有6个顶点的无向图至少应有（　　）条边才能确保是一个连通图。
A.5　　　　B.6　　　　C.7　　　　D.8
正确答案: A
第18 题（4分）：
一个有n个顶点的无向图最多有（　　）条边。
A.n　　　B. n(n-1)　　C. n(n-1)/2　　　　D. 2n
正确答案: C
第19 题（4分）：
任何一个无向连通图的最小生成树（      ）。
A.至少有一棵    B.只有一棵     C.一定有多棵     D.可能不存在
正确答案: A
第20 题（4分）：
已知一个图的边数为m，则该图的所有顶点的度数之和为（     ）。
A．2m         B．m          C．2m+1        D．m/2
正确答案: A
答案解析：一条边连接两个顶点，可以记为两个顶点的度。
第21 题（4分）：
已知一个图的所有顶点的度数之和为m，则m一定不可能是（    ）。
A．4         B．8            C．12           D．9
正确答案: D
答案解析：在一个无向图中，所有顶点的度之和等于边数的2倍。因此，度之和肯定是偶数。
第22 题（4分）：
以下说法不正确的是（    ）。
A．连通图G一定存在生成树
B．连通图G的生成树中一定包含G的所有顶点
C．连通图G的生成树中不一定包含G的所有边
D．连通图G的生成树可以是不连通的
正确答案: D
第23 题（4分）：
以下说法正确的是（     ）。
A．连通图G的生成树中可以包含回路
B．连通图G的生成树可以是不连通的
C．连通图G的生成树一定是唯一的
D．连通图G的生成树一定是连通而不包含回路的
正确答案: D