一. 单选题（共4题，40分）

(单选题)动态规划法一般包含4个步骤，关于这4个步骤的顺序，正确的描述是( ).
A. 建立递归关系，分析最优解的结构，构造最优解，计算最优值
B. 分析最优解的结构，建立递归关系，计算最优值，构造最优解
C. 分析最优解的结构，构造最优解，建立递归关系，计算最优值
D. 建立递归关系，计算最优值，分析最优解的结构，构造最优解

正确答案: B :分析最优解的结构，建立递归关系，计算最优值，构造最优解 ;
10分
(单选题)动态规划算法的基本要素为（ )。
A. 最优子结构性质与贪心选择性质
B. 重叠子问题性质与贪心选择性质
C. 最优子结构性质与重叠子问题性质
D. 预排序与递归调用

正确答案: C :最优子结构性质与重叠子问题性质 ;
10分
(单选题)
利用动态规划法求解矩阵连乘问题时，以下叙述正确的是（）。
A. 矩阵的最优计算次序是最优值，最少的数乘次数是最优解
B. 矩阵的最优计算次序是最优解，最少的数乘次数是最优值
C. 矩阵的最优计算次序既是最优值，也是最优解
D. 先得到最优解，然后根据最优解计算得到最优值

正确答案: B :矩阵的最优计算次序是最优解，最少的数乘次数是最优值;
10分
(单选题)
在以下问题中，除了（），其余都是矩阵连乘问题\(A_1A_2A_3\)的子问题。
A. \(A_2\)
B. \(A_1A_2\)
C. \(A_1A_3\)
D. \(A_1A_2A_3\)

正确答案: C :;
10分

二. 填空题（共6题，60分）

(填空题)最优子结构性质指的是____________________。

正确答案：
(1) 问题的最优解包含其子问题的最优解
(填空题)所谓重叠子问题性质是____________________。

正确答案：
(1) 在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次
(填空题)
在动态规划法中，通常用________来记录所有已解决的子问题的答案。

正确答案：
(1) 表
(填空题)
动态规划算法有一个变形方法称为________。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可以避免相同子问题的重复求解。

正确答案：
(1) 备忘录方法
(填空题)
若已知矩阵A的维数为 \(p×q\)，矩阵B的维数为\(q×r\)，则求其乘积C=AB共需要_______次乘法。

正确答案：
(1) pqr
(填空题)
若已知{ABCD}是序列{}和{}的最长公共子序列，而且。
根据这些条件，可以断定是{}和{}的一个最长公共子序列。

正确答案：
(1) ABC