数据结构与算法期末考试题及答案
一、选择题
1. 用于分离由加权无向边组成的完全连通图中连通分量中不相邻顶点的单纯形算法是（C）
A. 最小生成树算法
B. 广度优先搜索算法
C. 最大流算法
D. 关键路径算法
2. 要设计一个使用图来表示的行业里的公司的决策问题，图的顶点应该表示（B）
A. 公司拥有的资源
B. 公司所面对的决策选择
C. 公司内部的组织结构
D. 公司的竞争对手
3. 算法的计算时间复杂度O(log2n)中的n表示（A）
A. 求解问题规模
B. 求解算法所处理的数据量
C. 求解问题中所涉及的参数量
D. 求解算法所进行的求解步骤
4. 以树形结构存储的优先队列中元素出队的操作时间复杂度是（C）
A. O(1)
B. O(n)
数据结构与算法题库C. O(log2n)
D. O(n2)
5. 以下关于贝尔曼-福特算法的描述错误的是（A）
A. 贝尔曼-福特算法是求图 G=(V,E)最小生成树的法
B. 贝尔曼-福特算法克服了Prim算法因存储顶点增量重复而带来的内存浪费
C. 求解过程中，要维护贝尔曼-福特树中任意两个顶点之间的最短距离
D. 贝尔曼-福特算法可以解决单源最短路径问题
二、简答题
1. 请说明拓扑排序的概念，以及如何使用拓扑排序解决求解关键路径的问题。
拓扑排序是指对有向无环图进行排序，得到一个顶点的线性序列，使得对于图中的每条有向边（u,v），均有u在v之前。
拓扑排序可用于求解关键路径，首先对所有活动按照拓扑排序的方法进行排序，计算该活动的最早开始时间ESi和最晚开始时间LSi，若ESi=LSi，则此活动运行期间不能延迟，为关键活动；若ESi≠LSi，则此活动可以合理推迟，不为关键活动。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。