工大数据结构第四章作业.docx

《工大数据结构第四章作业.docx》由会员分享，可在线阅读，更多相关《工大数据结构第四章作业.docx（69页珍藏版）》请在第一文库网上搜索。

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

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

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

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

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

6、 v3), (v5, v6), (vl, v5)B. (vl, v3), (v2, v6), (v2, v5), (vl, v4)C. (vl, v3), (v2, v5), (v3, v6), (v4, v5)D. (v2, v5), (vl, v3), (v5, v6), (v4, v5) 10、如下图所示的图中，其中一个拓扑排序的结果是A 。A. Vv2f v3f v6f v4f v5f v7f v8B. vl-v2-v3-v4-v5-v6-v7-v8C. vl-v6-v4-v5-v2-v3-v7-v8D. vl-v6-v2-v3-v7-v8-v4-v5VIBA.13 B. 14 C.

7、15 D.1620、在上图所示的AOE网中，活动a4的最迟开始时间为D19、在下图所示的AOE网中，活动a9的最早开始时间为A.4B.5 C. 6D.721、设图有n个顶点和e条边，当用邻接矩阵表示该图时，则求解最短路径的Floyd算法的时间复杂度为 D oA. O(n) B. O(n+e) C. O(n2) D. O(n3)二、填空题1、若无向图G中顶点数为n,则图G至多有 n*(n-l)/2 条边:若G为有向图，则图G至多有 n*(n-l)条边。2、图的存储结构主要有两种，分别是一邻接矩阵 和 邻接叁O3、若G是有向图，则把邻接到顶点v的顶点数目或边数目称为顶点v的 指针域;把邻接于顶点v

8、的顶点数目或边数目称为顶点v的 顶点M。4、己知一个图的邻接矩阵表示，计算第j个顶点的入度的方法是 第i列元素之和，计算第i个顶点的出度的方法是第i行非零元素之和 o5、若将图中的每条边都赋予一个权，则称这种带权的图为网络 o6、无论是有向图还是无向图，顶点数n、边数e和各顶点的度D(%)之间的关系为：7、若路径上第一个顶点v,与最后一个顶点vm重合，则称这样的简单路径为回。8、如果图中任意一对顶点都是连通的，则称此图是一 连通图;非连通图的极大连通子图叫做连通分量 o创建一个邻接矩阵图的复杂度是 0(n2)；创建一个链接表图的复杂度是O(2e+n)o9、图的遍历有深度优先搜索 和广度优先遍历

9、等方法。10、在深度优先搜索和广度优先搜索中，都采用visitedi=l 的方式设置第i个顶点为new,而采用visitedfil=()的方式标识第i个结点为old。11、由于深度优先算法的特点，深度优先往往采用递归的方式实现。12、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构队列实现。13、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为树边和回退边 O14、连通而且无环路的无向图称为开放树。15、对于含有n个顶点e条边的连通图，利用Prim算法求其最小生成树的时间复杂度为0(n2),利用Kruscal算法求最小生成树的时间复杂度是O(|E|*k)g|

10、E|)o3、顶点表示活动的网简称为；边表示活动的网简称为AOE o16、一个含有n个顶点的无向连通图，其每条边的权重都是a(a0),则其最小生成树的权重等于o17、具有n个顶点的有向图，如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的Diikstra算法的时间复杂度是 0(n2)；如果采用邻接表表示该图，则时间复杂度为 0(e)o18、在用Dijkstra算法求单源最短路径的过程中，将顶点集合V划分为两个集合S和V-S,其中S中的点为, V-S中的点为 从Y-S中选择顶点，使Dw的值最小并将w加入集合S中，则w的最小路径-求出 o19、求每一对顶点之间的最短路径，可以用两种方法，一

11、种是分别对每个顶点采用算法，另一种方法是 对每个边采用算法。20、假设有向图的邻接矩阵C的传递闭包为A,则AiJ|jJ=l表示 (i,i)属于E o21、有向图的中心点是指具有最小偏心度的结点 o三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图(画图，分别用矩阵和数组链表图表示)，并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。/邻接表表示：#includeusing namespace std;#define freever #define Num Vertices 6typedef char Vertex

12、Data;typedef int EdgeData;顶点个数顶点数据类型/边上权值类型typedef struct node int adjvex;EdgeData cost;struct node *next; EdgeNode;typedef struct VertexData vertex;EdgeNode * firstedge;)VertexNode;边表结点邻接点域（下标）/边上的权值下一边链接指针顶点表结点顶点数据域/边链表头指针typedef struct 图的邻接表VertexNode vex!istNumVertices+1 ;int n, e;图中当前的顶点个数与边数 A

13、djGraph;void IniADJGraph(AdjGraph *G)G-e=0;G-n=0;for(int i=l; ivexlistli.vertex=freever;G-vexlisti.firstedge=NULL;)bool NewNode(AdjGraph *G VertexData v)增力n一个顶点，成功，返回 true,否则返回 false(if(G-nNum Vertices-1)(for(int i=l; ivexlisti.vertex=freever)(G-vexlisti.vertex=v;G-vexlisti.firstedge=NULL;G-n+;retur

14、n true;)return false;)bool IsEdge(AdjGraph *G, int vl,int v2)/ 判断 vl 与 v2 之间是否有边相连(EdgeNode *p=G-vexlistvIJ.firstedge;if(p=NULL)return false;while(l)(if(p-adjvex=v2)(return true;)p=p-next;if(p=NULL)return false;return false;)void DelSucc(AdjGraph *G, int vl, int v2) / 册U除 vl 和 v2 之间的一条边(if(IsEdge(G, vl, v2)EdgeNode *p=G