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

admin2019-12-10 52

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

学硕统考专业

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

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

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

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

在操作系统的以下功能中，不需要硬件支持的是()。

在TCP／IP模型中，主机采用()标识，运行在主机上的应用程序采用()标识。

Cushing综合征的临床表现不包括

化疗病人考虑停药的白细胞计数为

外科感染的局部治疗方法中错误的是

亚急性感染性心内膜炎青年人常发生于

证券的特点表现在()。

防护重要生境及野生生物可能受工程影响的措施，按优先次序选择，应遵循()的原则顺序。

成本与可变现净值孰低法中的“可变现净值”是指()。

歌德痛苦时创作《少年维特之烦恼》，这属于()防御机制。

Apowerfulpersonalgrowthtoolisthe30-daytrial.ThisisaconceptIborrowedfromthesharewareindustry,whereyoucan【W1】

WhatkindofprogramisDoctorLevydescribing?

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

计算机408

学硕统考专业

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

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

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

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

在操作系统的以下功能中，不需要硬件支持的是()。

在TCP／IP模型中，主机采用()标识，运行在主机上的应用程序采用()标识。

Cushing综合征的临床表现不包括

化疗病人考虑停药的白细胞计数为

外科感染的局部治疗方法中错误的是

亚急性感染性心内膜炎青年人常发生于

证券的特点表现在()。

防护重要生境及野生生物可能受工程影响的措施，按优先次序选择，应遵循()的原则顺序。

成本与可变现净值孰低法中的“可变现净值”是指()。

歌德痛苦时创作《少年维特之烦恼》，这属于()防御机制。

Apowerfulpersonalgrowthtoolisthe30-daytrial.ThisisaconceptIborrowedfromthesharewareindustry,whereyoucan【W1】

WhatkindofprogramisDoctorLevydescribing?

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