当前位置：文档库 › 数据结构第7章作业图答案

数据结构第7章作业图答案

第7章图

一、单选题

（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的倍。

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

B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有条边。

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

B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A ．栈 B. 队列 C. 树 D. 图（ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

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

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

（ D ）9. 已知图的邻接矩阵同上题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 （ C ）11. 已知图的邻接矩阵同上题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 （ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是

（ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是

???

???????????0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3

（ A ）14. 深度优先遍历类似于二叉树的

A ．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（ D ）15. 广度优先遍历类似于二叉树的

A ．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（ A ）16. 任何一个无向连通图的最小生成树

A ．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）

二、填空题

1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

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

3. 如果n 个顶点的图是一个环，则它有 n 棵生成树。（以任意一顶点为起点，得到n-1条边）

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

5. n 个顶点e 条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。

6. 设有一稀疏图G ，则G 采用邻接表存储较省空间。

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

8. 图的逆邻接表存储结构只适用于有向图。

9. 已知一个图的邻接矩阵表示，删除所有从第i

10. 图的深度优先遍历序列不是惟一的。

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

表存储时，该算法的时间复杂度为 O(n+e) 。

12. n 个顶点e 条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n 2) ；若采用邻接

表存储，该算法的时间复杂度为 O(n+e) 。

13. 图的BFS 生成树的树高比DFS

14. 用普里姆(Prim)算法求具有n 个顶点e 条边的图的最小生成树的时间复杂度为 O(n 2) ；用克鲁

A ．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2

斯卡尔(Kruskal)算法的时间复杂度是O(elog2e) 。

15. 若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal) 算法来求解。

16. 若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。

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

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

三、分析求解题

1. 已知如图所示的有向图，请给出该图的:

（2）邻接矩阵；

（3）邻接表；

（4）逆邻接表。

答案：

2. 请对下图的无向带权图：

（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：设起点为a 。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!

邻接矩阵为：

→

→ → → →

→ → → → → → → → → → → ^ → → → ^ → → → ^ → → → ^

??????????????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞064560252036307945670555505395504340

先罗列：f ---2---g a —3--c

f —3—e a —4---b d —4—h

(a,b,c) (e,f,g) (d,h) 取b —5—d, g —5--d 就把三个连通分量连接起来了。

3. 已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

4. 试利用Dijkstra 算法求图中从顶点a 到其他各顶点间的最短路径，写出执行算法过程中各步的状态。

解：最短路径为：（a,c,f,e,d,g,b ）

5．给定下列网G:

（1）试着找出网G 的最小生成树，画出其逻辑结构图；（2）用两种不同的表示法画出网G 的存储结构图；

（3）用C 语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。

解：（1

（2???

???????????∞∞∞∞

∞

∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞1012

696841015

121520982012412

→ →^

→ →→ → ^

→ →→ ^ → →^ → →→ ^ → →^ → →

五、算法设计题

1. 编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 {

InitALGraph(G); scanf("%d",&v);

if(v<0) return ERROR; //顶点数不能为负 G .vexnum=v; scanf("%d",&a);

if(a<0) return ERROR; //边数不能为负

G.arcnum=a;

for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号

for(m=1;m<=a;m++)

{

t=getchar();h=getchar(); //t为弧尾,h为弧头

if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到

p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;

else

{

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);

q->nextarc=p;

}

p->adjvex=j;p->nextarc=NULL;

}//while

return OK;

}//Build_AdjList

2. 试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？提示：将邻接矩阵的第i行全部置0 ）

解：//本题中的图G均为有向无权图。

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)

{

if((i=LocateVex(G,v))<0) return ERROR;

if((j=LocateVex(G,w))<0) return ERROR;

if(G.arcs[i][j].adj)

{

G.arcs[i][j].adj=0;

G.arcnum--;

}

return OK;

}//Delete_Arc

3. 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点v i到顶点v j的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j

是否有路径,是则返回1,否则返回0

{

if(i==j) return 1; //i就是j

else

{

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

}//for

}//else

}//exist_path_DFS

解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。）

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int level＝1;//递归进行的层数

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j

是否有路径,是则返回1,否则返回0

{

if(i==j) return 1; //i就是j

else

{

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--)

{ level++;

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

}//for

}//else

if (level==1) return 0;

}//exist_path_DFS

附加题：【严题集7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。

（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。

注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G

的顶点i到j是否存在长度为k的简单路径

{

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求

else if(k>0)

{

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一}//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中}//else

return 0; //没找到

}//exist_path_len

数据结构--图重点

一、定义与术语图：无序数据结构基本构成：1.边集（Edge ）：a. 有向图，有向边，弧，弧头，弧尾，权值 b. 无向图，无向边(v, w)，权值 2.顶点集（Vertices ）：a. 无向图：度(TD(v)) b. 有向图：出度(ID(v))，入度(OD(v))，度(TD(v) = ID(v) + OD(v)) 无向完全图：n 个顶点，(1)2 n n -条边有向完全图：n 个顶点，(1)n n -条边网：带权图连通分量：无向图中的极大连通子图（多个），无向完全图的连通分量就是本身（一个）强连通分量：有向图中的极大连通子图，其中i v 到j v 以及j v 到i v 都有路径生成树：图的极小连通子图，含有图的全部n 个顶点，只有n-1条边，少一条则不能连通，多一条则形成回路生成森林：不完全图中的各个连通分量的生成树，构成图的生成森林二、存储结构顶点：可采用链表或数组存储顶点列表，一般采用链表存储边：1. 邻接矩阵（数组） a. 无向图：对称阵，可采用矩阵压缩存储方式。A[i][j] = 0表示i v 和j v 没有连接； A[i][j] = 1表示i v 和j v 有边连接；第i 行的和表示顶点i v 的度 b. 有向图：不对称阵。,[][]i j A i j w =表示顶点i v 到j v 的有向弧的权值；[][]A i j =∞ 表示表示顶点i v 到j v 没有弧连接或者i = j 2. 邻接表（链表，有向无向都可用）边结点：adjvex （邻接点），nextarc （下一条边），info （权值）顶点结点：data （顶点数据），firstarc （第一条边） 3. 十字链表（Othogonal List ）弧结点：tailvex （弧尾结点），headvex （弧头结点），tlink （弧尾相同的下一条弧），hlink （弧头相同的下一条弧），info （权值）顶点结点：data （顶点数据），firstin （第一条入弧），firstout （第一条出弧）三、图的遍历（每个顶点只被访问一次） 1. 深度优先遍历（类似树的先根遍历）基本思想：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v 出发，访问此结点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问（非连通图），则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

数据结构-图习题

第8章图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。【解答】【证明】在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。【解答】点，它不是强连通的有向图。各个顶点自成强连通分量。所谓简单路径是指该路径上没有重复的顶点。从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的无向完全图 2个顶点的无向完全图 3个顶点的无向完全图 4个顶点的无向完全图 5个顶点的无向完全图 A D

????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。从顶点E 出发，到其他各个顶点的简单路径无。从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】 (1) 邻接矩阵 A D

数据结构中图的全部操作

#include #include #include #include #include #include using namespace std; #define MAX_VERTEX_NUM 100 #define INFINITY INT_MAX #define EXTERN 10 #define OK 1 #define ERROR -1 #define MAX -1 #define MAXW 10000 typedef int Status; typedef bool VisitIf; typedef char VertexType;//顶点数据类型 typedef int VRType; //顶点关系( 表示是否相邻) typedef int InfoType; //弧相关信息

typedef enum{DG,DN,UDG,UDN} GraphKind;//图的类型 bool visited[MAX_VERTEX_NUM]; //邻接矩阵 typedef struct ArcCell { VRType adj;//权值 InfoType *info; }ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMartix arcs; //邻接矩阵 int vexnum,arcnum; //图当前顶点数,弧数 GraphKind Kind; //图的类型 }MGraph; bool VexExist(MGraph G,VertexType v)//判断定点是否在图中{

数据结构图的存储结构及

数据结构图的存储结构及基本操作

1.实验目的通过上机实验进一步掌握图的存储结构及基本操作的实现。 2.实验内容与要求要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。 3.数据结构设计逻辑结构：图状结构存储结构：顺序存储结构、链式存储结构 4.算法设计 #include #include #include #define MAX_VERTEX_NU M 20 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc;

}ArcNode; typedef struct VNode { char data[2]; //顶点就设置和书上V1等等一样吧 ArcNode *firstarc; }VNode,AdjList[MAX _VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; typedef struct { int data[MAX_VERTEX_ NUM+10]; int front; int rear; }queue; int visited[MAX_VERTE X_NUM]; queue q; int main() { ALGraph G; int CreateUDG(ALGraph &G); int DeleteUDG(ALGraph &G); int InsertUDG(ALGraph &G); void BFSTraverse(ALGrap h G, int (*Visit)(ALGraph

数据结构图练习试题

图练习： 1．图中有关路径的定义是（）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（）条边。 2．n． n(n+1)/2 D．0 EA．n-1 B．n(n-1)/2 C3．一个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 8. 下列说法不正确的是（）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 9．无向图G=(V,E),其中： V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。 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 10. 关键路径是事件结点网络中（）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路

数据结构-图习题

????????? ?????? ?????=01 00000001001010000 010********* Edge 第8章图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n -1)/2。【解答】【证明】在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n -1 条边与其他n -1个顶点相连，总计n 个顶点有n(n -1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n -1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。【解答】判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成强连通分量。所谓简单路径是指该路径上没有重复的顶点。从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A →D →B →C →F 。从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。从顶点E 出发，到其他各个顶点的简单路径无。从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】 (1) 邻接矩阵 1个顶点的无向完全图 2个顶点的无向完全图 3个顶点的无向完全图 4个顶点的无向完全图 5个顶点的无向完全图

数据结构图习题

第七章图：习题习题一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。

数据结构第六章图练习题及答案详细解析(精华版)

图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 ⑵ n个顶点的强连通图至少有（）条边，其形状是（）。 A n B n+1 C n-1 D n×(n-1) E 无回路 F 有回路 G 环状 H 树状【解答】A，G ⑶含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。 A 1 B n/2 C n-1 D n

数据结构第7章作业 图答案

数据结构--图重点

数据结构-图习题

数据结构中图的全部操作

最新数据结构习题与答案--图

数据结构图的存储结构及

数据结构图练习试题

数据结构-图习题

数据结构图习题

数据结构 第六章 图 练习题及答案详细解析(精华版)

数据结构第7章作业图答案

数据结构第六章图练习题及答案详细解析(精华版)