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

admin2019-12-10 90

问题以下关于图的说法正确的是( )。
Ⅰ  图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://kaotiyun.com/show/hz3i777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

真值0在原码、反码和补码机器数形式下()。

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

高度为7的AVL树最少有()个结点。

在机器数中，正数的符号位用“1”表示的是()。

计算机系统中存储器为何采用分级结构?

在AOE网络中关键路径叙述正确的是()。

支持多道程序设计的操作系统在运行过程中，不断会选择新进程来运行，共享CPU资源，但是，下面哪个不是操作系统选择新进程的直接原因()。

设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。

行甲状腺手术时应防止损伤的主要结构有()

被改编为戏剧的同名小说《茶花女》是______的代表作。()

()是指先统一征税，然后再将税收收入的总额按照一定比例在中央与地方政府之间加以分割。

如果同事W多次对你说“Q在背地里经常说你的坏话”，你的反应是()。

简述亲子关系的类型。

世界历史上第一部资产阶级成文宪法是()。

在中断处理中，输入输出中断是指

若服务器系统可用性达到99,99％，那么每年的停机时间必须小于

假设某台计算机的内存容量为256MB，硬盘容量为40GB。硬盘容量是内存容量的

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

计算机408

学硕统考专业

真值0在原码、反码和补码机器数形式下()。

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

高度为7的AVL树最少有()个结点。

在机器数中，正数的符号位用“1”表示的是()。

计算机系统中存储器为何采用分级结构?

在AOE网络中关键路径叙述正确的是()。

支持多道程序设计的操作系统在运行过程中，不断会选择新进程来运行，共享CPU资源，但是，下面哪个不是操作系统选择新进程的直接原因()。

设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。

行甲状腺手术时应防止损伤的主要结构有()

被改编为戏剧的同名小说《茶花女》是______的代表作。()

()是指先统一征税，然后再将税收收入的总额按照一定比例在中央与地方政府之间加以分割。

如果同事W多次对你说“Q在背地里经常说你的坏话”，你的反应是()。

简述亲子关系的类型。

世界历史上第一部资产阶级成文宪法是()。

在中断处理中，输入输出中断是指

若服务器系统可用性达到99,99％，那么每年的停机时间必须小于

假设某台计算机的内存容量为256MB，硬盘容量为40GB。硬盘容量是内存容量的

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