GESP-C++八级 题库
共 5 道题
· 按题型筛选,点「查看答案」核对解析
1
单选题
适中
下面是使用邻接矩阵实现的Dijkstra算法的核心片段,用于求单源最短路径。在找到当前距离起点最近的顶点u 后,需要更新其邻接点 j 的距离。横线处应填入的代码是( )。
A
dis[j] < dis[u] + graph[u][j]
B
dis[j] > dis[u] + graph[u][j]
C
graph[u][j] > dis[u] + dis[j]
D
dis[j] > graph[u][j]
答案与解析
正确答案:B
在Dijkstra算法中,选定当前距离起点最近的未处理顶点u后,需遍历其所有邻接点j。对于每个邻接点j,若存在从u到j的边且通过u到达j的路径长度小于当前记录的最短距离,则更新j的最短距离。该判断条件基于比较经由u到达j的路径长度与原记录距离的大小关系,仅当新路径更短时执行更新操作。
2
单选题
适中
下面Floyd算法中,横线处应该填入的是?( )
A
map[i][j] = map[i][k] + map[k][j]
B
map[i][k] = map[i][j] - map[k][j]
C
map[i][j] = map[i][k] - map[k][j]
D
map[k][j] = map[i][j] - map[i][k]
答案与解析
正确答案:A
根据 Floyd 算法,如果 i 到 k 加上 k 到 j 的最短路长度小于当前 i 到 j 的最短路长度,则用前者更新后者。 (图论算法: Floyd 算法)
4
单选题
适中
下列Dijkstra算法中,横线处应该填入的是( )。
A
dis[j] > minn && cheak[j] == 0
B
dis[j] < minn && cheak[j] == 0
C
dis[j] >= minn && cheak[j] == 0
D
dis[j] < minn && cheak[j] != 0
答案与解析
正确答案:B
朴素dijkstra算法,在非负权图中,用cheak[]标记已经求得最短路的点(因为已经求得,所以后续不会再更新),每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因,该节点minxj将加入已经求得最短路的点的集合,同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的,因此选B。
5
单选题
适中
下面Floyd算法中,横线处应该填入的是( )。
A
map[i][j] < map[i][k] + map[k][j]
B
map[i][j] > map[i][k] + map[k][j]
C
map[i][j] > map[i][k] - map[k][j]
D
map[i][j] < map[i][k] - map[k][j]
答案与解析
正确答案:B
Floyd算法本质是个DP,或者可以理解为松弛操作:
i和j的最短路如果可以通过中间节点k做更新:
则需要map[i][j]>map[i][k]+map[k][j];选B。