首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I图G的生成树是该图的一个极小连通子图 Ⅱ生成树中最长路径的起点和终点的度均为1 Ⅲ对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
以下关于图的说法正确的是( )。 I图G的生成树是该图的一个极小连通子图 Ⅱ生成树中最长路径的起点和终点的度均为1 Ⅲ对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
admin
2021-08-17
53
问题
以下关于图的说法正确的是( )。
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
学硕统考专业
相关试题推荐
已知某CPU有16根地址线、8根数据线,并用阼为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所示。试对该机存储
某计算机字长8位,采用补码表示小数。若某数真值为一0.1001,则它在该计算机中的机器数形式为()。
一条双字长的取数指令(LDA)存于存储器的200和201单元,其中第一个字为操作码OP和寻址特征M,第二个字为形式地址A。假设PC当前值为200,变址寄存器IX的内容为100,基址寄存器BR的内容为200,存储器相关单元的内容如下表所示:下表各列分别为
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数;(2)画出散列表;(
以下关于查找方法的说法正确的是()。 Ⅰ顺序查找法只能在顺序存储结构上进行 Ⅱ折半查找法可以在有序的双向链表上进行 Ⅲ分块查找的效率与线性表被分为多少块有关
某计算机的指令系统中共有100条不同的指令,采用微程序控制方式时,控制存储器中具有的微程序数目至少是()。
下列选项中,在I/O总线的数据线上二传输的信息包括I.I/O接口中的命令字Ⅱ.I/O接口中的状态字Ⅲ.中断类型号
下列说法中,正确的是()。Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
网络层有哪些设备?各自的特点有哪些?
关于链表的特点,下面的叙述中不正确的是()。
随机试题
《中国人民政治协商会议共同纲领》规定,中华人民共和国是人民民主专政的人民共和国,它的基础是
用于灭菌检测化学指示剂有指示卡、指示管和指示胶带。正确的是
《建筑工程施工许可管理办法》规定建设资金已经落实是领取施工许可证必须具备的条件。建设工期不足一年的,到位资金原则上不得少于工程合同价的()。
脊柱的四个生理弯曲对维持人体重心稳定和减轻震荡有重要意义,其中前凸的两个弯曲是()。
现在很多地方热衷于为城市“改名”,将城市名字改为本地名胜古迹或名牌产品的名称。近日。以盛产茅台酒而闻名的贵州省仁怀市已向国家有关部门申请改名为“茅台市”。请问你怎么看待城市“改名”这个问题?
你单位正在开展“微笑服务”,有群众到你单位办事,却没有满意而归。群众很气愤,说你们只有微笑.没有服务。你怎么办?
证明不等式:当x∈时,x<tanx.
FoodanddrinkplayamajorroleinChristmascelebrationsinmostcountries,butinfewmoresothaninMexico.Manyfamiliesov
优势
A、Familiesandcommunities.B、Ethnicandculturalgroups.C、Stereotype,prejudiceanddiscrimination.D、Alloftheabove.C事实细节题
最新回复
(
0
)