第七章——知识点习题总结（14页）

知识点一 图的定义和术语

一、选择题

1．在一个图中，所有顶点的度数之和等于图的边数的( )倍。

A．1／2 B．1 C．2 D．4

答案：C

2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。

A．1／2 B．1 C．2 D．4

答案：B

3. 有8个结点的无向图最多有( )条边。

A．14 B．28 C．56 D．112

答案：B

4．有8个结点的无向连通图最少有( )条边。

A．5 B．6 C．7 D．8

答案：C

5．有8个结点的有向完全图有( )条边。

A．14 B．28 C．56 D．112

答案：C

6. 强连通分量是（ ）的极大强连通子图。

A. 树 B.图 C.无向图 D.有向图

答案：D

7. 在一个图中，所有顶点的度数之和等于图的边数的( )倍。

A. 1/2 B.1 C.2 D.4

答案：C

8. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。

A. 1/2 B.1 C.2 D.4

答案：B

9. 有8个结点的无向图最多有( )条边。

A. 14 B.28 C.56 D.112

答案：B

10. 无向图顶点v的度是关联于该顶点（ ）的数目。

A. 顶点 B.边 C.序号 D.下标

答案：B

11. 有8个结点的无向连通图最少有( )条边。

A. 5 B.6 C.7 D.8

答案：C

12. 有8个结点的有向完全图有( )条边。

A. 14 B.28 C.56 D.112

答案：C

13. 一个具有n个顶点e条边的图中，所有顶点的度数之和等于 ( )。

A. n B.e C.2n D.2e

答案：C

14. 若图G中（ ）都没有方向，则称G为无向图。

A. 每条边 B.部分边 C.一条边 D.每个顶点

答案：A

15. 对于一个具有n个顶点的无向图的边数最多有（ ）。

A. n B.n(n-1) C.n(n-1)/2 D.2n

答案：C

16. 对于一个具有n个顶点的有向图的边数最多有（ ）。

A. n B.n(n-1) C.n(n-1)/2 D.2n

答案：B

17. 具有4个顶点的无向完全图有（ ）条边。

A. 6 B.12 C.16 D.20

答案：A

18. 在下列表示方法中，（ ）是有向图边的表示方法。

A. （1，2） B.（1，2> C.<1，2） D.<1，2>

答案：D

19. 在下列表示方法中，（ ）是有无向图边的表示方法。

A. （1，2） B.（1，2> C.<1，2） D.<1，2>

答案：A

二、填空题

1.有n条边的无向图邻接矩阵中，1的个数是 _____。

答案：2n

2.若图G中每条边都 方向，则G为无向图。

答案：没有

3.n个顶点的完全无向图有 条边。

答案： n（n-1）/2

4.若图G中每条边都 _____方向，则G为有向图。

答案：有

5.在具有n个顶点的图的生成树中，含有 条边。

答案：n-1

6.有向图的边也称为 ____ 。

答案：弧

三、简答题

1 .画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。

答案：

2个顶点的无向完全图1个顶点的无向完全图

2个顶点的

无向完全图

1个顶点的

无向完全图

5个顶点的无向完全图4个顶点的无向完全图

5个顶点的

无向完全图

4个顶点的

无向完全图

3个顶点的

无向完全图

【证明】

在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。

知识点二 图的存储结构

一、选择题

1. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）．

A. n B. (n-1) 2 C. n-1 D. n2

答案：D

对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大

为( );

A. n B. (n-1) 2 C. n-1 D. n2

答案：A

3. 有n个顶点的无向图的邻接矩阵是用（ ）数组存储。

A. 一维 B.n行n列 C.任意行n列 D.n行任意列

答案：B

n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个（ ）。

A. 一般矩阵 B.对称矩阵 C.对角矩阵 D.稀疏矩阵

答案：B

5. 有n个顶点的有向图的邻接矩阵是用（ ）数组存储。

A. 一维 B.n行n列 C.任意行n列 D.n行任意列

答案：B

6. 有n个条边的无向图的邻接矩阵（表）存储法中，链表中结点的个数是（ ）个。

A. n/2 B.n C.2n D.n*n

答案：C

7. 有n个条边的有向图的邻接矩阵（表）存储法中，链表中结点的个数是（ ）个。

A. n/2 B.n C.2n D.n*n

答案：B

8. 下面关于图的存储结构的叙述中正确的是（ ）。

A. 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关

B. 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关

C. 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关

D. 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关

答案：A

9. 在图的表示法中，表示形式唯一的是（ ）。

A. 邻接矩阵表示法 B.邻接表表示法

C.逆邻接表表示法 D.邻接表和逆邻接表表示法

答案：A

二、填空题

1. 图有 等存储结构。

答案：邻接矩阵,邻接表

2．有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 。

答案：出度

n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为_________。

答案：

n个顶点e条边的图若采用邻接表存储，则空间复杂度为__________。

答案：O(n+e)

6. 设有一稀疏图C，则C采用_ 存储较省空间。

答案：邻接矩阵

7. 设有一稠密图G，则G采用 存储较省空间。

答案：邻接表

图的逆邻接表存储结构只适用于 图。

答案：有向

已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是

答案：把第i行全部置零

10. 图有： _ _ 和邻接表等存储结构。

答案：邻接矩阵

11. n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： 。

答案：O（n2）

12. n个顶点e条边的图若采用邻接表阵存储，则空间复杂度为： 。

答案： O（n+e）

13 .图的邻接矩阵表示法是表示 ______之间相邻关系的矩阵。

答案：顶点

14. 对n个顶点，e条弧的有向图，其邻接表表示中，需要 个结点。

答案：n+e

15. 对n个顶点，e条边的无向图，其邻接表表示中，需要 个结点。

答案：n+2e

16. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 ______。

答案：出度

17. 设有一稀疏图G，则G采用 _____存储比较节省空间。

答案：邻接表

18. 图的逆邻接表存储结构只适用于 ______图。

答案：有向

19. 设有一稠密图G，则G采用 _____存储比较节省空间。

答案：邻接矩阵

20. 一个图的 表示法是唯一的。

答案：邻接矩阵

21. .有向图的邻接表表示适于求顶点的 。

答案：出度

22. .有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的 。

答案：入度

三、简答题

1.下列函数是在有向图的邻接表中删除一条边的算法，请补充算法。

Void deledge (ALGraph * G, iht i, int j )

{EdgeNode * p, * q;

p = G -> adjlist Iii . firstedge;

if(_______(1)_______) {G->adjlist[i].firstedge=p->next;free(p);}

else { while (p ->next ->adjvex! = j && p ->next)

__________________________(2)________;

if(_________(3)____){q=p ->next;_______(4)_______;free(q);}

}

)

答案：（1）p->adjvex==j

（2）p=p->next

（3）p->next!=null

（4）p->next=q->next

用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？

答案：用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。

知识点三 图的遍历

一、选择题

1．用邻接表表示图进行广度优先遍历时，通常采用( )来实现算法的。

A. 栈 B．队列 C．树 D．图

答案：B

2．用邻接表表示图进行深度优先遍历时，通常采用( )来实现算法的。

A．栈 B。队列 C．树 D．图

答案：A

3．已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是( )

0 1 1 1 1 0 1

0 1 1 1 1 0 1

1 0 0 1 0 0 1

1 0 0 0 1 0 0

1 1 0 0 1 1 0

1 0 1 1 0 1 0

0 0 0 1 1 0 1

1 1 0 0 0 1 0

A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2

C．0 4 2 3 1 6 5 D．0 3 6 1 5 4 2

答案：C

4．已知图的邻接矩阵同上题8，根据算法，则从顶点0出发按深度优先遍历的结点序列是( )。

A．0 2 4 3 1 5 6 B．0 1 3 5 6 4 2 C．0 4 2 3 1 6 5 D．0 1 3 4 2 5 6

答案：D

5．已知图的邻接矩阵同上题8，根据算法思想，则从顶点0出发按广度优先遍历的结点序列是（ ）

A. 0 2 4 3 1 6 5 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6

答案：B

6．已知图的邻接矩阵同上题8，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ 　）

A. 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6

答案：C

7．深度优先遍历类似于二叉树的( )。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历

答案：A

8．广度优先遍历类似于二叉树的( )。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历

答案：D

9. 已知一个有向图如右图所示，则从顶点a出发，进行深度优先遍历，不可能得到序列为（ ）。

A. a，d，b，e，f，c B.a，d，c，e，f，b

C.a，d，c，b，f，e D.a，d，e，f，c，b

答案：A

10.深度优先遍历类似于二叉树的( )。

A. 先序遍历 B.中序遍历 C.后序遍历 D.层次遍历

答案：A

11.广度优先遍历类似于二叉树的( )。

A. 先序遍历 B.中序遍历 C.后序遍历 D.层次遍历

答案：D

D12.如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（ ）。

A. a，b，e，c，d，f B.a，c，f，e，b，d

C.a，e，b，c，f，d D.a，e，d，f，c，b

答案：D

13.按广度优先进行遍历，则可能得到的一种顶点序列为（ ）。

A． a，b，e，c，d，f B． a，b，e，c，f，d

C.a，e，b，c，f，d D.a，e，d，f，c，b

答案：B

14.深度优先遍历类似于二叉树的 ( )。

A. 前序遍历 B.中序遍历 C.后序遍历 D.层次遍历

答案：A

15.广度优先遍历类似于二叉树的 ( )。

A. 前序遍历 B.中序遍历 C.后序遍历 D.层次遍历

答案：D

B 41:用邻接表表示图进行广度优先遍历时，通常采用( )来实现算法的。

A. 栈 B.队列 C.树 D.图

答案：B

16.用邻接表表示图进行深度优先遍历时，通常采用( )来实现算法的。

A. 栈 B.队列 C.树 D.图

答案：A

二、填空题

1. 图的深度优先遍历序列__ ___唯一的。

答案：不是

2. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 。

答案：

3. n个顶点e条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为____。

答案：O(n+e)

4. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 。

答案：

5. n个顶点e条边的图采用邻接表存储，广度优先遍历算法的时间复杂度为 。

答案：O(n+e)

6. n个顶点e条边的图若采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 。

答案：O（n2）

7. 图的遍历有：深度优先搜和 __等方法。

答案：广度优先搜

8. .n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 。

答案：O（n2）

9. .图的深度优先搜索类似于树的 遍历。

答案：前序

10. 图的广度优先搜索类似于树的 遍历。

答案：层次

11. 图的深度优先遍历序列 ________唯一的。

答案：不是

三、简答题

1．完成下列深度优先遍历算法。

void DFS(ALGraph w G, int i)

{ EdgeNode *p;

print f ("DFS vextex % c In", G - > adj list [ ii. vextex);

visited [ i] = TRUE;

________(1)________;

while (p)

{if(_______(2)________) DFS(G,p -> adjvex);

_________(3)____;

}

答案：（1）p=G->adjlist[i].firstdege

（2）!visited[p->adjvex]

（3）p=p->next

知识点四 连通图的最小生成树

一、选择题

1．任何一个无向连通图的最小生成树( )。

A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在

答案：A

2. 任何一个连通图的生成树 ( )。

A. 可能不存在 B.只有一棵 C.有一棵或多棵 D.一定有多棵

答案：C

3. 生成树的构造方法只有（ ）。

A. 深度优先 B.深度优先和广度优先 C.无前驱的顶点优 D.无后继的顶点优先

答案：B

4. 任何一个无向连通图的最小生成树( )。

A. 只有一棵 B.一棵或多棵 C.一定有多棵 D.可能不存在

答案：A

5. 最小生成树的构造可使用（ ）算法。

A. prim算法 B.卡尔算法 C.哈夫曼算法 D.迪杰斯特拉算法

答案：A

二、填空题

1. 图的BFS生成树的树高比DFS生成树的树高____。

答案：小或相等

2. 用Prim算法求具有n个顶点e条边的图的最小生成树的时间复杂度为____。

答案：O ()

3. 用Kruskal算法求具有n个顶点e条边的图的最小生成树的时间复杂度为_ ___。

答案：

4. 若要求一个稀疏图C的最小生成树，最好用____算法来求解。

答案：Kruskal算法

5. 若要求一个稠密图G的最小生成树，最好用____算法来求解。

答案：Prim算法

6. 一个图的生成树的顶点是图的 _ ____顶点。

答案：全部

知识点五 两点之间最短路径问题

一、填空题

1. 用迪杰斯特拉(Dijstra)算法求n个顶点e条边的图中的某一顶点到其余各顶点间的最短路径的时间复杂度为_ ___。

答案：

2. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度____的次序来得到最短路径的。

答案：递增

二、简答题

1．求给定如下所示的有向图中顶点1到其余各顶点的最短路径及路径长度。

9

9

2

7

5

3

8

1

10

6

4

解答：最短路径及路径长度为：

13：8

132：11

14：12

135：13

136：14

1357：16

1368：16

136810：18

13689：22。

知识点六 拓扑排序

一、填空题

1. 拓扑排序算法是通过重复选择具有__个前趋顶点的过程来完成的。

答案：零

2. 拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在 __。

答案：环

3. 对n个顶点e条边的图进行拓扑排序，算法的时间复杂度为____。

答案：O(n+e )

二、简答题

1. 图G=(V，E)，V={0，1，2，3，4，5}，E={<0，1>，<0，2>，<1，4>，<2，5>，<5，4>，<4，3>，<5，3>}。写出图G中顶点的所有拓扑排序。

答案：拓扑排序为：0 1 2 5 4 3

0 2 1 5 4 3

0 2 5 1 4 3。

知识点七 关键路径

1. 试对右图所示的AOE网络，解答下列问题。

(1) 这个工程最早可能在什么时间结束。

(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。

(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。

(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速

可使整个工程提前完成。

答案：

按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。

1 ?

2 ?

3 ?

4 ?

5 ?

6 ?

Ve

0

19

15

29

38

43

Vl

0

19

15

37

38

43

<1, 2>

<1, 3>

<3, 2>

<2, 4>

<2, 5>

<3, 5>

<4, 6>

<5, 6>

e

0

0

15

19

19

15

29

38

l

17

0

15

27

19

27

37

38

l-e

17

0

0

8

0

12

8

0

此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>