下列算法中,()算法用来求图中某顶点到其他顶点所有顶点之间的最短路径。A.DijkstraB.FloyedC.Prim
下列算法中,()算法用来求图中某顶点到其他顶点所有顶点之间的最短路径。
A.Dijkstra
B.Floyed
C.Prim
D.Kruskal
下列算法中,()算法用来求图中某顶点到其他顶点所有顶点之间的最短路径。
A.Dijkstra
B.Floyed
C.Prim
D.Kruskal
下面是求无向连通图的最小生成树的一种算法:
//设图中总顶点数为n,总边数为m
将图中所有的边按其权值从大到小排序为;
若图不再连通,则恢复e1;(m=m+1);I=i+1;
(1)试间这个算法是否正确,并说明原因。
(2)以图8-44所示的图为例,写出执行以上算法的过程。
点到某一指定顶点v的最短路径,例如,对于图8-47(a)所示的带权有向图,用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.
关于最短路径的读法以顶点0为例,在从顶点0到顶点2的最短路径上,顶点0的后继为顶点1(即path[0]=1),顶点1的后继为顶点3(即path[1]=3),顶点3的后继顶点为2(即path[3]=2).
编写一个算法,求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char,边上权值的数据类型为float。
若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。
(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥,将把图分割成两个连通分量。
(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法,判断连通图G中是否有桥,若有。输出这样的桥。
● 求单源点最短路径的迪杰斯特拉(Dijkstra )算法是按(57) 的顺序求源点到各 顶点的最短路径的。
(57)A. 路径长度递减 B. 路径长度递增
C. 顶点编号递减 D. 顶点编号递增
某虚拟存储系统采用最近最少使用(LRU)页面淘汰算法。假定系统为每个作业分配3个页面的主存空间,其中一个页面用来存放程序。现有某作业的部分语句如下:
Var A:Array [1..128,1..128] OF integer;
i,j:integer;
FOR i:=1 to 128 DO
FOR j:=1 to 128 DO
A[i,j]:=0;
设每个页面可存放128个整数变量,变量i,j放在程序页中,矩阵A按行序存放。初始时,程序及变量i、j已在内存,其余两页为空。在上述程序片段执行过程中,共产生(27)次缺页中断。最后留在内存中的是矩阵A的最后(28)。
A.64
B.128
C.256
D.512
某虚拟存储系统采用最近最少使用(LRU)页面淘汰算法,假定系统为每个作业分配3个页面的主存空间,其中一个页面用来存放程序。现有某作业的部分语句如下:
Var A:Array[1..150,1..100]OF integer;
i,j:integer;
FOR i:=1 to 150 DO
FOR j:=1 to 100 DO
A[i,j]:=0;
设每个页面可存放150个整数变量,变量i、j放在程序页中。初始时,程序及变量i、j已在内存,其余两页为空,矩阵A按行序存放。在上述程序片段执行过程中,共产生(16)次缺页中断。最后留在内存中的是矩阵A的最后(17)。
A.50
B.100
C.150
D.300
一次。
(l)试证明一个有向图存在欧拉回路的充要条件是该图必须是强连通的且每一个顶点有相同的人度与出度;
(2)设图中的顶点数为n,试描述有向图的数据结构并编写一个时间复杂性为O(n)的算法,在有向图中查找一条欧拉回路(如果它存在).
A.源节点到目的节点的最短距离
B. 源节点到目的节点的路径
C. 本节点到目的节点的输出节点(下一节点)地址
D. 本节点到目的节点的路径