资源描述：
《数据结构1new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题7图7.1单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。A.1/2B.1C.2D.42．任何一个无向连通图的最小生成树。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。A.1/2B.1C.2D.44．一个有n个顶点的无向图最多有____条边。A.nB.n(n-1)C.n(n-1)/2D.2n5．具有4个顶点的无向完全图有____条边。A.6B.12C.16D.206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。A.5B.
2、6C.7D.87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。A.nB.n+1C.n-1D.n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。A.nB.(n-1)2C.n-1D.n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。①A.nB.n+1C.n-1D.n+e②A.e/2B.eC.2eD.n+e10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度
3、搜索法进行遍历，则可能得到的一种顶点序列为__②__。①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,bbaecdf图7.1一个无向图11．已知一有向图的邻接表存储结构如图7.2所示。12345324524^^^^^图7.2一个有向图的邻接表存储结构⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5
4、C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v212．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。A.先序遍历B.中序遍历C.后序遍历D.按层遍历13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。A.先序遍历B.中序遍历C.后序遍历D.按层遍历14．判定一个有向图是否存在回路除了可以利用拓扑排序方法
5、外，还可以利用____。A.求关键路径的方法B.求最短路径的Dijkstra方法C.宽度优先遍历算法D.深度优先遍历算法15．关键路径是事件结点网络中。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路16．下面不正确的说法是。（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小；（2）AOE网工程工期为关键活动上的权之和；（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。A.（1）B.（2）C.（3）D.（1）、（2）17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相
6、应的顶点，则输出的顶点序列是。A.逆拓朴有序的B.拓朴有序的C.无序的18．在图7.3所示的拓朴排列的结果序列为。A.125634B.516234C.123456D.521634图7.3有向图19．一个有n个顶点的无向连通图，它所包含的连通分量个数为。A.0B.1C.nD.n+120．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为。A.k1B.k2C.k1-k2D.k1+k221．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为。A.k1B.k2C.k1-
7、k2D.k1+k27.2填空题（将正确的答案填在相应饿空中）1．n个顶点的连通图至少____条边。2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于____。4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3图7.4图G的邻接表5．已知一个有向图的邻
8、接矩阵表示，计算第i个结点的入度的方法是____。6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。7．如果含
