超星 - 第3章课后练习 - 查题吧

单选题

以下关于动态规划的陈述中不正确的是()。

A. 使用动态规划必须满足无后效性的原则
B. 动态规划可求解多阶段优化问题
C. 动态规划的指标函数要满足可分离性、单调性、递推性
D. 动态规划只能倒推求解

单选题

关于动态规划问题的下列命题中错误的是()。

A. 动态规划阶段的顺序与求解过程无关
B. 状态是由决策确定的
C. 用逆序法求解动态规划问题的重要基础之一是最优性原理
D. 列表法是求解某些离散变量动态规划问题的有效方法

单选题

实现最长公共子序列利用的算法是()。

A. 分治法
B. 贪心法
C. 动态规划法
D. 回溯法

单选题

备忘录方法是哪种算法的变形()。

A. 分治法
B. 贪心法
C. 动态规划法
D. 回溯法

单选题

矩阵连乘问题的算法可由()设计实现。

A. 分支界限法
B. 贪心法
C. 动态规划法
D. 回溯法

单选题

实现最大子段和利用的算法是()。

A. 分治法
B. 贪心法
C. 动态规划法
D. 回溯法

单选题

用动态规划算法实现最大子段和所需要的时间复杂度为()。

A. O(n2)
B. O(nlogn)
C. O(n)
D. O(2n)

单选题

用动态规划算法实现矩阵连乘问题所需要的时间复杂度为()。

A. O(n2)
B. O(nlogn)
C. O(n3)
D. O(2n)

单选题

用动态规划算法实现矩阵连乘问题所需要的空间复杂度为()。

A. O(n2)
B. O(n3)
C. O(n)
D. O(n4)

单选题

用动态规划算法实现最长公共子序列(设两序列的长度分别为m和n)所需要的时间复杂度为()。

A. O(mn2)
B. O(mlogn)
C. O(mn)
D. O(m2n)

4