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

admin2021-08-17 54

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

学硕统考专业

设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是()。

流水计算机中，下列语句发生的数据相关类型是()。ADDR1，R2，R3；(R2)+(R3)→R1ADDR4，R1，R5；(R1)+(R5)→R4

将一个A[1．．100，1．．100]的三对角矩阵，按行优先存入-维数组B[1．．298]中，A中元素A66,65(即该元素下标i=66，j=65)，在B数组中的位置k为()。

在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为

假定磁盘传输数据以32bit的字为单位，传输速率为1MB／s。CPU的时钟频率为50MHz。用中断方式进行控制，每次传输的开销(包括中断处理)为100个时钟周期。求CPU为传输磁盘数据花费的时间比率。

志愿者参加社会服务的动机有所不同，下面哪项是以自我为中心的动机?()

子宫颈癌的不典型增生

"Igotcancerinmyprostrate."DetectiveAndySipowiczofthefictional15’Precinct,astoic,bigbearofaman,isclearlyi

表1中pH平均值计算有误，请予以更正。根据素材中提供的数据计算监测期间污水处理厂的生产负荷，并说明此负荷是否符合要求。

________应当按照一般进口货物的报关程序报关。

基金管理公司的设立须经(　　)批准。

小学生在日常生活中已经能分辨你我他、上下左右等概念，这些概念一般是通过()获得的。

下列选项中，属于职权性行政主体的是()。

2012年，三沙市伴随海南省西沙群岛、南沙群岛、中沙群岛办事处撤销而设立。根据我国现行相关法律，三沙市的设立必须由（）批准。

Bob:DoyoumindffIplaysomemusic?Lily:________.I’mwritingmyassignment.

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

计算机408

学硕统考专业

设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是()。

流水计算机中，下列语句发生的数据相关类型是()。ADDR1，R2，R3；(R2)+(R3)→R1ADDR4，R1，R5；(R1)+(R5)→R4

将一个A[1．．100，1．．100]的三对角矩阵，按行优先存入-维数组B[1．．298]中，A中元素A66,65(即该元素下标i=66，j=65)，在B数组中的位置k为()。

在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是

某磁盘的转速为10000转／分，平均寻道时间是6ms，磁盘传输速率是20MB／s，磁盘控制器延迟为0．2ms，渎取一个4KB的扇区所需的平均时间约为

假定磁盘传输数据以32bit的字为单位，传输速率为1MB／s。CPU的时钟频率为50MHz。用中断方式进行控制，每次传输的开销(包括中断处理)为100个时钟周期。求CPU为传输磁盘数据花费的时间比率。

志愿者参加社会服务的动机有所不同，下面哪项是以自我为中心的动机?()

子宫颈癌的不典型增生

"Igotcancerinmyprostrate."DetectiveAndySipowiczofthefictional15’Precinct,astoic,bigbearofaman,isclearlyi

表1中pH平均值计算有误，请予以更正。根据素材中提供的数据计算监测期间污水处理厂的生产负荷，并说明此负荷是否符合要求。

________应当按照一般进口货物的报关程序报关。

基金管理公司的设立须经( )批准。

小学生在日常生活中已经能分辨你我他、上下左右等概念，这些概念一般是通过()获得的。

下列选项中，属于职权性行政主体的是()。

2012年，三沙市伴随海南省西沙群岛、南沙群岛、中沙群岛办事处撤销而设立。根据我国现行相关法律，三沙市的设立必须由（）批准。

Bob:DoyoumindffIplaysomemusic?Lily:________.I’mwritingmyassignment.

基金管理公司的设立须经(　　)批准。