知到答案算法分析与设计（山东联盟）智慧树答案_2022年

第七章

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