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

admin2019-12-10 64

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

学硕统考专业

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：我国银行最早的雏形是唐朝时期出现的()

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

文件系统的主要目的是()。

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。

1937年出版《人格：心理学的解释》一书，标志着用科学方法系统研究人格问题的开始的人是【】

2型糖尿病患者胰岛素分泌缺陷表现为胰岛素的

下列不属环烯醚萜苷的是

借款人的信用承受能力主要内容不包括()。

全国范围内，凡是正式开业的旅游饭店均可申请评定绿色旅游饭店。()

集装箱提单所记载的内容，通常由承运人填写，或由托运人填写，或由承运人或其代理人根据托运人所提供的有关托运文件制成。()

在结案阶段，社会工作者需要做好哪些工作?(　　)

表象，是指事物不在面前时，人们在头脑中出现的关于事物的形象。具有直观性、概括性、可操作性等特点，在形象思维中具有重要作用。根据该定义，下列属于表象的是()。

甲、乙、丙共同购置一套房屋，三人约定对房屋按照出资比例分享房屋产权，但对因管理房屋产生的修缮费用没有约定承担份额。该房屋由丁完成修缮，丁对房屋共有产权的性质并不知情。则()。

A—Above-the-lineadvertisingJ—MailorderadvertisingB—LightboxadvertisingK—BrandloyaltyC—Neo

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

计算机408

学硕统考专业

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：我国银行最早的雏形是唐朝时期出现的()

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

文件系统的主要目的是()。

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。

1937年出版《人格：心理学的解释》一书，标志着用科学方法系统研究人格问题的开始的人是【】

2型糖尿病患者胰岛素分泌缺陷表现为胰岛素的

下列不属环烯醚萜苷的是

借款人的信用承受能力主要内容不包括()。

全国范围内，凡是正式开业的旅游饭店均可申请评定绿色旅游饭店。()

集装箱提单所记载的内容，通常由承运人填写，或由托运人填写，或由承运人或其代理人根据托运人所提供的有关托运文件制成。()

在结案阶段，社会工作者需要做好哪些工作?( )

表象，是指事物不在面前时，人们在头脑中出现的关于事物的形象。具有直观性、概括性、可操作性等特点，在形象思维中具有重要作用。根据该定义，下列属于表象的是()。

甲、乙、丙共同购置一套房屋，三人约定对房屋按照出资比例分享房屋产权，但对因管理房屋产生的修缮费用没有约定承担份额。该房屋由丁完成修缮，丁对房屋共有产权的性质并不知情。则()。

A—Above-the-lineadvertisingJ—MailorderadvertisingB—LightboxadvertisingK—BrandloyaltyC—Neo

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

在结案阶段，社会工作者需要做好哪些工作?(　　)