以下关于图的说法正确的是( )。 Ⅰ 图G的生成树是该图的一个极小连通子图　　Ⅱ 生成树中最长路径的起点和终点的度均为1 　　Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

admin2019-12-10 69

问题以下关于图的说法正确的是( )。
Ⅰ  图G的生成树是该图的一个极小连通子图
　　Ⅱ  生成树中最长路径的起点和终点的度均为1
　　Ⅲ  对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

选项 A、Ⅰ、Ⅱ
B、Ⅱ、Ⅲ
C、Ⅰ、Ⅲ
D、仅有Ⅱ

答案D

解析说法Ⅰ是错误的，图G的生成树是该图的一个极小连通子图，但必须包含全部顶点。说法Ⅱ是正确的，可用反证法证明。设v₁，v₂，…v_k是生成树的一条最长路径，其中，v₁为起点，v_k为终点，若v_k的度为2，取v_k的另一个邻接点v，由于生成树中无回路。所以，v在最长路径上，显然v₁，v₂，…，v_k，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v₁的度不能大于1，只能为1。说法Ⅲ是错误的，只有连通图从某个顶点出发进行一次遍历，可访问图的所有顶点。

转载请注明原文地址:https://www.kaotiyun.com/show/hz3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

以下关于图的说法正确的是( )。 Ⅰ 图G的生成树是该图的一个极小连通子图　　Ⅱ 生成树中最长路径的起点和终点的度均为1 　　Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

计算机408

学硕统考专业

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

给定集合S={0，1，2，3，4)，以及优先关系R={0＜1，1＜4，1＜2，2＜3，2＜4，4＜0)。(1)R是偏序关系吗?(2)证明你的结论。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

用链接方式存储的队列，在进行删除运算时，下面正确的是()。

某二叉树的先序和后序序列正好相反，则该二叉树一定是()。

设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0

人和哺乳动物的心室肌细胞静息电位为

调配散剂时，下列物理性质中哪一条不是特别重要的

任何一个工程项目管理班子除了对工程项目本身的日常活动进行管理外，还必须考虑()。

关于招标人法律责任，下列说法不正确的是(　　)。

当经济处于复苏阶段时，下列说法正确的有()。

在现阶段，我们的工作重心是发展经济，阶级斗争已经不是我国社会的主要矛盾，这意味着公安机关的专政职能可以削弱。()

2006年第一季度我国的GDP约为()。填入画横线部分最恰当的一句是()。

阶级斗争是区分历史唯物主义和历史唯心主义的根本标准。()

编译程序将高级语言程序翻译成与之等价的机器语言程序，该机器语言程序称为()。

•Readthearticlebelowaboutatrainingcompany.•Inmostofthelines34-45,thereisoneextraword.Itiseithergrammatica

以下关于图的说法正确的是( )。 Ⅰ 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

计算机408

学硕统考专业

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

给定集合S={0，1，2，3，4)，以及优先关系R={0＜1，1＜4，1＜2，2＜3，2＜4，4＜0)。(1)R是偏序关系吗?(2)证明你的结论。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

用链接方式存储的队列，在进行删除运算时，下面正确的是()。

某二叉树的先序和后序序列正好相反，则该二叉树一定是()。

设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0

人和哺乳动物的心室肌细胞静息电位为

调配散剂时，下列物理性质中哪一条不是特别重要的

任何一个工程项目管理班子除了对工程项目本身的日常活动进行管理外，还必须考虑()。

关于招标人法律责任，下列说法不正确的是( )。

当经济处于复苏阶段时，下列说法正确的有()。

在现阶段，我们的工作重心是发展经济，阶级斗争已经不是我国社会的主要矛盾，这意味着公安机关的专政职能可以削弱。()

2006年第一季度我国的GDP约为()。填入画横线部分最恰当的一句是()。

阶级斗争是区分历史唯物主义和历史唯心主义的根本标准。()

编译程序将高级语言程序翻译成与之等价的机器语言程序，该机器语言程序称为()。

•Readthearticlebelowaboutatrainingcompany.•Inmostofthelines34-45,thereisoneextraword.Itiseithergrammatica

以下关于图的说法正确的是( )。 Ⅰ 图G的生成树是该图的一个极小连通子图　　Ⅱ 生成树中最长路径的起点和终点的度均为1 　　Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

关于招标人法律责任，下列说法不正确的是(　　)。