数据结构第五章图习题
10页1、精品文档5 图【单选题】1.设无向图G中有五个顶点,各顶点的度分别为2、 4、 3、 1、 2,则 G中边数为( C)。、 4 条、 5 条、 6 条、无法确定2.含 n 个顶点的无向完全图有(D)条边;含n 个顶点的有向图最多有(C)条弧;含n 个顶点的有向强连通图最多有(C)条弧;含n 个顶点的有向强连通图最少有()条弧;设无向图中有n 个顶点,则要接通全部顶点至少需(G)条边。A、 n2B、 n(n+1)C、 n(n-1)D、 n(n-1)/2E、 n+1F、 nG、n-13. 对下图从顶点 a 出发进行深度优先遍历,则( A)是可能得到的遍历序列。A、 acfgdebB、 abcdefgC、acdgbefD、 abefgcd对下图从顶点a 出发进行广度优先遍历,则(D)是不可能得到的遍历序列。A、 abcdefgB、 acdbfgeC、abdcegfD、 adcbgef0104.设图 G的邻接矩阵A= 101010,则 G中共有 (C)个顶点; 若 G为有向图, 则 G中共有 (D)条弧;若 G为无向图,则G中共有( B)条边。A、 1B、 2C、 3D、 4E、5F、 9G、
2、以上答案都不对5. 含 n 个顶点的图,最少有( B)个连通分量,最多有( D)个连通分量。A、 0B、 1C、 n-1D、 n6.用邻接表存储图所用的空间大小(A)。A、与图的顶点数和边数都有关B、只与图的边数有关C、只与图的顶点数有关D、与边数的平方有关7. n 个顶点的无向图的邻接表最多有(B)个表结点。A、 n2B、 n(n-1)C、 n(n+1)D、 n(n-1)/28.无向图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),对该图进行深度优先遍历,得到的顶点序列正确的是(D)。A、 a,b,e,c,d,fB、 a,c,f,e,b,dC、 a,e,b,c,f,dD、 a,e,d,f,c,b。1欢迎下载精品文档9. 图的 BFS生成树的树高比 DFS生成树的树高( A)。A、小或相等B、小C、大或相等D、大10. 下列不正确的是( C)。(1) 求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra )最短路径算法中弧上权不能为负的原因是在实际应用中无意义;(2) 利用 Dijkstr
3、a求每一对不同顶点之间的最短路径的算法时间是3O(n ) ;(图用邻接矩阵表示)(3)Floyd 求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。A、 (1),(2),(3)B、 (1)C、(1),(3)D、 (2),(3)11. 当各边上的权值( A)时, BFS算法可用来解决单源最短路径问题。A、均相等B、均互不相等C、不一定相等12.若一个有向图具有拓扑排序序列,那么它的邻接矩阵必定为(C)。A、对称矩阵B、稀疏矩阵C、三角矩阵D、一般矩阵13.在有向图G的拓扑序列中,若顶点Vi 在顶点 Vj 之前,则下列情形不可能出现的是(D)。A、 G中有弧 B、 G中有一条从 Vi 到 Vj 的路径C、 G中没有弧 D、G中有一条从 Vj 到 Vi 的路径14. 关键路径是 AOE网中( B)。A、从始点到终点的最短路径B、从始点到终点的最长路径C、人始点到终点的边数最多的路径D、从始点到终点的边数最少的路径15.下面关于求关键路径的说法不正确的是(C)。A、求关键路径是以拓扑排序为基础的B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C、一个事件的最迟
《数据结构第五章图习题》由会员汽***分享,可在线阅读,更多相关《数据结构第五章图习题》请在金锄头文库上搜索。
小学语文毕业考试卷及答案
个人租车合同标准样本(8篇)
晋升个人工作总结范本(2篇).doc
公司总经理工作报告中建6篇
(完整word版)2015~2016四年级上册科学教学工作总结
部门经理个人年终总结标准范本(二篇).doc
《范进中举》分层作业设计
消防维保投标书模版
2022年德育工作经验交流材料-班级特色文化
《用色彩表达情感》教案
特气管道施工流程
招生专员工作职责2022岗位职责
城市排水及污水处理厂系统组成
试验检测委托合同格式范本(8篇)
政史地教研组工作总结
幼儿园2023年清明节放假通知及安全教育告家长书3篇
2022年金属非金属矿山(小型露天采石场)安全管理人员资格考试题库及模拟卷含参考答案69
幼儿园中班案例:VeryGood你一定能行
光伏项目用地控制指标要点十问
村卫生室建设动员会发言
2023-02-22 2页
2023-05-07 14页
2022-09-25 35页
2022-11-22 45页
2024-01-21 7页
2024-02-25 13页
2023-02-05 16页
2023-10-27 6页
2023-01-11 35页
2024-01-14 26页