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

admin2019-12-10 31

问题以下关于图的说法正确的是( )。
Ⅰ  图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在原码、反码和补码机器数形式下()。

以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间，请简要解释之。

由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。

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

下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。

外源性凝血系统的作用起始于

下列哪些体征提示髋关节有屈曲畸形

在判断甲状腺结节良恶性时，下列哪项不恰当

单独或者合计持有公司股份3％以上的股东，可以在股东大会召开()前提出临时提案并书面提交董事会。

旅游经营者准许他人挂靠其名下从事旅游业务，造成旅游者人身损害、财产损失，旅游者请求旅游经营者与挂靠人承担连带责任的，人民法院不予支持。()

比较性组织者

甲是某化学实验室的研究员，现实验室有A、B、C三种浓度分别为60k，、12％、16％的硫酸溶液，甲将B溶液的1/3与A溶液混合，得到8％的硫酸溶液，将剩下的B溶液与C溶液混合，得到13％的硫酸溶液，求原A、C溶液的质量比：

设一棵完全二叉树共有700个结点，则此二叉树中的叶子结点数为()。

Cubesaren’tusuallythego-toshapewhencreatinganobjectthat’smeanttomovearound,but【C1】________inSwitzerlandhavecre

A、Foundajobinabigfirm.B、Triedtogetajob.C、Gambledallthetime.D、Becameamanager.B本题考查考生对信息的掌握。文章中直接提到MatthewHobb

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

计算机408

学硕统考专业

编写判定给定的二叉树是否是二叉排序树的函数。

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

以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间，请简要解释之。

由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。

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

下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。

外源性凝血系统的作用起始于

下列哪些体征提示髋关节有屈曲畸形

在判断甲状腺结节良恶性时，下列哪项不恰当

单独或者合计持有公司股份3％以上的股东，可以在股东大会召开()前提出临时提案并书面提交董事会。

旅游经营者准许他人挂靠其名下从事旅游业务，造成旅游者人身损害、财产损失，旅游者请求旅游经营者与挂靠人承担连带责任的，人民法院不予支持。()

比较性组织者

甲是某化学实验室的研究员，现实验室有A、B、C三种浓度分别为60k，、12％、16％的硫酸溶液，甲将B溶液的1/3与A溶液混合，得到8％的硫酸溶液，将剩下的B溶液与C溶液混合，得到13％的硫酸溶液，求原A、C溶液的质量比：

设一棵完全二叉树共有700个结点，则此二叉树中的叶子结点数为()。

Cubesaren’tusuallythego-toshapewhencreatinganobjectthat’smeanttomovearound,but【C1】________inSwitzerlandhavecre

A、Foundajobinabigfirm.B、Triedtogetajob.C、Gambledallthetime.D、Becameamanager.B本题考查考生对信息的掌握。文章中直接提到MatthewHobb

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