数据结构第章图习题.doc
《数据结构第章图习题.doc》由会员分享,可在线阅读,更多相关《数据结构第章图习题.doc(7页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、习题7 图7.1 单项选择题1在一个图中,所有顶点的度数之和等于所有边数的_倍。A. 1/2 B. 1 C. 2 D. 4 2任何一个无向连通图的最小生成树 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的_倍。A. 1/2 B. 1 C. 2 D. 44一个有n个顶点的无向图最多有_条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n5具有4个顶点的无向完全图有_条边。A. 6 B. 12 C. 16 D. 206具有6个顶点的无向图至少应有_条边才能确保是一个连通图。A. 5 B. 6 C. 7 D.
2、87在一个具有n个顶点的无向图中,要连通全部顶点至少需要_条边。A. n B. n+1 C. n-1 D. n/28对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是_。A. n B. (n-1)2 C. n-1 D. n29对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为_;所有邻接表中的接点总数是_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一个图如图7.1所示,若从顶点a出发按深度搜索法进行遍历,则可能得到的一种顶点序列为_;按宽度搜索法进行遍历,则可能得到的一种顶点序列为_。
3、A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bbaecdf图 7.1 一个无向图11已知一有向图的邻接表存储结构如图7.2所示。12345324524图7.2 一个有向图的邻接表存储结构 根据有向图的深度优先遍历算法,从顶点v1出发,所得到的顶点序列是_。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根据有向图
4、的宽度优先遍历算法,从顶点v1出发,所得到的顶点序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历13采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历14判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用_。A. 求关键路径的方法 B. 求最短路径的Dijkstra方法C. 宽度优先遍历算法 D.
5、 深度优先遍历算法15关键路径是事件结点网络中 。A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路 D.最短的回路16下面不正确的说法是 。 (1)在AOE网中,减小一个关键活动上的权值后,整个工期也就相应减小; (2)AOE网工程工期为关键活动上的权之和; (3)在关键路径上的活动都是关键活动,而关键活动也必在关键路径上。A.(1)B.(2)C.(3)D.(1)、(2)17用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印出相应的顶点,则输出的顶点序列是 。A.逆拓朴有序的B.拓朴有序的C.无序的18在图7.3所示的拓朴排列的结果序列为 。A.125634B.516
6、234C.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-k2D.k1+k27.2 填空题(将正确的答案填在相应饿空中)1n个顶点的连通图至少_条边。2在无权图G的邻接矩阵A中,若(vi,vj)或vi,vj属于图G的边集合,则对应元素Aij等于_
7、,否则等于_。3在无向图G的邻接矩阵A中,若Aij等于1,则Aji 等于_。4已知图G的邻接表如图7.4所示,其从顶点v1出发的深度有限搜索序列为_,其从顶点v1出发的宽度优先搜索序列为_。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3 图7.4 图G的邻接表5已知一个有向图的邻接矩阵表示,计算第i个结点的入度的方法是_。6已知一个图的邻接矩阵表示,删除所有从第i个结点出发的边的方法是_。7如果含n个顶点的图形成一个环,则它有 棵生成树。8一个非连通无向图,共有28条边,则该图至少有 个顶点。9遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ,DFS遍历图的时间复杂度为 ,两
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第章图 习题
限制150内