以下哪些方法可以判断出一个有向图是否有环( )。 Ⅰ．深度优先遍历 Ⅱ．求最短路径 Ⅲ．拓扑排序 Ⅳ．求关键路径

admin2019-05-10 42

问题以下哪些方法可以判断出一个有向图是否有环( )。
Ⅰ．深度优先遍历 Ⅱ．求最短路径 Ⅲ．拓扑排序 Ⅳ．求关键路径

选项 A、仅Ⅰ、Ⅲ
B、仅Ⅰ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅱ、Ⅲ
D、Ⅰ、Ⅱ、Ⅲ和Ⅳ

答案A

解析有两种方法可以判断有向图中是否有回路。用深度优先遍历的方法，如果从有向图上某个顶点v出发的遍历，在dfs(v)结束之前出现一条从顶点j～v的边，由于j在生成树上是v的子孙，则图中必定存在包含v和j的环，因此Ⅰ可以；用拓扑排序的方法，在拓扑排序过程中，每次要删去一个没有前驱的顶点，如果最后图中所有顶点都被删除，则表示没有环，否则有环，因此Ⅲ正确。而最短路径和关键路径(建立在无环的AOE网的基础之上)都是不可以判断的。
补充：还有一个出题点是间接出题，即若一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图一定有什么?想必90％以上的考生都会选择有环，但是没有环这个选项，只有顶点数目大于l的强连通分量这个选项，此时考生必须知道顶点数目大于1的强连通分量就表明有环。

转载请注明原文地址:https://kaotiyun.com/show/I9Ci777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

以下哪些方法可以判断出一个有向图是否有环( )。 Ⅰ．深度优先遍历 Ⅱ．求最短路径 Ⅲ．拓扑排序 Ⅳ．求关键路径

计算机408

学硕统考专业

中华人民共和国恢复在联合国合法席位的时间是()。

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

日本明治政府于1871年推出的改革措施是()。

五四运动爆发后，国内很快出现亲俄“狂飙”和宣传社会主义的浪潮，研究系和国民党人的一些刊物也积极宣传社会主义。引发这一现象的直接原因是()

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

设指令由取指、分析、执行3个子部件完成，每个子部件的工作周期均为△t，采用常规标量流水线处理机。若连续执行12条指令，则共需时间是()。

女，46岁。平素健康，突然发热发冷，咳嗽，用青霉素后热不退，8天后咳大量脓臭痰，诊断可能为()

下列作家，“词开豪放一派”的是()

A．胰液和胆汁分泌都减少B．胰液和胆汁分泌都增加C．胰液和胆汁分泌都不变D．胰分泌不变，胆汁分泌增加E．胰液分泌增加，胆汁分泌不变向狗十二指肠内注入0．5％盐酸

生姜与半夏配伍属于()麻黄与桂枝配伍属于()

全身营养不良时，首先发生萎缩的组织或器官是()。

甲公司生产A、B两种产品，A、B产品为联产品。2017年3月发生加工成本900万元，A产品可变现净值800万元，B产品可变现净值1200万元。甲公司采用可变现净值法分配联合成本，则A产品应当分配的联合成本为()万元。

我国《票据法》规定，汇票的出票人在汇票上记载“不得转让”字样的，该汇票无效。()

近体诗又称“今体诗”，是相对于古体诗而言，它成熟于()。

有效的数学学习活动不能单纯地依赖模仿与记忆，、与__是学生学习数学的重要方式．

以下哪些方法可以判断出一个有向图是否有环( )。 Ⅰ．深度优先遍历 Ⅱ．求最短路径 Ⅲ．拓扑排序 Ⅳ．求关键路径

计算机408

学硕统考专业

中华人民共和国恢复在联合国合法席位的时间是()。

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

日本明治政府于1871年推出的改革措施是()。

五四运动爆发后，国内很快出现亲俄“狂飙”和宣传社会主义的浪潮，研究系和国民党人的一些刊物也积极宣传社会主义。引发这一现象的直接原因是()

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT、服务器上，并且通过NAT服务器连接到Internet上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

设指令由取指、分析、执行3个子部件完成，每个子部件的工作周期均为△t，采用常规标量流水线处理机。若连续执行12条指令，则共需时间是()。

女，46岁。平素健康，突然发热发冷，咳嗽，用青霉素后热不退，8天后咳大量脓臭痰，诊断可能为()

下列作家，“词开豪放一派”的是()

A．胰液和胆汁分泌都减少B．胰液和胆汁分泌都增加C．胰液和胆汁分泌都不变D．胰分泌不变，胆汁分泌增加E．胰液分泌增加，胆汁分泌不变向狗十二指肠内注入0．5％盐酸

生姜与半夏配伍属于()麻黄与桂枝配伍属于()

全身营养不良时，首先发生萎缩的组织或器官是()。

甲公司生产A、B两种产品，A、B产品为联产品。2017年3月发生加工成本900万元，A产品可变现净值800万元，B产品可变现净值1200万元。甲公司采用可变现净值法分配联合成本，则A产品应当分配的联合成本为()万元。

我国《票据法》规定，汇票的出票人在汇票上记载“不得转让”字样的，该汇票无效。()

近体诗又称“今体诗”，是相对于古体诗而言，它成熟于()。

有效的数学学习活动不能单纯地依赖模仿与记忆，______、______与______是学生学习数学的重要方式．

有效的数学学习活动不能单纯地依赖模仿与记忆，、与__是学生学习数学的重要方式．