图的应用解析

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

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

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

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

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

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

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


C

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

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

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

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

14.下列关于拓扑排序的说法中,正确的是().
Ⅰ强连通图不能进行拓扑排序
II.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a, b>|
​​​​​​​A.仅Ⅰ
B.仅Ⅱ
C.Ⅰ和Ⅱ
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/514887.html

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

相关文章

windows@软件显示模糊@屏幕显示器分辨率和精细度

文章目录 refsDPIPPIPPI (Pixels Per Inch)DPI (Dots Per Inch) 屏幕尺寸数windows中DPI设置对单个应用设置DPI兼容性设置使用系统全局设置 获取屏幕(监视器)信息&#x1f47a;获取监视器的型号pnp 监视器windows 获取屏幕分辨率 高分辨率屏幕高分辨率和高精细度屏幕&#x1f4…

基于Python的微博旅游情感分析、微博舆论可视化系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

基于深度学习的吸烟检测系统(网页版+YOLOv8/v7/v6/v5代码+训练数据集)

摘要&#xff1a;本文深入研究了基于YOLOv8/v7/v6/v5等深度学习模型的吸烟行为检测系统&#xff0c;核心采用YOLOv8并整合了YOLOv7、YOLOv6、YOLOv5算法&#xff0c;进行性能指标对比&#xff1b;详述了国内外研究现状、数据集处理、算法原理、模型构建与训练代码&#xff0c;及…

Android配置抓包证书的原理

一、数字证书的常见格式 数字证书有多种格式&#xff0c;其中一些常见的格式包括&#xff1a; X.509证书&#xff1a; X.509是最常见的数字证书标准&#xff0c;它定义了公钥证书的格式和相关的验证流程。X.509证书通常使用DER编码或PEM编码。 DER (Distinguished Encoding …

Linux进程概念(一):冯诺依曼体系结构和操作系统的基本概念

目录 冯诺依曼体系结构 操作系统 理解操作系统的“管理” 操作系统的六层结构 冯诺依曼体系结构 输入设备&#xff1a;键盘、鼠标、摄像头、话筒、磁盘、网卡输出设备&#xff1a;显示器、声卡、磁盘、网卡、显示器等......CPU&#xff1a;运算器、控制器存储器&#xff1a…

js表达式

js 数据&#xff1a; 字面量 1 123 变量 a 表达式 12 2*2 a&&b 表达式都会有一个返回结果。表达式仍然是数据&#xff0c;所有可以写字面量&#xff0c;变量的地方都可以写表达式 在JavaScript中&#xff0c;表达式中的运算符具有不同的优先级&#xff0c;这决定…

C++语言学习(二)——⭐缺省参数、函数重载、引用

1.⭐缺省参数 &#xff08;1&#xff09;缺省参数概念 缺省参数是声明或定义函数时为函数的参数指定一个缺省值。在调用该函数时&#xff0c;如果没有指定实参则采用该形参的缺省值&#xff0c;否则使用指定的实参。 void Func(int a 0) {cout<<a<<endl; } int…

什么是「第一性原理」?

生活中的诸多原则&#xff0c;宛如无形的锁链&#xff0c;束缚着我们的价值观、认知、信仰体系及学习推理的方式。 我们的观点&#xff0c;犹如被锁链牵引的风筝&#xff0c;随风飘摇&#xff0c;却始终无法挣脱这些原则的束缚。 我们的大脑&#xff0c;在思考的瞬间&#xf…

Redis 的主从复制、哨兵

目录 一. Redis 主从复制 1. 介绍 2. 作用 3. 流程 4. 搭建 Redis 主从复制 安装redis 修改 master 的Redis配置文件 修改 slave 的Redis配置文件 验证主从效果 二. Redis 哨兵模式 1. 介绍 2. 原理 3. 哨兵模式的作用 4. 工作流程 4.1 故障转移机制 4.2 主节…

创业成功三要素:定位、追求与舍得

一、引言 在这个充满挑战与机遇的商业世界里&#xff0c;每一位创业者都怀揣着梦想&#xff0c;期望能在商海中开辟一片属于自己的天地。然而&#xff0c;成功的创业并非易事&#xff0c;它需要我们深思熟虑&#xff0c;明确自己的方向&#xff0c;并做出明智的决策。马云&…

学习鸿蒙基础(12)

目录 一、网络json-server配置 &#xff08;1&#xff09;然后输入&#xff1a; &#xff08;2&#xff09;显示下载成功。但是输入json-server -v的时候。报错。 &#xff08;3&#xff09;此时卸载默认的json-server &#xff08;4&#xff09;安装和nodejs匹配版本的js…

加密无忧:SpringBoot中快速搭建安全的API接口

加密无忧&#xff1a;SpringBoot中快速搭建安全的API接口 项目介绍什么是RSA加密加密实战实战准备新建一个springboot项目引入maven依赖启动类Application中添加EnableSecurity注解在application.yml或者application.properties中添加RSA公钥及私钥对Controller 里面的API方法进…

Windows进程监视器Process Monitor

文章目录 Process Monitor操作逻辑 Process Monitor Process Monitor是 Windows 的高级监视工具&#xff0c;是Filemon Regmon的整合增强版本&#xff0c;实时显示文件系统&#xff0c;注册表&#xff0c;网络活动&#xff0c;进程或线程活动&#xff0c;资料收集事件&#x…

上位机图像处理和嵌入式模块部署(qmacvisual并发执行)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 类似于qmacvisual这样的软件&#xff0c;其实价格并不便宜。比如大家熟知的halcon、vision pro、vision master这样的软件&#xff0c;最便宜的版本…

【精品方案】智慧金融大数据分析平台总体架构方案

以下是部分PPT内容&#xff0c;请您参阅。如需下载完整PPTX文件&#xff0c;请前往星球获取&#xff1a; 1.实现数据共享 通过数据平台实现数据集中&#xff0c;确保金融集团各级部门均可在保证数据隐私和安全的前提下使用数据&#xff0c;充分发挥数据作为企业重要资产的业务价…

海外版 双语言爆点游戏 双语音指挥游戏 去中心化投注游戏 双声道音效游戏 附带安装教程

海外版双语言爆点游戏/纯vue源码版/去中心化投注游戏 系统为纯VUE源码&#xff0c;附带安装教程 前端只有一个爆点游戏能玩&#xff0c;去中心化无后台 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/88991298 更多资源下载&#xff1a;关注我。

chromium源码学习-调试日志 LOG

在学习 chromium 源码时&#xff0c;我们经常需要增加调试日志&#xff0c;常见的用法一般是 // TurboNet.mm133134 LOG(INFO) << "TurboNet Engine started.";日志输出效果如下&#xff1a; 其中 INFO 代表当前这条日志的级别&#xff0c;使用的时候就是输…

网易云歌曲评论抓取

网易云歌曲评论爬取 步骤1.找到一首歌曲2.按下F12键打开开发者模式,对其进行抓包3.查找获得评论数据的接口4.对获得评论数据接口进行分析5.构建加密函数方法一方法二运行结果全部代码使用Js文件只使用python新的代码小结与展望这次的任务是获取网易云音乐下面的评论,涉及的知…

AI绘图:Stable Diffusion WEB UI 详细操作介绍:进阶-面部修复和调参

结合两篇文章完成了本地部署和基础操作,现在我们来介绍下进阶内容:面部修复,高清修复和调参区。 一:脸部修复 面部修复的适用在画真人、三次元的场景,特别是在画全身的时候 一般在画全身,由于脸部占比的空间比较小,那么绘制出来的效果就会比较差 1.面部修复 SD 支持…

C++核心编程——4.2(2)对象的初始化和清理

4.2.5 深拷贝与浅拷贝 浅拷贝&#xff1a;编译器提供的简单的赋值拷贝操作 深拷贝&#xff1a;在堆区重新申请空间&#xff0c;进行拷贝操作 示例&#xff1a; class Person { public://无参&#xff08;默认&#xff09;构造函数Person() {cout << "无参构造函数…