算法大视界章节测试课后答案2024春

第十章测试

1.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的
A:1倍 B:2倍 C:1/2 D:4倍
答案:A
2.下列哪一种图的邻接矩阵是对称矩阵？
A:有向图 B:AOV网 C:无向图 D:AOE网 3.设某强连通图中有n个顶点，则该强连通图中至少有（  ）条边
A:n+1 B:n(n-1) C:n D:n(n+1) 4.求解最短路径的Floyd算法的时间复杂度为
A:O（n） B:O（n*n*n） C:O（n*n） D:O（n+c） 5.图中有关路径的定义是
A:由不同边所形成的序列 B:由不同顶点所形成的序列 C:由顶点和相邻顶点序偶构成的边所形成的序列 D:其他定义都不是 6.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为
A:VT为所有顶点，ET为空 B:VT为网中任意一点，ET为空 C:VT为空，ET为网中所有边 D:VT，ET为空 7.下面不正确的是（    ）(1) .求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3 ) ；（图用邻接矩阵表示）(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路
A:(1),(2),(3) B:(1) C:(2),(3) D:(1),(3) 8.若要求在找到从S到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将Dijkstra算法略作修改，增加一个count[]数组：count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为：
A:对所有顶点都有count[V]=0 B:对所有顶点都有count[V]=1 C:count[S]=1;对于其他顶点V则令count[V]=0 D:count[S]=0;对于其他顶点V则令count[V]=1 9.数据结构中Dijkstra算法用来解决哪个问题？
A:关键路径 B:字符串匹配 C:最短路径 D:拓扑排序 10.使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
A:5, 2, 4, 3, 6 B:5, 2, 3, 6, 4 C:5, 2, 6, 3, 4 D:5, 2, 3, 4, 6