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

admin2019-12-10 58

问题以下关于图的说法正确的是( )。
Ⅰ  图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

学硕统考专业

1946年3月5日，英国前首相丘吉尔在富尔敦发表了()，发出第一个明白无误的“冷战”信号。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

下面关于进程的叙述中，正确的是()。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。

急性心肌梗塞时心律失常大多发生于梗死后（）

A、牙槽骨B、牙槽窝C、牙槽嵴D、牙槽间隔E、牙根间隔牙槽窝的游离缘为

下列有关结合通气管的连接与替代的叙述中，不正确的是()。

上述招标的做法违反了《合同法》中的(　　)原则。合同调整的是平等主体之间的(　　)。

2003—2007年间，SCI收录中国科技论文数的年均增长率约为()。

试分析当前我国学校德育存在的问题和改革趋势。

行为人承担刑事责任的哲学根据是

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

计算机408

学硕统考专业

1946年3月5日，英国前首相丘吉尔在富尔敦发表了()，发出第一个明白无误的“冷战”信号。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

下面关于进程的叙述中，正确的是()。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。

急性心肌梗塞时心律失常大多发生于梗死后（）

A、牙槽骨B、牙槽窝C、牙槽嵴D、牙槽间隔E、牙根间隔牙槽窝的游离缘为

下列有关结合通气管的连接与替代的叙述中，不正确的是()。

上述招标的做法违反了《合同法》中的( )原则。合同调整的是平等主体之间的( )。

2003—2007年间，SCI收录中国科技论文数的年均增长率约为()。

试分析当前我国学校德育存在的问题和改革趋势。

行为人承担刑事责任的哲学根据是

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

上述招标的做法违反了《合同法》中的(　　)原则。合同调整的是平等主体之间的(　　)。

　　2003—2007年间，SCI收录中国科技论文数的年均增长率约为()。