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

admin2021-08-17 57

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

选项 A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅱ
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/CX3i777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

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

在单发射、按序流动的普通流水线中，可能出现下列哪种数据相关问题?()。

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

图2-2所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout)控制命令，但图中未标出。(

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。若题47一a表中的某个IP分组在S发出时

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。根据题47一a表中的IP分组，分析s已经

CPU的CPI与下列哪个因素有关?()Ⅰ．时钟频率Ⅱ．系统结构Ⅲ．指令集

下列关于无向图的说法中，正确的是()。Ⅰ．无向图中某个顶点的度是指图中与该顶点连通的顶点数Ⅱ．在一个具有n个顶点的无向图中，要连通全部顶点至少需要n一1条边Ⅲ．无向图的邻接矩阵是对称矩阵Ⅳ．具有n个顶点的无向

Youhavebeenbadlyinjuredinacaraccident.Itisnecessarytogiveyouabloodtransfusionbecauseyoulostagreatdealof

尿素呼气试验是基于下述原理的

固摄受纳清气的脏器是

行政强制实施机关进行行政强制的实施应当遵循行政强制适当原则，这种要求体现在()。

新时期大力弘扬爱国主义精神，必须把坚持爱国主义与拥护社会主义制度有机统一起来，坚定不移地维护社会主义制度。()

【新柏拉图主义】(Neo-Platonism)

下面关于类、对象、属性和方法的叙述中，错误的是(　　)。

数据的逻辑结构有线性结构和【】两大类。

Relentlessrainstriggeredheavyfloodinginnineprovinces,where68personswerekilled.Thegovernmentpledgedrelieffundsof

A、Becauseheloveseatingcucumbers.B、Becausehehateseatingcucumbers.C、Becausehedoesn’tbelievefishhavefeelings.D、Bec

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

计算机408

学硕统考专业

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

在单发射、按序流动的普通流水线中，可能出现下列哪种数据相关问题?()。

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

图2-2所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout)控制命令，但图中未标出。(

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。若题47一a表中的某个IP分组在S发出时

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。根据题47一a表中的IP分组，分析s已经

CPU的CPI与下列哪个因素有关?()Ⅰ．时钟频率Ⅱ．系统结构Ⅲ．指令集

Youhavebeenbadlyinjuredinacaraccident.Itisnecessarytogiveyouabloodtransfusionbecauseyoulostagreatdealof

尿素呼气试验是基于下述原理的

固摄受纳清气的脏器是

行政强制实施机关进行行政强制的实施应当遵循行政强制适当原则，这种要求体现在()。

新时期大力弘扬爱国主义精神，必须把坚持爱国主义与拥护社会主义制度有机统一起来，坚定不移地维护社会主义制度。()

【新柏拉图主义】(Neo-Platonism)

下面关于类、对象、属性和方法的叙述中，错误的是( )。

数据的逻辑结构有线性结构和【】两大类。

Relentlessrainstriggeredheavyfloodinginnineprovinces,where68personswerekilled.Thegovernmentpledgedrelieffundsof

A、Becauseheloveseatingcucumbers.B、Becausehehateseatingcucumbers.C、Becausehedoesn’tbelievefishhavefeelings.D、Bec

下面关于类、对象、属性和方法的叙述中，错误的是(　　)。