GESP 7级客观题｜图的概念与存储｜课后作业

考试频率：高频。本卷共 6 题。

1. 简单有向图有 n 个顶点和 e 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 u 的度的时间复杂度一样。( )

   {{ select(1) }}

• 对
• 错

2. 下面关于图的说法正确的是

   {{ select(2) }}

• 在无向图中，环是指至少包含三个不同顶点，并且第一个顶点和最后一个顶点是相同的路径。
• 在有向图中，环是指一个顶点经过至少另一个顶点到自身的路径。
• 在有向图中，如果任意两个顶点之间都存在一条边，则这个图一定是强连通图。
• 在有向图中，所有顶点的入度和出度的总和就是图的边数的两倍。

3. 邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。

   {{ select(3) }}

• 正确
• 错误

4. 下列关于树和图的说法，错误的是（）。

   {{ select(4) }}

• 树是一种有向无环图，但有向无环图不都是一棵树。
• 如果把树看做有向图，每个节点指向其子节点，则该图是强连通图。
• $N$个顶点且连通的无向图，其最小生成树一定包含$N-1$条边。
• $N+1$个顶点、$N$条边的有向图，一定不是强连通的。

5. G 是一个非连通无向图，共有 28 条边，则该图至少有( )个顶点。

   {{ select(5) }}

• 6
• 7
• 8
• 9

6. 用下面的邻接表结构保存一个有向图 G ， InfoType 和 VertexType 是定义好的类。设 G 有 n 个顶点、e 条弧，则求图 G 中某个顶点 u （其顶点序号为 k ）的度的算法复杂度是( )。

typedef struct ArcNode{
	int            adjvex;    // 该弧所指向的顶点的位置 
	struct ArcNode *nextarc;  // 指向下一条弧的指针 
	InfoType       *info;     // 该弧相关信息的指针 
}ArcNode;
typedef struct VNode{
	VertexType  data;    // 顶点信息 
	ArcNode *firstarc;  // 指向第一条依附该顶点的弧 
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
	AdjList vertices;
	int vexnum, arcnum;
	int kind;    // 图的种类标志 
};

{{ select(6) }}

• $O(n)$
• $O(e)$
• $O(n+e)$
• $O(n+2*e)$