题34

题34

题目

【2011 统考真题】下列关于图的叙述中, 正确的是 ( ).
I. 回路是简单路径
II. 存储稀疏图, 用邻接矩阵比邻接表更省空间
III. 若有向图中存在拓扑序列, 则该图不存在回路
A. 仅 II
B. 仅 I、II
C. 仅 III
D. 仅 I、III

分析

简单路径是指路径上的结点不重复

解

C
第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, I 错误。
稀疏图是边比较少的情况, 邻接矩阵存储的空间复杂度为 ,必将浪费大量的空间,而邻接表存储的空间复杂度为 ,所以应选用邻接表, II 错误。
存在回路的有向图不存在拓扑序列, 若拓扑排序输出结束后所余下的顶点都有前驱, 则说明只得到了部分顶点的拓扑有序序列, 图中存在回路, III 正确。