图的应用试题

01.任何一个无向连通图的最小生成树( )。
A.有一棵或多棵                                                B.只有一棵
C.一定有多棵                                                   D.可能不存在

02.用Prim算法和Kruskal算法构造图的最小生成树,所得到的最小生成树()。
A.相同                                                               B.不相同
C.可能相同,可能不同                                      D.无法比较

03.以下叙述中,正确的是( )。
A.只要无向连通图中没有权值相同的边,则其最小生成树唯一
B.只要无向图中有权值相同的边,则其最小生成树一定不唯一
C.从n个顶点的连通图中选取n-1条权值最小的边,即可构成最小生成树
D.设连通图G含有n个顶点,则含有n个顶点、n-1条边的子图一定是G的生成树

04.设有n个顶点的无向连通图的最小生成树不唯一,则下列说法中正确的是( )。
A.图的边数一定大于n- 1
B.图的权值最小的边一定有多条
C.图的最小生成树的代价不一定相等
D.图的各条边的权值不相等

05.用Prim算法求一个带权连通图的最小生成树,在算法执行的某个时刻,已选取的顶点
集合U={1,2,3},已选取的边集合TE={(1,2),(2,3)},要选取下一条权值最小的边,应当从( )组中选取。
A. {(1,4),(3,4),(3,5),(2,5)}
B.{(3,4),(3,5), (4,5), (1,4)}
C. {(1,2),(2,3),(3,5)}
D. {(4,5), (1,3),(3,5)}

06.用Kruskal算法求一个带权连通图的最小生成树,在算法执行的某个时刻,已选取的边
集合TE={(1,2),(2,3),(3,5)},要选取下一条权值最小的边,不可能选取的边是( ).
A.(3,6)
B. (2,4)
C. (1,3)
D. (1,4)

07.下列关于图的最短路径的相关叙述中,正确的是( ).
A.最短路径一定是简单路径
B.Dijkstra算法不适合求有回路的带权图的最短路径
C.Dijkstra算法不适合求任意两个顶点的最短路径
D.Floyd算法求两个顶点的最短路径时,pathk-1一定是pathk的子集

08.下列关于图的最短路径的相关叙述中,正确的是( )。
Ⅰ Dijkstra算法求单源最短路径不允许边的权为负
Ⅱ.Dijkstra算法求每对顶点间的最短路径的时间复杂度是O(n2)
Ⅲ. Floyd算法求每对顶点间的最短路径允许边的权为负,但不允许含有负边的回路
A.I、Ⅱ和Ⅲ                        B.仅I                        C.I和Ⅲ                        D.II和Ⅲ


10. 用Dijkstra算法求一个带权有向图的从顶点0出发的最短路径,在算法执行的某个时刻,已求得的最短路径的顶点集合S= {0,2,3,4},下一个选取的目标顶点是顶点1,则可能修改的最短路径是()。
A.从顶点0到顶点3的最短路径
B.从顶点0到顶点2的最短路径
C.从顶点2到顶点4的最短路径
D.从顶点0到顶点1的最短路径

11.下面的( )方法可以判断出一个有向图是否有环(回路)。
Ⅰ深度优先遍历        Ⅱ.拓扑排序        Ⅲ.求最短路径        IV.求关键路径
A.I、II、IV                        B.I、Ⅲ、IV                C.I、II、Ⅲ                D.全部可以

12.在有向图G的拓扑序列中,若顶点v在顶点v之前,则不可能出现的情形是( )。
A.G中有弧<vi,vj>
B.G中有一条从vi到vj的路径
C.G中没有弧<vi,vj>
D.G中有一条从vj到vi的路径

13.下列关于拓扑排序的说法中,错误的是()。
Ⅰ若某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中为暂存入度为零的顶点,可以使用栈,也可以使用队列
Ⅲ、若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
IV.若有向图的拓扑有序序列唯一,则图中入度为0和出度为0的顶点都仅有1个
A.I、Ⅲ、IV                B.Ⅲ、IV                        C.II、IV                        D.Ⅲ

14.下列关于拓扑排序的说法中,正确的是().
Ⅰ强连通图不能进行拓扑排序
II.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a, b>A.仅I
B.仅П
C.I和I
D,都不正确

15.若一个有向图的顶点不能排成一个拓扑序列,则判定该有向图( ).
A.含有多个出度为0的顶点
B.是个强连通图
C.含有多个入度为0的顶点
D.含有顶点数大于1的强连通分量

16.下图所示有向图的所有拓扑序列共有()个。

A.4
B.6
C.5
D.7


 

18.下列哪种图的邻接矩阵是对称矩阵?()
A.有向网
B.无向图
C.AOV网
D.AOE网

19.若一个有向图具有有序的拓扑排序序列,则它的邻接矩阵必定为()。
A.对称
B.稀疏
C.三角
D.一般

20.用DFS算法遍历一个无环有向图,并在 DFS算法退栈返回时输出相应的顶点,则输出的顶点序列是()。
A.逆拓扑有序                  B.拓扑有序                        C.无序的                D.无法确定

21.下列关于图的说法中,正确的是().
Ⅰ有向图中顶点V的度等于其邻接矩阵中第V行中1的个数
Ⅱ.无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵
Ⅲ.在带权图G的最小生成树G中,某条边的权值可能会超过未选边的权值
IV.若有向无环图的拓扑序列唯一,则可以唯一确定该图
A. I、II和Ⅲ                        B.Ⅲ和IV                        C.Ⅲ                       D.IV

22.下图所示的AOE网中,关键路径长度为()。

A. 16                                B. 17                        C. 18                        D. 19


A.19                                B.20                        C. 21                        D.22

24.下面关于求关键路径的说法中,不正确的是( )。
A.求关键路径是以拓扑排序为基础的
B.一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同
C.一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持
续时间的差
D.任何一个活动的持续时间的改变可能会影响关键路径的改变

25.下列关于关键路径的说法中,正确的是()
Ⅰ改变网上某一关键路径上的任意一个关键活动后,必将产生不同的关键路径
Ⅱ.在AOE图中,关键路径上活动的时间延长多少,整个工期也就随之延长多少
Ⅲ.缩短关键路径上任意一个关键活动的持续时间可缩短关键路径长度
IV.缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度
V.缩短多条关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度
A.Ⅱ和V
B.Ⅰ、Ⅱ和IV
C.Ⅱ和IV
D.Ⅰ和IV

26.在求AOE网的关键路径时,若该有向图用邻接矩阵表示且第i列值全为o,则( )。
A.若关键路径存在,第i个顶点一定是起点
B.若关键路径存在,第i个顶点一定是终点
C.关键路径不存在
D.该有向图对应的无向图存在多个连通分量

27.【2010统考真题】对下图进行拓扑排序,可得不同拓扑序列的个数是( )。

A.4
B.3
C.2
D.1

28.【2012统考真题】下列关于最小生成树的叙述中,正确的是()。
Ⅰ.最小生成树的代价唯一
Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ.使用Prim算法从不同顶点开始得到的最小生成树一定相同
IV.使用Prim算法和Kruskal算法得到的最小生成树总不相同
A.仅Ⅰ
B.Ⅰ、Ⅱ和IV
C.Ⅱ和IV
D.Ⅰ和IV

29.【2012统考真题】对下图所示的有向带权图,若采用Dijkstra算法求从源点α到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是()。

A. d, e,f
B. e, d,f
C. f, d, e
D. f, e, d

30.【2012统考真题】若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是().
A.存在,且唯一                                        B.存在,且不唯一
C.存在,可能不唯一                                D.无法确定是否存在

31.【2013统考真题】下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可缩短整个工程的工期。在下列选项中,加快其进度就可缩短工程工期的是()

A.c和e                        B.d和c                                 C.f和d                                    D.f和h

32.【2014统考真题】对下图所示的有向图进行拓扑排序,得到的拓扑序列可能是()。

A. 3,1,2,4,5,6                 B. 3,1,2,4,6,5                  C. 3,1,4,2,5,6                       D.3,1,4,2,6,5

33.【2015统考真题】求下面的带权图的最小(代价)生成树时,可能是Kruskal算法第2次选中但不是Prim算法(从V开始)第2次选中的边是()。

A.(V1, V3)                        B. (V1, V4)                        C. (V2, V3)                        D. (V3, V4)

34.【2011统考真题】下列关于图的叙述中,正确的是( )。
Ⅰ.回路是简单路径
Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间
Ⅲ.若有向图中存在拓扑序列,则该图不存在回路
A.仅Ⅱ
B.仅Ⅰ、Ⅱ
C.仅Ⅲ
D.仅Ⅰ、Ⅲ

35.【2016统考真题】使用Dijkstra算法求下图中从顶点1到其他各顶点的最短路径,依次
得到的各最短路径的目标顶点是()

A. 5,2,3,4,6
B. 5,2,3,6,4
C. 5,2,4,3,6
D.5,2,6,3,4

36.【2016统考真题】若对n个顶点、e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是()。
A. O(n)
B.O(n+e)
C. O(n2)
D. O(ne)

37.【2018统考真题】下列选项中,不是如下有向图的拓扑序列的是().

A.1,5,2,3,6,4
B. 5,1,2,6,3,4
C. 5,1,2,3,6,4
D.5,2,1,6,3,4

38.【2019统考真题】下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是( ).

A.3和7                          B.12和12                     C.12和 14                        D.15和15

39.【2019统考真题】用有向无环图描述表达式(x+y)(x+y)/x),需要的顶点个数至少是
( ).
A.5                                B.6                                C. 8                                D.9

40.【2020统考真题】已知无向图G如下所示,使用Kruskal算法求图G的最小生成树,加到最小生成树中的边依次是( ).

A. (b,f) (b, d ),(a, e),(c, e), (b, e)                        B. (b,f ), (b, d), (b, e),(a, e), (c, e)
C. (a, e), (b,e), (c, e), (b, d ),(b,f )                      D. (a,e),(c,e), (b,e),(b,f), (b,d )

41. 【2020统考真题】修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的( )。
A.拓扑有序序列                                                B.逆拓扑有序序列
C.广度优先搜索序列                                        D.深度优先搜索序列

42.【2020统考真题】若使用AOE网估算工程进度,则下列叙述中正确的是()。
A.关键路径是从源点到汇点边数最多的一条路径
B.关键路径是从源点到汇点路径长度最长的路径
C.增加任意一个关键活动的时间不会延长工程的工期
D.缩短任意一个关键活动的时间将会缩短工程的工期

43.【2021统考真题】给定如下有向图,该图的拓扑有序序列的个数是()。

A.1                                 B.2                                C.3                                        D.4

44.【2021统考真题】使用Dijkstra算法求下图中从顶点1到其余各顶点的最短路径,将当前找到的从顶点1到顶点2,3,4,5的最短路径长度保存在数组dist 中,求出第二条最短路径后,dist中的内容更新为()。

A. 26,3,14,6                  B.25,3,14,6                     C.21,3, 14,6                        D. 15,3,14,6

45.【2022统考真题】下图是一个有10个活动的AOE网,时间余量最大的活动是()。

A.c                                 B.g                                   C. h                                  D. j

46.【2023统考真题】已知无向连通图G中各边的权值均为1。在下列算法中,一定能够求出图G中从某顶点到其余各顶点最短路径的是( )。
ⅠPrim算法        Ⅱ.Kruskal算法        Ⅲ.图的广度优先搜索算法
A.仅I                              B.仅Ⅲ                              C.仅Ⅰ、Ⅱ                        D.Ⅰ、Ⅱ、IⅢ

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/510892.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

食物链(并查集) 维护权值写法,非常详细,适合新手服用

题目描述&#xff1a; 动物王国中有三类动物 A,B,C这三类动物的食物链构成了有趣的环形。 A 吃 B&#xff0c;B 吃 C&#xff0c;C吃 A。 现有 N 个动物&#xff0c;以 1∼N 编号。 每个动物都是 A,B,C 中的一种&#xff0c;但是我们并不知道它到底是哪一种。 有人用两种说法对…

YOLOv8全网独家改进: 小目标 | CAMixing:卷积-注意融合模块和多尺度提取能力 | 2024年4月最新成果

💡💡💡本文独家改进:CAMixingBlock更好的提取全局上下文信息和局部特征,包括两个部分:卷积-注意融合模块和多尺度前馈网络; 💡💡💡红外小目标实现涨点,只有几个像素的小目标识别率提升明显 💡💡💡如何跟YOLOv8结合:1)放在backbone后增强对全局和局部特…

[lesson02]C到C++的升级

C到C的升级 C与C的关系 C继承了所有的C特性C在C的基础上提供了更多的语法和特性C的设计目标是运行效率与开发效率的统一 C到C的升级 C更强调语言的实用性 所有的变量都可以在需要使用时再定义 int c 0; for (int i 1; i < 3; i) {for(int j 1; j < 3; j){c i * …

隐私计算实训营第六讲-隐语PIR介绍及开发实践

隐私计算实训营第六讲-隐语PIR介绍及开发实践 文章目录 隐私计算实训营第六讲-隐语PIR介绍及开发实践1.隐语实现PIR总体介绍1.1按服务器数量分类1.2按查询类型分类 2. Index PIR - SealPIR3. Keyword PIR - Labeled PSI4.隐语PIR功能分层5.隐语PIR后续计划PIR协议开发PIR调用框…

坦白局:PMP真的是智商税吗?

近些年报考PMP认证的学员越来越多&#xff0c;PMP全球持证人数已经突破百万了&#xff0c;据PMI统计&#xff0c;IT行业近50%人士都持有PMP证书&#xff0c;因此也有很多学员在思考&#xff0c;PMP持证人员这么多&#xff0c;PMP是不是都已经烂大街了&#xff1f;证书还有含金量…

【浅尝C++】STL第三弹=>list常用接口使用示例/list底层结构探索/list模拟实现代码详解

&#x1f3e0;专栏介绍&#xff1a;浅尝C专栏是用于记录C语法基础、STL及内存剖析等。 &#x1f3af;每日格言&#xff1a;每日努力一点点&#xff0c;技术变化看得见。 文章目录 list介绍list常用接口使用示例构造类函数迭代器属性与元素获取增删改操作 list底层结构探索list模…

2024年03月CCF-GESP编程能力等级认证Scratch图形化编程一级真题解析

本文收录于专栏《Scratch等级认证CCF-GESP真题解析》,专栏总目录・点这里 一、单选题(每题 3 分,共 30 分) 第1题 小杨的父母最近刚刚给他买了一块华为手表,他说手表上跑的是鸿蒙,这个 鸿蒙是?( )。 A、小程序 B、计时器 C、操作系统 D、神话人物 答案:C 第2题 …

golang语言系列:Web框架+路由 之 Gin

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是golang语言学习系列&#xff0c;本篇对Gin框架的基本使用方法进行学习 1.Gin框架是什么 Gin 是一个 Go (Golang) 编写的轻量级 http web 框架&#xff0c;运行速度非常快&#xff0c;如果你是性能和高效的追求者…

HBase基础必备知识-Day1

HBase 简介 概述 HBase是Yahoo!公司开发的后来贡献给了Apache的一套开源的、分布式的、可扩展的、基于Hadoop的非关系型数据库(Non-Relational Database)&#xff0c;因此HBase并不支持SQL(几乎所有的非关系型数据库都不支持SQL)&#xff0c;而是提供了一套单独的命令和API操…

Redis高可用及持久化

文章目录 一、Redis高可用1、Redis高可用概述2、Redis高可用策略 二、Redis持久化1、Redis持久化的功能2、Redis持久化的两种方式2.1 RDB持久化2.2 AOF持久化&#xff08;append only file&#xff09; 3、RDB持久化3.1 触发条件3.1.1 手动触发3.1.2 自动触发3.1.2.1 配置方式3…

[Linux] 排查问题指令top/ps/netstat

在Linux下查看某个端口运行的指令 1. 首先通过netstat来查看端口对应的进程号 比如抓取端口53这个DNS服务的进程 netstat -tulnp | grep 53 可以看到53这个端口号对应的pid是720 2. 通过ps指令来对进程号执行的命令查询 ps aux | grep 720 可以看到pid为720这个进程对应的执…

聚道云助IT公司破解数据同步难,高效转型新利器!

客户介绍&#xff1a; 该公司是一家在信息技术行业具有丰富经验和良好声誉的公司。作为专业的软件服务提供商&#xff0c;他们致力于为客户提供全方位的解决方案和支持服务。公司秉持合规经营的原则&#xff0c;严格遵守相关法律法规&#xff0c;确保客户的数据安全和合法权益…

HTML基础:脚本 script 标签

你好&#xff0c;我是云桃桃。 1枚程序媛&#xff0c;大专生&#xff0c;2年时间从1800到月入过万&#xff0c;工作5年买房。 分享成长心得。 255篇原创内容-公众号 后台回复“前端工具”可获取开发工具&#xff0c;持续更新中 后台回复“前端基础题”可得到前端基础100题汇…

图卷积神经网络GCN

图卷积神经网络GCN 我们的GCN就是用来解决如何确定a、b、c的

Java毕业设计-基于springboot开发的致远汽车租赁系统平台-毕业论文+答辩PPT(附源代码+演示视频)

文章目录 前言一、毕设成果演示&#xff08;源代码在文末&#xff09;二、毕设摘要展示1、开发说明2、需求分析3、系统功能结构 三、系统实现展示1、系统功能模块2、管理员功能模块3、业务员功能模块3、用户功能模块 四、毕设内容和源代码获取总结 Java毕业设计-基于springboot…

Sora 基础作品之 DiT:Scalable Diffusion Models with Transformer

Paper name Scalable Diffusion Models with Transformers (DiT) Paper Reading Note Paper URL: https://arxiv.org/abs/2212.09748 Project URL: https://www.wpeebles.com/DiT.html Code URL: https://github.com/facebookresearch/DiT TL;DR 2022 年 UC Berkeley 出…

LeetCode 59 螺旋矩阵(模拟)

给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[[1,2,3],[8,9,4],[7,6,5]]示例 2&#xff1a; 输入&#xff1a;n 1 输出&…

模型训练----parser.add_argument添加配置参数

现在需要配置参数来达到修改训练的方式&#xff0c;我现在需要新建一个参数来开关wandb的使用。 首先就是在def parse_option():函数里添加上你要使用的变量名 parser.add_argument("--open_wandb",type bool,defaultFalse,helpopen wandb) 到config文件里增加你的…

2024-04-02 作业

作业要求&#xff1a; 整理思维导图使用模板类&#xff0c;实现顺序栈写一个char类型的字符数组&#xff0c;对该数组访问越界时抛出异常&#xff0c;并做处理。 作业1&#xff1a; 作业2&#xff1a; 运行代码: #include <iostream>using namespace std; #define LEN …

OpenGL_Learn16(模板测试)

模板缓冲首先会被清除为0&#xff0c;之后在模板缓冲中使用1填充了一个空心矩形。场景中的片段将会只在片段的模板值为1的时候会被渲染&#xff08;其它的都被丢弃了&#xff09;。 模板缓冲操作允许我们在渲染片段时将模板缓冲设定为一个特定的值。通过在渲染时修改模板缓冲的…