图习题

1. 问答题

1.1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。[答案] 1.2 试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。[答案] 1.3 下边的有向图是强连通的吗？请列出所有的简单路径。[答案]

1.4 在下图的有向图中：

(1) 该图是强连通的吗? 若不是，则给出其强连通分量。 (2) 请给出所有的简单路径及有向环。 (3) 请给出每个顶点的度，入度和出度。

(4) 请给出其邻接表、邻接矩阵及逆邻接表。[答案] 1.5 给出下图的邻接矩阵。[答案]

1.6 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？[答案] 1.7 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。[答案]

1.8 对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？[答案] 1.9 对于如下图所示的有向图，试写出：

(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；[答案]

1.10 用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e)？或者是O(max(n,e))？[答案]

1.11 下图是一个连通图，请画出(1) 以顶点①为根的深度优先生成树；(2) 如果有关节点，请找出所有的关节点。(3)如果想把该连通图变成重连通图，至少在图中加几条边？如何加？[答案]

1.12 什么样的图其最小生成树是唯一的?用PRIM 和Kruskal求最小生成树的时间各为多少?它们分别适合于哪类图? [答案]

1.13 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。 [答案] ┌ ┐ ┌ ┐ │ 0 1 1 0 0 │ │ 0 1 1 1 │ │ 0 0 0 1 0 │ │ 1 0 1 1 │ │ 0 0 0 1 0 │ │ 1 1 0 1 │ │ 1 0 0 0 1 │ │ 1 1 1 0 │ │ 0 1 0 1 0 │ └ ┘ └ ┘ (a) (b)

7.14 假设一棵完全二叉树包括A,B,C...等七个结点，写出其邻接表和邻接矩阵。[答案] 7.15 画出以顶点v1为初始源点遍历图(下图)所示的有向图所得到的DFS 和BFS生成森林。[答案]

7.16 对下图所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充红点集的每次循环状态。[答案]

2. 填空题

2.1 具有10个顶点的无向图，边的总数最多为【 】。 2.2 在有n个顶点的有向图中，每个顶点的度最大可达【 】。 2.3 克鲁斯卡尔算法的时间复杂度为 【 】,它对稀疏图较为适合。

2.4 若一个连通图中每个边上的权值均不同，则得到的最小生成树是 【 】的。

2.5 深度优先搜索遍历类似于树的 前序 遍历，它所用到的数据结构是【 】；广度优先搜索遍历类似于树的【 】遍历，它所用到的数据结构是【 】。

2.6 一个图的【 】 表示法是唯一的，而 【 】表示法是不唯一的。 2.7 对无向图，若它有n个顶点e条边，则其邻接表中需要【 】个结点。其中，【 】个结点构成邻接表，【 】个结点构成顶点表。

3. 算法题

3.1 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为 void Graph::DFS ( const int v, int visited [ ], TreeNode * t ) 其中，指针t指向生成森林上具有图顶点v信息的根结点。（提示：在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前，建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。）[答案]

3.2 试对右图所示的AOE网络，解答下列问题。 (1) 这个工程最早可能在什么时间结束。

(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。 (3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。

(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。[答案]

4. 判断题

4.1 在n个结点的无向图中，若边数>n-1，则该图必是连通图。【 】 4.2 任何AOV网拓扑排序的结果都是唯一的。【 】 4.3 有回路的图不能进行拓扑排序。【 】 4.4 一个图的广度优先搜索使是唯一的。【 】

4.5 图的深度优先搜索序列和广度优先搜索序列不是唯一的。【 】

5. 选择题

5.1 设无向图的顶点个数为n，则该无向图最多有【 】条边。 A、n-1 B、n(n+1)/2 C、n（n-1）/2 D、0 E、n2

5.2 在下列两种求图的最小生成树的算法中，【 】 算法适合于求边稀疏的网的最小生成树。 A、Prim B、Kruskal

5.3 下面的叙述中不正确的是【 】。

A、任何一个关键活动提前完成，将使整个工程提前完成 B、关键活动不按期完成就会影响整个工程的完成时间 C、所有关键活动都提前完成，则整个工程将提前完成 D、某些关键活动若提前完成，将使整个工程提前完成

5.4 采用邻接表存储的图，其深度优先遍历类似于二叉树的【 】。 A、中序遍历 B、先序遍历 C、后序遍历 D、按层次遍历

5.5 采用邻接表存储的图，其广度优先遍历类似于二叉树的【 】。 A、按层次遍历 B、中序遍历 C、后序遍历 D、先序遍历

5.6 具有n个顶点的有向图最多有【 】条边。 A、n B、n C、n（n+1） D、n（n-1）

5.7 一个n个顶点的连通无向图，其边的个数至少为【 】。 。

A、n-1 B、n C、n+1 D、nlog2n

5.8 下列说法中，正确的有【 】。 A、最小生成树也是哈夫曼树 B、最小生成树唯一

C、普里姆最小生成树算法时间复杂度为O（n）

D、克鲁斯卡尔最小生成树算法普里姆算法更适合与边稠密的网。

5.10 判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用【 】。 A、求关键路径的方法

B、求最短路径的Dijkstra方法

2

2

C、深度优先遍历算法 D、广度优先遍历算法

5.11 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为【 】。

A、s B、s-1 C、s+1 D、n

5.12 在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为【 】。 A、k B、k+1 C、k+2 D、2

5.13 一个有n个顶点的无向连通图，它所包含的连通分量个数为【 】。 A、0 B、1 C、n D、n+1

5.14 对于一个有向图，若一个顶点的入度为k1、出度k2，则对应邻接表中该顶点单链表中的结点数为【 】。

A、k1 B、k2 C、k1-k2 D、k1+k2

5.15 对于一个有向图，若一个顶点的入度为k1、出度k2，则对应逆邻接表中该顶点单链表中的结点数为【 】。

A、k1 B、k2 C、k1-k2 D、k1+k2

5.16 为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用【 】。 A、顺序存储 B、链式存储 C、索引存储 D、散列存储

k

本文来源：https://www.bwwdw.com/article/5c3x.html