算法设计|算法--第四章动态规划|算法

一.单选题（共13题,55.9分） 1
【单选题】关于动态规划与分治法的区别,表述不正确的是()

A、动态规划划分的子问题一般具有重叠子问题,分治法则通常互不相交
B、动态规划建立在描述子问题最优值关系的状态转移方程基础上,分治法一般不需要建立类似的最优值之间的数量关系
C、分治法能写成递归形式,动态规划不能写成递归形式
D、动态规划一般用来求解最优化问题,分治法多不用于求解最优化问题

正确答案： C
2
【单选题】给定序列X={A, B, C, B, D, A, B}和Y={B, D, C, A, B, A},它们的最长公共子序列是()

A、 BCAA
B、 BCDA
C、 ADAB
D、 BCBA

正确答案： D
3
【单选题】有7个工件,它们在第一台机器和第二台机器上的处理时间分别为:[t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15],[t21,t22,t23,t24,t25,t26,t27]=[7,2,6,18,3,10,4],这7个工件的最优加工顺序为()。

A、1,2,3,4,5,6,7
B、1,4,6,3,2,7,5
C、1,6,4,3,7,5,2
D、1,4,2,6,5,7,3

正确答案： C
4
【单选题】按照顺序排列动态规划的求解步骤,正确的是( ) (1)递归定义最优值。 (2)以自底向上的方式计算出最优值,并记录相关信息。 (3)分析最优解子结构性质。 (4)构造出最优解。

A、(1),(2),(3),(4)
B、(1),(3),(2),(4)
C、(3),(1),(2),(4)
D、(1),(2),(4),(3)

正确答案： C
5
【单选题】n个工件2台机器的加工顺序问题(调度问题),依据贝尔曼法则设计的动态规划算法的时间复杂度为( )

A、O(logn)
B、O(nlogn)
C、O(logn^2)
D、O(n^2)

正确答案： B
6
有7个工件，它们在第一台机器和第二台机器上的处理时间分别为：[t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15]，[t21,t22,t23,t24,t25,t26,t27]=[7,2,6,18,3,10,4]，这7个工件的最优加工顺序为（）。

A、1，2，3，4，5，6，7
B、1，4，6，3，2，7，5
C、1，6，4，3，7，5，2
D、1，4，2，6，5，7，3

正确答案： C
7
【单选题】n个物品,背包容量为W的0-1背包问题的动态规划算法的时间复杂度为( )

A、O(logn)
B、O(nW)
C、O(n^2)
D、O(W^2)

正确答案： B
8
设c[i][j]表示序列Xi和Yj的最长公共子序列的长度。则它的递推关系式为：

文章图片

则，根据给定的X=={A, B, C, B, D, A, B}和Y={B, D, C, A, B, A}从上到下填写缺失值

文章图片

A、 2 3 3
B、 2 2 2
C、 3 4 4
D、 3 3 3

正确答案： C
9
【单选题】关于动态规划和回溯法的区别,以下表述不正确的是()

A、动态规划和回溯法都可以用来求解最优化问题,但回溯法是基于枚举解的思想,动态规划则是基于构造子问题最优值关系的方式
B、在遇到重叠子问题的时候,动态规划思想会使用存储最优值的方式直接排除,而回溯法一般做法是设法避环和剪枝,降低其影响
C、在求解相同问题时,动态规划必然比回溯法浪费空间,但是更节约时间

正确答案： C
补充：
【单选题】关于动态规划与分治法的区别,表述不正确的是()

A、动态规划划分的子问题一般具有重叠子问题,分治法则通常互不相交
B、动态规划建立在描述子问题最优值关系的状态转移方程基础上,分治法一般不需要建立类似的最优值之间的数量关系
C、分治法能写成递归形式,动态规划不能写成递归形式
D、动态规划一般用来求解最优化问题,分治法多不用于求解最优化问题

正确答案： C
10
【单选题】0-1背包问题的跳跃点算法的时间复杂度为( )

A、O(2^n)
B、O(nW)
C、O(n^2)
D、O(min(nW,2^n))

正确答案： D
11
{【单选题】矩阵连乘问题中,A1矩阵大小是100*5,A2矩阵大小为5*30,A3矩阵大小为30*10,则乘法次序 (A1*A2)*A3需要的元素乘法次数是( )。

A、15000
B、30000
C、45000
D、4500000
}

正确答案： C
12
解决给定的5个矩阵连乘问题：矩阵A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3），设m[i][j]表示Ai...Aj的最优计算次序对应的乘法计算次数（最优值），P为存储矩阵行列的数组，其中P[i]是第i个矩阵的列、第i-1个矩阵的行。求解最优值递归关系是为：

文章图片

根据该递归关系式，求解过程中得到下面最优决策的二维表：

文章图片

由此，可得上述5个矩阵连乘的最优计算次序为（）

A、（A1（A2（A3（A4A5））））
B、（（A1A2）（A3（A4A5）））
C、（（A1A2）（（A3A4）A5））
D、（A1（（A2（A3A4））A5））

正确答案： D 我的答案：D得分： 4.3分
13
解决给定的5个矩阵连乘问题：矩阵A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3），设m[i][j]表示Ai...Aj的最优计算次序对应的乘法计算次数（最优值），P为存储矩阵行列的数组，其中P[i]是第i个矩阵的列、第i-1个矩阵的行。求解最优值递归关系是为：

文章图片

根据该递归关系式，求解得到下面二维表：

文章图片

行A1和列A5确定的方格中的元素是（）。

A、 132
B、 130
C、 264
D、 150

正确答案： D
二.多选题（共6题,25.8分） 1
【多选题】有关0-1背包问题,用c[i][j]描述子问题:1...i共i个物品,背包容量为j的最优值(装入背包的最大价值),以下说法正确的是( )

A、当i=0时或j=0时,c[i][j]=0
B、当j
C、当j≥w i时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最小。故c]i][j]=min(c[i-1][j],c[i-1][j-w i]+v i)
D、当j≥w i时,物品可以装入,装呢还是不装呢?这取决于哪个决策能够让c[i][j]最大。故c]i][j]=max(c[i-1][j],c[i-1][j-w i]+v i)

正确答案： ABD
2
【多选题】有关矩阵连乘问题说法正确的是( )

A、矩阵A i...A j连乘, A i的行列为(p(i-1)×p i),A j的行列为(p(j-1)×p j),最后一次划分在A k,它的行列为(p(k-1)×p k),k=i,i+1,...,j,其结果矩阵的行列为(p(i-1)×p j)。
B、n个矩阵连乘A 1...A n,其子问题为A i...A j连乘,1≤i≤j≤n,其中i=j表示规模为1的子问题,其需要的乘法次数为0
C、设矩阵A i...A j连乘最少的乘法次数为c[i][j],矩阵A i...A j连乘的子问题为矩阵A i...A k连乘和矩阵A k+1...A j连乘,则最优值的递归关系式表示为c[i][j]=c[i][k]+c[k+1][j]+p i-1* p j* p k
D、矩阵连乘问题的时间复杂度为O(n^2)

正确答案： AB
3
【多选题】有关工件加工顺序问题算法描述正确的是()

A、该问题的子问题:M1开始处理S集合的工件时,M2需要t时间才能停下来情况下,加工S集合中的工件总加工时间最短,可以用T(S,t)表示最短的总加工时间。
B、该问题的最短加工时间用T(S,t),则递推方程为:T(S,t)=min i∈S{t 1i+T(S-{i},max{t-t 1i,0}+t 2i)}
C、该问题的动态规划算法依据Johnson Bellman’s Rule.
D、该算法将第一台机器处理时间大于等于第二台机器处理时间的工件后安排加工,并按照第二台机器处理时间非降序排列的顺序加工。

正确答案： ABC
4
有关工件加工顺序问题算法描述正确的是()

A、该问题的子问题:M1开始处理S集合的工件时,M2需要t时间才能停下来情况下,加工S集合中的工件总加工时间最短,可以用T(S,t)表示最短的总加工时间。
B、该问题的最短加工时间用T(S,t),则递推方程为:T(S,t)=min i∈S{t 1i+T(S-{i},max{t-t 1i,0}+t 2i)}
C、该问题的动态规划算法依据Johnson Bellman’s Rule.
D、该算法将第一台机器处理时间小于第二台机器处理时间的工件后安排加工,并按照第一台机器处理时间非降序排列的顺序加工。
E、该算法将第一台机器处理时间大于等于第二台机器处理时间的工件后安排加工,并按照第二台机器处理时间非降序排列的顺序加工。

正确答案： ABC
5
【多选题】有关最长公共子序列问题的动态规划算法说法正确的是( )

A、X n和Y m的代表了两个长度为n和m的字符串,求X n和Y m的最长公共子序列的子问题是:求X i和Y j的最长公共子序列,i=0,1,...n,j=0,1,...,m。
B、X i和Y j的最长公共子序列当i=0时,最长公共子序列的长度为0; j=0时,最长公共子序列的长度也为0
C、设X i和Y j的最长公共子序列的长度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]
D、设X i和Y j的最长公共子序列的长度c[i][j],求最优值的递归关系式为:c[i][j]=c[i-1][j]+1

正确答案： AB
6
有关动态规划描述正确的是()

A、动态规划将多阶段决策问题转化为单阶段决策问题。
B、动态规划往往用于求解某种最优性质的问题。
C、适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。
D、动态规划求解时往往采用填表的方法记录问题最优值。
E、动态规划划分的各子问题与原问题相同,一般递归求解子问题。

正确答案： ABCD
补充：
多选题】有关0-1背包问题的跳跃点算法描述正确的是( )

A、跳跃点(x,c[i][x])表示装入重量为x时,装入最大价值为c[i][x]
B、初始跳跃点为(0,0)
C、用p[i]描述c[i][j]的跳跃点,用q[i]描述p[i-1]+(w i,v i),则p[i+1]=p[i]∪q[i],其中i=1,2,...,n
D、用p[i]描述c[i][j]的跳跃点,用q[i]描述p[i-1]+(w i,v i),则p[i+1]=p[i]∪q[i]去掉重量不减,价值反而减少的受控点。其中i=1,2,...,n

正确答案： ABD
三.判断题（共4题,18.3分） 1
矩阵连乘问题中有多个矩阵相乘，问题是安排矩阵相乘的先后顺序，使总乘法次数最少，例如有[A][B]C三个矩阵，则可行的顺序有ABC\ACB\CAB\CBA\BAC\BCA六个。
正确答案：×
2
0-1背包问题的动态规划解法不适合背包容量非常大()的情况。
正确答案：√
3
最长公共子序列问题中，如果采取穷举法，可以在序列A中子序列可能的开头和结尾（因为子序列由其开头位置和结尾位置唯一确定），然后在序列B中查找它是否存在，如果按照子序列长度降序枚举，找到的第一个公共子序列就是最长公共子序列。
正确答案：×
4
以动态规划求解0-1背包问题，背包容量可以是任意实数。
正确答案：×
补充：

最长公共子序列问题的动态规划解法时间复杂度等于两个序列长度之积。
正确答案：√
0-1背包问题的贪心法解法和动态规划解法都能够生成最优解。
【算法设计|算法--第四章】正确答案：×