首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I图G的生成树是该图的一个极小连通子图 Ⅱ生成树中最长路径的起点和终点的度均为1 Ⅲ对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
以下关于图的说法正确的是( )。 I图G的生成树是该图的一个极小连通子图 Ⅱ生成树中最长路径的起点和终点的度均为1 Ⅲ对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
admin
2021-08-17
57
问题
以下关于图的说法正确的是( )。
I图G的生成树是该图的一个极小连通子图
Ⅱ生成树中最长路径的起点和终点的度均为1
Ⅲ对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
选项
A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅱ
D、仅有Ⅱ
答案
D
解析
说法工是错误的,图G的生成树是该图的一个极小连通子图,但必须包含全部顶点。
说法Ⅱ是正确的,可用反证法证明。设v
1
,v
2
,…,v
k
是生成树的一条最长路径,其中,v
1
为起点,v
k
为终点,若v
k
的度为2,取v
k
的另一个邻接点v,由于生成树中无回路。所以,v在最长路径上,显然v
1
,v
2
,…,v
k
,v的路径最长,与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v
1
的度不能大于1,只能为1。
说法Ⅲ是错误的,只有连通图从某个顶点出发进行一次遍历,可访问图的所有顶点。
转载请注明原文地址:https://kaotiyun.com/show/CX3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面关于进程的叙述中,正确的是()。
在单发射、按序流动的普通流水线中,可能出现下列哪种数据相关问题?()。
假设二叉树采用二叉链表存储结构存储,试设计一个算法,求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
设某计算机有变址寻址、间接寻址和相对寻址等寻址方式,设当前指令的地址码部分为001AH,正在执行的指令所在地址为1F05H,变址寄存器中的内容为23A0H。(1)当执行取数指令时,如为变址寻址方式,则取出的数为多少?(2)如为间接寻
图2-2所示的CPU逻辑框图中,有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位),数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout)控制命令,但图中未标出。(
设有一个带头结点的循环单链表,其结点值均为正整数。试设计一个算法,反复找出单链表中结点值最小的结点,并输出之,然后将该结点从中删除,直到单链表空为止,最后再删除表头结点。(1)给出算法的基本设计思想;(2)根据设计思想,采用C或C++或JAVA语言表述
主机H通过快速以太网连接Internet,IP地址为192.168.0.8,服务器S的lP地址为211.68.71.80。H与S使用TCP通信时,在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。若题47一a表中的某个IP分组在S发出时
主机H通过快速以太网连接Internet,IP地址为192.168.0.8,服务器S的lP地址为211.68.71.80。H与S使用TCP通信时,在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。根据题47一a表中的IP分组,分析s已经
CPU的CPI与下列哪个因素有关?()Ⅰ.时钟频率Ⅱ.系统结构Ⅲ.指令集
下列关于无向图的说法中,正确的是()。Ⅰ.无向图中某个顶点的度是指图中与该顶点连通的顶点数Ⅱ.在一个具有n个顶点的无向图中,要连通全部顶点至少需要n一1条边Ⅲ.无向图的邻接矩阵是对称矩阵Ⅳ.具有n个顶点的无向
随机试题
Youhavebeenbadlyinjuredinacaraccident.Itisnecessarytogiveyouabloodtransfusionbecauseyoulostagreatdealof
尿素呼气试验是基于下述原理的
固摄受纳清气的脏器是
行政强制实施机关进行行政强制的实施应当遵循行政强制适当原则,这种要求体现在()。
新时期大力弘扬爱国主义精神,必须把坚持爱国主义与拥护社会主义制度有机统一起来,坚定不移地维护社会主义制度。()
【新柏拉图主义】(Neo-Platonism)
下面关于类、对象、属性和方法的叙述中,错误的是( )。
数据的逻辑结构有线性结构和【】两大类。
Relentlessrainstriggeredheavyfloodinginnineprovinces,where68personswerekilled.Thegovernmentpledgedrelieffundsof
A、Becauseheloveseatingcucumbers.B、Becausehehateseatingcucumbers.C、Becausehedoesn’tbelievefishhavefeelings.D、Bec
最新回复
(
0
)