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

admin2019-12-10 54

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

关于德国工业革命，说法不正确的是()。

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。

虚拟存储器技术是基于程序的()特性。

已知在二叉树中，T为根结点，p和q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

单处理机系统中，可并行的是()。I进程与进程Ⅱ处理机与设备Ⅲ处理机与通道Ⅳ设备与设备

伤亡事故的处理，法律要求应当结束的期限是（）

肝性脑病前驱期时的临床表现有

A．合成tRNAB．合成rRNAC．合成mRNAD．合成cDNA真核RNA聚合酶Ⅱ

胃、十二指肠溃疡发生形成和发展过程中，肯定无疑的一点是

教师成长公式是，是由提出的。

论述建构主义学习理论对学习实质的认识与认知主义的不同之处。

下图阴影部分对应的逻辑表达式为(57)。

已知一程序运行后执行的第一个输出操作是()。cout

A、 B、 C、 A原句说的是“汤姆在火车站送他的朋友”(seehisfriendoff)。图片[A]画的是火车站，而图片[B]画的是公共汽车站，图片[C]画的是飞机场，只有[A]符合题意，所以应该选[A]。

WhichisthemostimportantairportinBritain?

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

计算机408

学硕统考专业

关于德国工业革命，说法不正确的是()。

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。

虚拟存储器技术是基于程序的()特性。

已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

单处理机系统中，可并行的是()。I进程与进程Ⅱ处理机与设备Ⅲ处理机与通道Ⅳ设备与设备

伤亡事故的处理，法律要求应当结束的期限是（）

肝性脑病前驱期时的临床表现有

A．合成tRNAB．合成rRNAC．合成mRNAD．合成cDNA真核RNA聚合酶Ⅱ

胃、十二指肠溃疡发生形成和发展过程中，肯定无疑的一点是

教师成长公式是________，是由________提出的。

论述建构主义学习理论对学习实质的认识与认知主义的不同之处。

下图阴影部分对应的逻辑表达式为(57)。

已知一程序运行后执行的第一个输出操作是()。cout

A、 B、 C、 A原句说的是“汤姆在火车站送他的朋友”(seehisfriendoff)。图片[A]画的是火车站，而图片[B]画的是公共汽车站，图片[C]画的是飞机场，只有[A]符合题意，所以应该选[A]。

WhichisthemostimportantairportinBritain?

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

已知在二叉树中，T为根结点，p和q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

教师成长公式是，是由提出的。