首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 Ⅰ 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
以下关于图的说法正确的是( )。 Ⅰ 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
admin
2019-12-10
43
问题
以下关于图的说法正确的是( )。
Ⅰ 图G的生成树是该图的一个极小连通子图
Ⅱ 生成树中最长路径的起点和终点的度均为1
Ⅲ 对任意一个图,从某个顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点
选项
A、Ⅰ、Ⅱ
B、Ⅱ、Ⅲ
C、Ⅰ、Ⅲ
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://jikaoti.com/ti/OeDjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,分别分在卫、鲁、唐、燕的贵族是()
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
通常通信信道的带宽越大,在数据传输中失真将会()。
快速排序最易发挥其长处的情况是()。
下列的网络协议中,()的运输层协议是使用TCP的。
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
已知加权有向图G如下,回答下列问题:(1)画出该有向图G的邻接矩阵;(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间。请
随机试题
涂料具有良好的触变性,有利于方便施工,防止流挂。
关于宫颈上皮内瘤样病变,叙述正确的是
A.2年B.20年C.7年D.6个月中药一级保护品种可申请的保护年限为()
强迫观念是()
班主任要做好个别教育工作,既要发挥________的骨干作用;又要抓好________的转化工作。
保险利益:又称可保利益或者可保权益,指投保人或被保险人对保险标的具有利害关系而享有的合法的、可以用金钱估计的、确定的经济利益。按照保险利益原则,下列哪个当事人的投保行为有效?()
大李和小王是某报新闻部的编辑。该报总编计划从新闻部抽调人员到经济部。总编决定:未经大李和小王本人同意,将不调动两人。大李告诉总编:“我不同意调动,除非我知道小王是否调动。”小王说:“除非我知道大李是否调动,否则我不同意调动。”如果上述三人坚持各自的决定,则
所有国家机关、社会组织和公民个人都必须遵守法律,依法享有和行使法定职权与权利,承担和履行法定职责与义务。这集中体现了
Manycriticsconsiderthatfarmorestressisplacedonachievementsinathleticsthanintheacademicsphere.We’retoldthati
A、Hewaslookingforajob.B、Heseemedtohavemanyneededqualifications.C、Hehandedinhisapplicationearlierthanothers.
最新回复
(
0
)