第七章 图 练习题

7．对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )，利用Kruskal时间复杂度为( )。

(A)O(1og2n) (B)O(n2) (C)O(ne) (D)O(e log2 e) 8．具有n个顶点的完全有向图的边数为( )。

(A)n(n一1)／2 (D)n(n—1) (C)n2 (D) n2 -1

2．有向图G用邻接矩阵A{l?n，1?n}存储，其第i列的所有元素等于顶点i的______________。

3．对于下图，试给出

(1)每个顶点的入度和出度 (2)邻接矩阵， (3)逆邻接表； (4)强连通分量。

3．设汁一个算法，建立无向图(n个顶点，e条边)的邻接表。 8．对下图v4的度为( )。

(A)1 (B)2 (C)3 (D)4

7．有向图G用邻接矩阵A[1?m，1?m ]存储，其第i行的所有元素值之和等于顶点vi的__________________。

1．n个顶点的无向图的邻接表中结点总数最多有( )个。

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

2．设连通图G的顶点数为n，则G的生成树的边数为( ) (A)n (B)n一1 (C)2n (D) 2n-1

6．连通分量是无向图中的极小连通子图。( )

6．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。( )

7．一个无向连通图有5个顶点8条边，则其生成树将要去掉( )条边。 (A)3 (B)4 (C)5 (D)6

2．如果某有向图的所有顶点可以构成一个拓扑排序，则说明有向图存在回路。( ) 8．一个图可以没有边，但不能没有顶点。( ) 3．已知下图是一个有向图。

(1)画出该有向图的邻接矩阵。(5分)

(2)基于你给出的邻接矩阵，求从顶点6出发的深度优先遍历。(5分)

4．有向图的邻接矩阵的第i行的所有元素之和等于第i列的所有元素之和。（ ） 6．图的生成树的边数应小于顶点数。( )

3．一个无向连通图有6个顶点7条边，则其生成树有_____________条边。 8．设无向图G有100条边，则G至少有_____________个顶点。

4．已知下图是一个无向团。

(1)画出该无向图的邻接链表。(5分)

(2)基于你给出的邻接链表，求从顶点C出发的广度优先遍历。(5分)

3．一个n个顶点的连通无向图，其边的个数至少为( )。

(A) n-1 (B) n (C) n+1 (D)O n log n

4．如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图__________。 7．无向图用邻接矩阵存储，其所有元素之和表示无向图的__________。

3．已知下图是一个有向图。

(1)画出该有向图的邻接链表。(4分)

(2)基于你给出的邻接链表，求从顶点5／出发的广度优先温历。(4分)

4．用Prim算法(一条顶点一条顶点加入生成树)求下图的最小生成树。 (1)从顶点D开始，写出各顶点加人生成树的次序。(4分) (2)画出最终的最小生成树。(4分)

4．已知左下图是一个无向图。

(1)画出该无向图的邻接矩阵。(5分)

(2)基于你给出的邻接矩阵，求从顶点A出发的深度优先遍历。(4分) 5．用Kruskal算法(一条边一条边地加入生成树)求右下图的最小生成树。 (1)写出各条边加入生成树的次序(用权值表示)。(5分) (2)画出最终的最小生成树。(4分)

2．己知一带权有向图的邻接矩阵表示如下，试画出其逻辑图。

3．已知一有向图如下图所示，试画出从A点出发的深度优先生成树。

4．以(1，3，6，7，9，15，22)为权值，构造一棵Huffman树，并求出其WPL。

课后习题：

一、单项选择题

1、一个n个顶点的无向图最多有________条边。

（A）n （B）n(n-1) （C）n(n-1)/2 （D） 2n

2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_________倍。 （A）1/2 （B）1 （C）2 （D）4 3、关键路径是事件结点网络中 __________ 。 （A）从源点到汇点的最长路径 （B）最长的回路 （C）从源点到汇点的最短路径 （D）最短的回路 4、下面不正确的说法是__________。

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

D、某些关键活动若提前完成，将使整个工程提前完成。 二、填空题

1、一个图的 表示法是惟一的，而 表示法是不惟一的。 2、在有n个顶点的有向图中，每个顶点的度最大可 达 。 三、计算题

1、设有向图G如下图所示，试给出： （1）该图的邻接矩阵； （2）该图的邻接表；

（3）从V1出发的“深度优先”遍历序列； （4）从V1出发的“广度优先”遍历序列。

V1V2V3V4V8V5V6V7 2、对下图的AOE网，求出：

（1）每个事件的最早发生时间和最迟发生时间；

（2）每个活动的最早开始时间和最迟开始时间；

（3）画出关键活动组成的图。对哪些活动提速，可使整个工期提前。

213a6=2579846

本文来源：https://www.bwwdw.com/article/078o.html