首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I图G的生成树是该图的一个极小连通子图 Ⅱ生成树中最长路径的起点和终点的度均为1 Ⅲ对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
以下关于图的说法正确的是( )。 I图G的生成树是该图的一个极小连通子图 Ⅱ生成树中最长路径的起点和终点的度均为1 Ⅲ对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
admin
2021-08-17
54
问题
以下关于图的说法正确的是( )。
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
学硕统考专业
相关试题推荐
设数组S[n]作为两个栈S1和S2的存储空间,对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是()。
将任意给定的序列1,2,…,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2,…,n)的一个排列p1,p2…pn为这棵树的后根遍历序列。(1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树?如果能够,请简述理由(不要求形式化证
流水计算机中,下列语句发生的数据相关类型是()。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为()。
某请求分页系统的局部页面置换策略如下:系统从0时刻开始扫描,每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计),本轮没有被访问过的页框将被系统回收,并放入到空闲页框链尾,其中内容在下一次被分配之前不被清空。当发生缺页时,如果该页曾被使用过且还在空闲页框链表
下列关于IP路由器功能的描述中,正确的是I.运行路由协议,设置路由表Ⅱ.监测到拥塞时,合理丢弃IP分组Ⅲ.对收到的IP分组头进行差错校验,确保传输的IP分组不丢失Ⅳ.根据收到的IP分组的目的IP地址,将其转发到合适的输出线路上
在物理层接口特性中,用于描述完成每种功能的事件发生顺序的是
设系统缓冲区和用户工作区均果用单缓冲,从外设读人1个数据块到系统缓冲区的时间为100,从系统缓冲区读入1个数据块到用户工作区的时间为5,对用户工作区中的1个数据块进行分析的时间为90(如下图所示)。进程从外设读人并分析2个数据块的最短时间是
某磁盘的转速为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.
最新回复
(
0
)