《数据结构》第五章测试题 - 在线考试测评模板

Q1:姓名

选项1

Q2:学号

选项1

Q3:班级

选项1

Q4:1、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。

A、1/2

B、1

C、2

D、4

Q5:2、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A、完全图

B、连通图

C、有回路

D、一棵树

Q6:3、关键路径是事件结点网络中（）。

A、从源点到汇点的最长路径

B、从源点到汇点的最短路径

C、最长的回路

D、最短的回路

Q7:4、下面（）可以判断出一个有向图中是否有环（回路）。

A、广度优先遍历

B、拓扑排序

C、求最短路径

D、求关键路径

Q8:5、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。

A、第i行非无穷的元素之和

B、第i列非无穷的元素个数之和

C、第i行非无穷且非0的元素个数

D、第i行与第i列非无穷且非0的元素之和

Q9:6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。

A、中序遍历

B、先序遍历

C、后序遍历

D、按层次遍历

Q10:7、无向图的邻接矩阵是一个（）。

A、对称矩阵

B、零矩阵

C、上三角矩阵

D、对角矩阵

Q11:8、一个图的广度优先搜索树是惟一的（）。

A、对

B、错

Q12:9、邻接表是图的一种（）。

A、顺序存储结构

B、链式存储结构

C、索引存储结构

D、散列存储结构

Q13:10、下面有向图所示的拓扑排序的结果序列是（）。

A、125634

B、516234

C、123456

D、521643

Q14:11、对某个无向图的邻接矩阵来说，下列叙述正确的是（）。

A、第i行上的非零元素个数和第i列上的非零元素个数一定相等

B、矩阵中的非零元素个数等于图中的边数

C、第i行与第i列上的非零元素的总数等于顶点Vi的度数

D、矩阵中非全零行的行数等于图中的顶点数

答案：A

Q15:12、在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。

A、入边

B、出边

C、入边和出边

D、不是出边也不是入边

Q16:13、设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1V2,E1E2则称（）。

A、G1是G2的子图

B、G2是G1的子图

C、G1是G2的连通分量

D、G2是G1的连通分量

Q17:14、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。

A、将邻接矩阵的第i行删除

B、将邻接矩阵的第i行元素全部置为0

C、将邻接矩阵的第i列删除

D、将邻接矩阵的第i列元素全部置为0

Q18:15、任一个有向图的拓扑序列（）。

A、不存在

B、有一个

C、一定有多个

D、有一个或多个

Q19:16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A、1/2

B、1

C、2

D、4

Q20:17、下列关于图遍历的说法不正确的是（）。

A、连通图的深度优先搜索是一个递归过程

B、图的广度优先搜索中邻接点的寻找具有“先进先出”的特征

C、非连通图不能用深度优先搜索法

D、图的遍历要求每一顶点仅被访问一次

Q21:18、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中：（）。

A、第i行非的元素之和

B、第i列非的元素之和

C、第i行非且非0的元素个数

D、第i列非且非0的元素个数

Q22:19、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。

A、先序遍历

B、中序遍历

C、后序遍历

D、按层次遍历

Q23:20、一个具有n个顶点的有向图最多有（）条边。

A、n×(n-1)/2

B、n×(n-1)

C、n×(n+1)/2

D、n^2

Q24:21、已知一个有向图的邻接表存储结构如图所示，根据深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。[图片]

B、v1,v2,v3,v4,v5

C、v1,v3,v4,v5,v2

D、v1,v4,v3,v5,v2

Q25:22、设图的邻接矩阵为，则该图为（）。[图片]

A、有向图

B、无向图

C、强连通图

D、完全图

Q26:23、任何一个无向连通图的最小生成树（）种。

A、只有一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

Q27:24、无向图中一个顶点的度是指图中（）。

A、通过该顶点的简单路径数

B、与该顶点相邻接的顶点数

C、与该顶点连通的顶点数

D、通过该顶点的回路数

Q28:25、一个有n个顶点的无向图最多有（　　）条边。

A、n

B、n(n-1)　　　

C、n(n-1)/2

D、2n

Q29:26、在一个具有n个顶点的有向完全图中包含有（）条边：

A、n(n-1)/2

B、n(n-1)

C、n(n+1)/2

D、n^2

Q30:27、无向图的邻接矩阵是一个（）

A、上三角矩阵

B、下三角矩阵

C、对称矩阵

D、无规律

Q31:28、在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（）。

A、s　

B、s-1

C、s+1

D、n

Q32:29、存储有向图的邻接矩阵一定是对称的（）。

A、对

B、错

Q33:30、一个有向图的邻接表和逆邻接表中的结点个数一定相等（）。

A、对

B、错

Q34:31、用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（）

A、对

B、错

Q35:31、含有10个顶点的无向连通图其生成树含有9条边。（）

A、对

B、错

Q36:32、AOV网上如果能够进行拓扑排序，则说明该活动安排是合理的。（）

A、对

B、错