南工大第四章-图.docx

《南工大第四章-图.docx》由会员分享，可在线阅读，更多相关《南工大第四章-图.docx（39页珍藏版）》请在三一文库上搜索。

1、数据结构与算法上机作业第四章 图一、选择题1、在一个无向图中，所有顶点的度数之和等于所有边数的C倍。A. 1/2B. 1C. 2D. 42、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的B倍。A. 1/2B. 1C. 2D. 43、 G 是一个非连通无向图，共有28 条边，则该图至少有D个顶点。A. 6B. 7C. 8D. 94、有 n 个顶点的图的邻接矩阵使用B数组存储的。A. 一维B. n 行 n 列C. 任意行 n 列D. n 行任意列5、对于一个具有n 个顶点和 e 条边的无向图， 采用邻接表表示， 则表头数组大小至少为（假设下标为 0 的数组参与使用）A。A. n -1B.

2、 n+1C. nD. n+e6、下列说法正确的是C。A. 有向图的邻接矩阵一定是不对称的B. 有向图的邻接矩阵一定是对称的C. 无向图的邻接矩阵一定是对称的D. 无向图的邻接矩阵可以不对称7、深度优先遍历类似与二叉树的A：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历8、广度优先遍历类似与二叉树的D：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历9、下列关于开放树(Free Tree)的说法错误的是C：A.具有 n 个结点的开放树包含n-1 条边B. 开放树没有回路C. 开放树可以是非连通图D. 在开放树中任意加一条边，一定会产生回路10、在如下图所示的图中，从顶点a 出发

3、，按深度优先遍历，则可能得到的一种顶点的序列为。A. a, b, e, c, d, fC. a, e, b, c, f, dB. a, c, f, e, b, dD. a, e, d, f, c, b11、在如上图所示的图中，从顶点a 出发，按广度优先遍历，则可能得到的一种顶点的序列为。A. a, b, e, c, d, fC. a, e, b, c, f, dB. a, b, e, c, f, dD. a, e, d, f, c, b12、设网 (带权的图 )有 n 个顶点和e 条边，则采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为C。A. O(n)B. O(n+e)C. O(

4、n 2)D. O(n 3)13、设图有n 个顶点和e 条边，求解最短路径的Floyd 算法的时间复杂度为O。A. O(n)B. O(n+e)C. O(n 2)D. O(n 3)14、最小生成树是指C。A. 由连通网所得到的边数最少的生成树。B. 由连通网所得到的顶点数相对较少的生成树。C. 连通网中所有生成树中权值之和为最小的生成树。D. 连通网的极小连通子图。15、下面关于工程计划的AOE 网的叙述中，不正确的是B。A. 关键活动不按期完成就会影响整个工程的完成时间。B. 任何一个关键活动提前完成，那么整个工程将会提前完成。C. 所有关键活动都提前完成，那么整个工程将会提前完成。D. 某些关

5、键工程若提前完成，那么整个工程将会提前完成。16、在AOE网中，始点和汇点的个数为C。A. 1个始点，若干个汇点B. 若干个始点，若干个汇点C. 若干个始点，1 个汇点C. 1个始点，1 个汇点17、在下图所示的无向图中，生的顶点次序为B从顶点。v1 开始采用Prim算法生成最小生成树，算法过程中产A. v1, v3, v4, v2, v5, v6 C. v1, v2, v3, v4, v5, v6B. v1, v3, v6, v2, v5, v4D. v1, v3, v6, v4, v2, v518、在上图所示的途中， 采用 Cruskal 算法生成最小生成树，过程中产生的边的次序是A. (

6、v1, v2), (v2, v3), (v5, v6), (v1, v5)B. (v1, v3), (v2, v6), (v2, v5), (v1, v4)C. (v1, v3), (v2, v5), (v3, v6), (v4, v5)D. (v2, v5), (v1, v3), (v5, v6), (v4, v5)C 。19、如下图所示的图中，其中一个拓扑排序的结果是A。A. v1 v2 v3 v6 v4 v5 v7 v8B. v1 v2 v3 v4 v5 v6 v7 v8C. v1 v6 v4 v5 v2 v3 v7 v8D. v1 v6 v2 v3 v7 v8 v4 v520、在下图所

7、示的AOE 网中，活动a9 的最早开始时间为B。A. 13B. 14C. 15D. 1621、在上图所示的AOE 网中，活动a4 的最迟开始时间为DA. 2B. 3C. 4D. 522、设图有n 个顶点和e 条边，当用邻接表表示该图时，则求解最短路径的Dijkstra 算法的时间复杂度为O。A. O(n)B. O(n+e)C. O(e)D. O(n 2)二、填空题1、若无向图G 中顶点数为n，则图 G 至多有n(n-1)/2条边；若 G 为有向图， 则图 G至多有n(n-1)条边。2 、图的存储结构主要有两种，分别是邻接表和邻接矩阵。3 、若G 是有向图，则把邻接到顶点v 的顶点数目或边数目称

8、为顶点v的入度； 把 邻 接 于 顶 点v的 顶 点 数 目 或 边 数 目 称 为 顶 点v的出度。4、已知一个图的邻接矩阵表示，计算第j 个顶点的入度的方法是第 j 行非 0 元素的个数，计算第 j 个顶点的出度的方法是第 j 列非 0 元素的个数。5、若将图中的每条边都赋予一个权，则称这种带权的图为网络。6 、无论是有向图还是无向图，顶点数n 、边数e 和各顶点的度D(v i) 之间的关系为：。7、若路径上第一个顶点v1 与最后一个顶点vm 重合 , 则称这样的简单路径为回路或环。8、如果图中任意一对顶点都是连通的, 则称此图是连通图；非连通图的极大连通子图叫做连通分量。9、创建一个邻接

9、矩阵图的复杂度是O（ n*n ）；创建一个链接表图的复杂度是O(n+e)。10、图的遍历有深度优先遍历和广度优先遍历等方法。11、在深度优先搜索和广度优先搜索中，都采用visitedi=0(false)的方式设置第i 个顶点为 new，而采用visitedi=1（ true）的方式标识第i 个结点为old。12、由于深度优先算法的特点，深度优先往往采用递归的方式实现。13、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构队列实现。14、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为搜索边。15、连通而且无环路的无向图称为开放数。16、对于含有 n 个顶点

10、e 条边的连通图，利用Prim 算法求其最小生成树的时间复杂度为O(n*n)，利用 Kruscal 算法求最小生成树的时间复杂度是O(e*lg e)。3 、 顶 点 表 示 活 动 的 网 简 称 为AOV； 边 表 示 活 动 的 网 简 称 为AOE。17、一个含有 n 个顶点的无向连通图，其每条边的权重都是a(a0)，则其最小生成树的权重等于（ n-1）*a。18、具有 n 个顶点的有向图， 如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的 Dijkstra 算法的时间复杂度是O(n*n)；如果采用邻接表表示该图，则时间复杂度为O(e)。19、在用 Dijkstra 算法求单

11、源最短路径的过程中，将顶点集合V 划分为两个集合S 和 V -S，其中 S 中的点为最短路径已确定的顶点集合， V -S 中的点为最短路径未确定的顶点集合。20 、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用算法，另一种方法是。21、假设有向图的邻接矩阵C 的传递闭包为A，则 Aij=1表示。22、有向图的中心点是指具有最小偏心度的顶点。三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。代码：#incl

12、udeusing namespace std;#define max_vexNum 26/ 最大顶点个数typedef structint vex_num, arc_num;/ 顶点数,边数int count;/记录当前顶点数char vexsmax_vexNum;/ 顶点向量double arcsmax_vexNummax_vexNum;/ 邻接矩阵 Graph;/添加一个新的顶点char NewNode(Graph *G,char v)G-vexsG -count=v;G-count+;return v;/寻找某个顶点的位置int FindPosition(Graph *G,char v)

13、for( int i=0;icount;i+)if(v=G -vexsi)return i;void Delete(Graph *G,char v)/先删除点int i,j;int temp_count=G-count;i=FindPosition(G,v);for(j=i;jvexsj=G -vexsj+1;G-count - ;/ 删除边/先删除行int p=i;/ 记住位置for(i=p;itemp_count -1;i+)for(j=0;jarcsij=G -arcsi+1j;/ 再删除列for(i=p;itemp_count -1;i+)for(j=0;jarcsji=G -arcs

14、ji+1;/建立 v1 与 v2 的一条边void SetSoucc(Graph * G,char v1,char v2)/先找到对应的定的位置int i,j;int temp_count= G -count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) /没有找到return ;/找到后， Aij=0;vexsji=0;G- arcsij=1;G- arcsji=1;void DelSucc(Graph * G,char v1,char v2)int i,j;int temp_count= G

15、-count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) /没有找到return ;/找到后， Aij=0;vexsji=0;G- arcsij=0;G- arcsji=0;/判断 v1y 与 v2 是否连接bool isEdge(Graph * G,char v1,char v2)int i,j;int temp_count= G -count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) /没有

16、找到return -1;if(G -arcsij=1)return true;return false;void Print(Graph * G)int i,j;for( i=0;icount;i+)for(j=0;jcount;j+)coutarcsij ;coutendl;coutcount=0;NewNode(G,A);NewNode(G,B);NewNode(G,C);NewNode(G,D);/插入边SetSoucc(G,A,B);SetSoucc(G,A,D);SetSoucc(G,C,B);Print(G);/删除一个顶点Delete(G,C);Print(G);/删除边DelS

17、ucc(G,A,D);Print(G);if(isEdge(G,A,B)coutA 与 B 右边 endl;return 0;四、已知一个有向图如下图所示，试给出图的邻接矩阵和邻接表存储示意图矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，种表示方法的存储结构、相关基本操作，并在主函数中创建该图。（画图，分别用要求编写两代码：#include#include #includeusing namespace std;#definemax_n20struct ArcNode char adjvex=#;ArcNode * next=NULL; ;typedef struct

18、VNodechar data;ArcNode* first_head; VNode ,AdjListmax_n;typedef struct AdjListvertices;intvexnum,arcnum;int count=0; Graph;/新增一个顶点char NewNode(Graph * G,char v) G-verticesG -count.data=v;G-verticesG -count.first_head=new ArcNode;G-count+;return v;/寻找某个顶点的位置int FindPosition(Graph *G,char v)for( int i

19、=0;icount;i+)if(v=G -verticesi.data)return i;/删除一个顶点void DelNode(Graph * G,char v)int i=FindPosition(G,v);/去头ArcNode *p=G - verticesi.first_head;/现在vertices 中删除int j;for(j=i;jcount -1;j+)G-verticesj=G -verticesj+1;G-verticesj.data=#;G-verticesj.first_head=NULL;G-count - ;/删除边ArcNode *q;while(p!=NULL

20、)q=p;p=p -next;q=NULL;/设置 v1 到 v2 直接的一条边void SetSucc(Graph * G,char v1,charv2)int i=FindPosition(G,v1);ArcNode *p;p=G-verticesi.first_head;while(p -next!=NULL)p=p-next;ArcNode *q=new ArcNode;q-adjvex=v2;p-next=q;ArcNode * FindNode(ArcNode * p,char v2)for(;p;p=p -next)if(p -next-adjvex=v2)break;retur

21、n p;void Detele(Graph * G,char v1,charv2)int i=FindPosition(G,v1);ArcNode *p;/没有找到if(i= -1)return ;p=FindNode(G -verticesi.first_head,v2);/ 因为 p 是上一个节点的位置，用q 来保存/ 要删除的节点的地址ArcNode *q = p -next;/ 通过将上一个节点的next 指针指向要删除节点的next 指/ 针志向的节点实现断开要删除节点的目的/ p-adjvex=p -next -adjvex;p-next = p -next -next;/删除要删

22、除的节点qdelete q;/输出领接表void Print(Graph * G)ArcNode *p;for(int i=0;icount;i+)/先将datacoutverticesi.data;/从每个顶点的头结点开始遍历if(G -verticesi.first_head -next!=NULL)p=G-verticesi.first_head -next;while(p!=NULL)coutadjvex;p=p-next;coutendl;coutendl;Graph * G=new Graph;int main() NewNode(G,A);NewNode(G,B);NewNode

23、(G,C);NewNode(G,D);Print(G);SetSucc(G,A,D);SetSucc(G,A,B);SetSucc(G,A,C);SetSucc(G,B,C);SetSucc(G,C,D);SetSucc(G,D,B);Print(G);Detele(G,A,C);Detele(G,D,B);Print(G);SetSucc(G,D,C);Print(G);return 0;五、已知一个图的顶点集为 a, b, c, d, e ，其邻接矩阵如下图，考虑图为无向图和有向图两种情况，分别画出该图。六、已知一个连通图如下图所示， 分别给出一个按深度优先遍历和广度优先遍历的顶点序列（假

24、设从顶点 v1 出发）。并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。代码：#include#include #include#includeusing namespace std;#definemax_n20struct ArcNode char adjvex=#;ArcNode * next=NULL; ;typedef struct VNode char data;ArcNode* first_head; VNode ,AdjListmax_n;typedef struct AdjListvertices;intintvi

25、sitmax_n = 0; /记录是否被访问过vexnum,arcnum;int count=0; Graph;/新增一个顶点char NewNode(Graph * G,char v) G-verticesG -count.data=v;G-verticesG -count.first_head=new ArcNode;G-count+;return v;/寻找某个顶点的位置int FindPosition(Graph *G,char v) for( int i=0; icount; i+) if(v=G -verticesi.data)return i;/删除一个顶点void DelNod

26、e(Graph * G,char v) int i=FindPosition(G,v);/去头ArcNode *p=G - verticesi.first_head;/现在vertices 中删除int j;for(j=i; jcount -1; j+)G-verticesj=G -verticesj+1;G-verticesj.data=#;G-verticesj.first_head=NULL;G-count -;/删除边ArcNode *q;while(p!=NULL) q=p;p=p-next;q=NULL;/设置 v1 到 v2 直接的一条边void SetSucc(Graph *

27、G,char v1,charv2) int i=FindPosition(G,v1);ArcNode *p;p=G-verticesi.first_head;while(p -next!=NULL) p=p-next;ArcNode *q=new ArcNode;q-adjvex=v2;p-next=q;/对于无向图void SetSucc1(Graph * G,char v1,charv2) SetSucc(G,v1,v2);SetSucc(G,v2,v1);ArcNode * FindNode(ArcNode * p,char v2) for(; p; p=p -next) if(p -n

28、ext -adjvex=v2)break;return p;void Detele(Graph * G,char v1,charv2) int i=FindPosition(G,v1);ArcNode *p;/没有找到if(i= -1)return ;p=FindNode(G -verticesi.first_head,v2);/因为 p 是上一个节点的位置，用q 来保存/要删除的节点的地址ArcNode *q = p -next;/通过将上一个节点的next 指针指向要删除节点的next 指/针志向的节点实现断开要删除节点的目的/ p-adjvex=p -next -adjvex;p-nex

29、t = p -next -next;/删除要删除的节点qdelete q;/输出领接表void Print(Graph * G) ArcNode *p;for(int i=0; icount; i+) /先将datacoutverticesi.data;/从每个顶点的头结点开始遍历if(G -verticesi.first_head -next!=NULL) p=G-verticesi.first_head -next;while(p!=NULL) coutadjvex;p=p-next;coutendl;coutendl;void makeVisitNull(Graph * G)for(int i=0;ivisiti=0;void Dfs_part(Graph * G,int i) ArcNode *p=G -verticesi.first_head -n