对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一

题目

对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一的。

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

拓扑排序的主要步骤有()

A、在AOV网中,选一个没有后继的节点,并输出

B、在网中删去该顶点,并删去所有指向该顶点的弧

C、重复上述两步,直到网中不再有出度为0的顶点为止

D、删除网中的回路


参考答案:ABC

第2题:

任何有向图的顶点都可以排成拓扑有序序列,而且拓扑序列不唯一。()

此题为判断题(对,错)。


参考答案:错误

第3题:

网络拓扑是通过网中结点与通信线路之间的______关系表示网络结构的。


正确答案:几何
几何 解析:计算机网络拓扑是通过网络中结点与通信线路之间的几何关系表示网络结构,从而反映出网络各实体间的结构关系。

第4题:

拓扑排序的图中______表示活动。

A.顶点

B.边

C.图

D.边或顶点


正确答案:A
解析:在有向图中,若以顶点表示活动,用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网(Active On Vertex network),简称AOV网。拓扑排序就是将AOV网中所有顶点排成的一个线性序列。

第5题:

阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的语句填写完整。

[说明]

函数int Toplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中,图G表示一个具有n个顶点的AOE-网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下。

例如,某AOE-网如图6-22所示,其邻接表存储结构如图6-23所示。

[函数]


正确答案:是一道要求读者掌握数据结构中拓扑排序和求关键路径问题的算法分析及设计题。本题的解答思路如下。 AOE网(Activity On Edge network边表示活动的网)是一个带权的有向无环图其中顶点表示事件弧表示活动权表示活动持续的时间。通常AOE网可以用来估算工程的完成时间。 在AOE网中入度为0的顶点为源点出度为0的顶点为汇点。由于有些活动可以并行地执行因此从源点到汇点的路径中长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点Vn表示汇点则汇点的最早发生时间和最晚发生时间是一致的并且等于关键路径的长度。 设顶点Vj的最早发生时间用ve(j)表示则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。 ve(j)计算方法为 其中T是所有到达顶点j的弧的集合;dut(Ij>)是弧Ij>上的权值;n是网中的顶点数(即汇点的序号)。 显然上式是一个从源点开始的递推公式。Ve(j)的计算必须在Vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对AOE网进行拓扑排序然后按拓扑有序序列逐个求出各顶点事件的最早发生时间。 拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程并且该序列满足:若在有向图中从顶点Vi到Vj有一条路径则在该线性序列中顶点Vi必然在顶点Vj之前。可见拓扑排序序列是由有向图中的所有顶点构成的一个线性序列在这个序列中体现了所有顶点之间的优先关系。 对AOE网进行拓扑排序的步骤如下: ①首先在AOE网中选择一个入度为0(没有前驱)的顶点且输出它。 ②然后从网中删除该顶点并且删除以该顶点为始点的所有引出边。 ③重复上述两个步骤直至网中不存在入度为0的顶点为止。 在拓扑排序过程中有可能同时存在多个入度为0的顶点函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。 本试题所给出的算法首先申请了3块连续的地址空间分别用来存放关键路径长度、网中各顶点的入度及入度为0的顶点编号它们的首地址分别存放在指针变量Ve、indegree、Stack中。 算法主体是由3个for循环和3个while循环组成。第1个for循环即for(j=1;j=G.n;j++){ve[j]=0; indegree[j]=O;}主要完成数组初始化的功能。 进行拓扑排序之前应先求出网中每个顶点的入度并存入数组indegree[]中从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”一旦发现某个顶点的入度变为0就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。 题目中顶点从1开始编号顶点Vi的编号为i第2个for循环代码主要完成求网中各个顶点的入度的功能。 在有向图中若以V2为尾的弧有V2V4>且权值为30、V2V6>且权值为50则其的邻接表表示形式是:V2→430→650^。 因此扫描顶点V2的邻接表可以将邻接于V2的所有顶点的入度加1即(1)空缺处应填入“indegree[p ->adjvex)++”或其等价形式。 第3个for循环语句主要完成求网中入度为0的顶点并保存其编号的功能。以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。 由于入度为0的顶点由栈中弹出根据变量w在后续代码中所起的作用——存放网中没有直接前驱的顶点并通过printf语句输出可知(2)空缺处应填入“Stack[top--]”或其等价形式。 然后在网中删除没有直接前驱的顶点和以该顶点为始点的所有引出边并通过内嵌的while循环语句把这些引出边对应的终点的入度减1即将邻接到顶点w的各个顶点(p->adjvex)的入度减1再判断它们是否也是入度为0的顶点。因此(3)空缺处应填入“indegree[p->adjvex]——”或其等价形式。 同时对于顶点p->adjveX而言当删除其所有引入边之后从源点出发到达它的最长路径长度也就计算出来了所以每删除一条到达顶点p->adjvex的引入边都要查看一下最长路径长度是否需要更新。因此(4)空缺处填入“ve[w]+p->weight>ve[p->adjvex]”或其等价形式。 算法程序的最后部分通过return语句返回该图的关键路径长度即汇点的最早发生时间(该AOE网的关键路径长度)。由于AOE网中汇点未必是编号最大的顶点但它必然是从栈中弹出的最后一个顶点因此(5)空缺处填入“ve[w]”或其等价形式。
是一道要求读者掌握数据结构中拓扑排序和求关键路径问题的算法分析及设计题。本题的解答思路如下。 AOE网(Activity On Edge network,边表示活动的网)是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续的时间。通常,AOE网可以用来估算工程的完成时间。 在AOE网中,入度为0的顶点为源点,出度为0的顶点为汇点。由于有些活动可以并行地执行,因此从源点到汇点的路径中,长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点Vn表示汇点,则汇点的最早发生时间和最晚发生时间是一致的,并且等于关键路径的长度。 设顶点Vj的最早发生时间用ve(j)表示,则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。 ve(j)计算方法为 其中,T是所有到达顶点j的弧的集合;dut(I,j>)是弧I,j>上的权值;n是网中的顶点数(即汇点的序号)。 显然,上式是一个从源点开始的递推公式。Ve(j)的计算必须在Vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对AOE网进行拓扑排序,然后按拓扑有序序列逐个求出各顶点事件的最早发生时间。 拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程,并且该序列满足:若在有向图中从顶点Vi到Vj有一条路径,则在该线性序列中,顶点Vi必然在顶点Vj之前。可见,拓扑排序序列是由有向图中的所有顶点构成的一个线性序列,在这个序列中体现了所有顶点之间的优先关系。 对AOE网进行拓扑排序的步骤如下: ①首先在AOE网中选择一个入度为0(没有前驱)的顶点且输出它。 ②然后从网中删除该顶点,并且删除以该顶点为始点的所有引出边。 ③重复上述两个步骤,直至网中不存在入度为0的顶点为止。 在拓扑排序过程中,有可能同时存在多个入度为0的顶点,函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。 本试题所给出的算法首先申请了3块连续的地址空间,分别用来存放关键路径长度、网中各顶点的入度及入度为0的顶点编号,它们的首地址分别存放在指针变量Ve、indegree、Stack中。 算法主体是由3个for循环和3个while循环组成。第1个for循环,即for(j=1;j=G.n;j++){ve[j]=0; indegree[j]=O;},主要完成数组初始化的功能。 进行拓扑排序之前,应先求出网中每个顶点的入度并存入数组indegree[]中,从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”,一旦发现某个顶点的入度变为0,就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。 题目中顶点从1开始编号,顶点Vi的编号为i,第2个for循环代码主要完成求网中各个顶点的入度的功能。 在有向图中,若以V2为尾的弧有V2,V4>且权值为30、V2,V6>且权值为50,则其的邻接表表示形式是:V2→4,30→6,50^。 因此,扫描顶点V2的邻接表可以将邻接于V2的所有顶点的入度加1,即(1)空缺处应填入“indegree[p ->adjvex)++”或其等价形式。 第3个for循环语句主要完成求网中入度为0的顶点并保存其编号的功能。以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。 由于入度为0的顶点由栈中弹出,根据变量w在后续代码中所起的作用——存放网中没有直接前驱的顶点,并通过printf语句输出,可知(2)空缺处应填入“Stack[top--]”或其等价形式。 然后,在网中删除没有直接前驱的顶点和以该顶点为始点的所有引出边,并通过内嵌的while循环语句把这些引出边对应的终点的入度减1,即将邻接到顶点w的各个顶点(p->adjvex)的入度减1,再判断它们是否也是入度为0的顶点。因此(3)空缺处应填入“indegree[p->adjvex]——”或其等价形式。 同时,对于顶点p->adjveX而言,当删除其所有引入边之后,从源点出发到达它的最长路径长度也就计算出来了,所以每删除一条到达顶点p->adjvex的引入边,都要查看一下最长路径长度是否需要更新。因此,(4)空缺处填入“ve[w]+p->weight>ve[p->adjvex]”或其等价形式。 算法程序的最后部分,通过return语句返回该图的关键路径长度,即汇点的最早发生时间(该AOE网的关键路径长度)。由于AOE网中汇点未必是编号最大的顶点,但它必然是从栈中弹出的最后一个顶点,因此(5)空缺处填入“ve[w]”或其等价形式。

第6题:

任何AOV网的拓扑序列都是唯一的()

此题为判断题(对,错)。


参考答案:错

第7题:

网络拓扑是通过网中结点与通信线路之间的______关系表示网络结构。


正确答案:几何关系
几何关系 解析:计算机网络拓扑是通过网中结点与通信线路之间的几何关系表示网络结构,反映出网络务实体间的结构关系。

第8题:

目前实际存在与使用的广域网,采取的网络拓扑结构基本上都是()。

A、网状拓扑结构

B、环形拓扑结构

C、总线拓扑结构

D、星型拓扑结构


参考答案:A

第9题:

在局域网的主要拓扑构型中,任二结点出现故障都会严重影响整个网络的是( )


正确答案:D
在环型拓扑构型中,结点通过网卡,利用点到点线路连接构成闭合的环型。环中数据沿着一个方向绕环逐站传输,环中任何一个结点或线路出现故障,都会造成网络瘫痪。

第10题:

在由许多项目组成的大型工程中,用顶点表示项目,有向边表示项目之间谁先开工的先后关系,这种用顶点表示活动的图称为AOV网络,其常用的一种存储结构是(40)。为规划整个工程的实现,通常要对上述图的顶点进行(41)排序,据此可获得项目的(42)序列。

A.队列表

B.连通表

C.邻接表

D.路径表


正确答案:C

更多相关问题