第七章单元测试
动态规划算法把原问题分为交叉的子问题,解决子问题,记录子问题的解,合并为原问题的解。
0/1背包问题的动态规划算法是多项式时间算法。
对于稀疏图,Floyd算法的效率要高于执行n次Dijkstra算法,也要高于执行n次SPFA算法。
Dijkstra算法在求解过程中,源点到集合S内各顶点的最短路径一旦求出,则之后不变了,修改的仅仅是源点到还没选择的顶点的最短路径长度。
含负权的最短路问题一般使用()求解。
动态规划算法的基本要素有( )和最优子结构性质。
下面不是动态规划的基本方法有()。
最短路算法中适用于稀疏图的是()
分治算法与动态规划算法的相同点是()
DAG上最短路,固定起点和终点没有意义。
DAG图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度 。
树上最大权独立集不包含u,可能包含儿子结点,也可能不包含儿子结点。
SPFA算法的时间复杂度为O(mn)
A:对 B:错
答案:对
A:对 B:错
A:对 B:错
A:错 B:对
A:动态规划 B:贪心算法 C:分治算法 D:网络流算法
A:贪心选择性质 B:独立子问题性质 C:分解合并性质 D:重叠子问题性质
A:舍入 B:多重选择 C:增加变量 D:区间变量
A:Bellman算法 B:Dijkstra算法 C:Floyd算法 D:SPFA算法
A:最优子结构 B:递推关系 C:子问题独立
D:子问题重叠
A:对 B:错
A:错 B:对
A:对 B:错
A:对 B:错
温馨提示支付 ¥3.00 元后可查看付费内容,请先翻页预览!