算法设计与分析(python版)-作业四

参考教材：算法设计与分析（Python版）         作者：王秋芬

1 . 普通 （5分）解决给定的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））

2 . 容易 （5分）关于动态规划和回溯法的区别，以下表述不正确的是

A. 动态规划和回溯法都可以用来求解最优化问题，但回溯法是基于枚举解的思想，动态规划则是基于构造子问题最优值关系的方式

B. 在遇到重叠子问题的时候，动态规划思想会使用存储最优值的方式直接排除，而回溯法一般做法是设法避环和剪枝，降低其影响

C. 在求解相同问题时，动态规划必然比回溯法浪费空间，但是更节约时间

3 . 容易 （5分）关于动态规划与分治法的区别，表述不正确的是

A. 动态规划划分的子问题一般具有重叠子问题，分治法则通常互不相交

B. 动态规划建立在描述子问题最优值关系的状态转移方程基础上，分治法一般不需要建立类似的最优值之间的数量关系

C. 分治法能写成递归形式，动态规划不能写成递归形式

D. 动态规划一般用来求解最优化问题，分治法多不用于求解最优化问题，

4 . 普通 （5分）矩阵连乘问题中，A1矩阵大小是100*5,A2矩阵大小为5*30，A3矩阵大小为30*10，则乘法次序 (A1*A2)*A3需要的乘法次数是

A. 15000

B. 30000

C. 45000

D. 450000000

5 . 普通 （5分）规模为5矩阵连乘问题,计算次序有()种。

A. 10

B. 12

C. 14

D. 16

6 . 普通 （5分）根据下面斐波那契数列的递归算法，可知斐波那契数列的第n项的递归式为（）。 def Fibonacci(int num):

 if(num == 0 || num == 1):

        return num

    return  Fibonacci(num-1)+Fibonacci(num - 2)

A. Fibonacci(n)=0  当n=0时

B. Fibonacci(n)=1  当n=1时

C. Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2) 当n〉1时

D. Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3) 当n〉1时

7 . 普通 （5分）下面代码为求n！的递归算法，该代码反应的n!问题递归实现的停止条件（边界条件）为（）。

def fun(n):   if (n == 1):

    return 1 else :

  return fun(n - 1) * n

A. n!=1  当n=0时

B. n!=1  当n=1时

C. n!=1  当n〈1时

D. n!=1  当n〈=1时

8 . 容易 （5分）合并排序的空间复杂度为()

A. θ(logn)

B. θ(n)

C. θ(nlogn)

D. θ(n*n)

9 . 普通 （5分）以下哪个问题的时间复杂度与输入序列有关（）

A. 二分查找

B. 最小值问题

C. 合并排序

D. 以上都不对

10 . 普通 （5分）以下函数的功能是（）

def Q(R, low，high):

   if(low<high):#仅当区间长度大于1时才须排序

     pivotpos=Partition(R,low,high) #划分后的基准元素所对应的位置

       Q(R,low,pivotpos-1)#对左区间递归排序

       Q(R,pivotpos+1,high)#对右区间递归排序 

A. 二分查找

B. 二分求最值

C. 合并排序

D. 快速排序

11 . 普通 （5分）以下代码功能为合并排序，请根据注释按照数顺序选择合适的语句填入对应的括号。

def MergeSort(A， low， high):

  if (low < high):

    （）#分解

（）# 递归序列左半部分

（）# 递归序列右半部分

Merge(A, low, middle, high)# 子问题的解合并成原问题的解

A. middle=(high-low)/2; MergeSort(A,low,middle); MergeSort(A,middle+1,high); 

B. middle=(low+high)/2; MergeSort(A,low,middle); MergeSort(A,middle+1,high); 

C. middle=(low+high)/2; MergeSort(A,middle+1,high);  MergeSort(A,low,middle);

D. middle=(high-low)/2; MergeSort(A,middle+1,high);  MergeSort(A,low,middle);

12 . 容易 （5分）合并排序的分治算法时间复杂度的是()

A. O(logn)

B. O(nlogn)

C. 

D. 

13 . 普通 （5分）矩阵连乘问题中有多个矩阵相乘，问题是安排矩阵相乘的先后顺序，使总乘法次数最少，例如 有[A][B]C三个矩阵，则可行的顺序有ABCACBCABCBABACBCA六个。

错误

14 . 普通 （5分）以动态规划求解0-1背包问题，背包容量可以是任意实数。

错误

15 . 普通 （5分）有关矩阵连乘问题说法正确的是()

A. 矩阵A i...A j连乘,其中A k的行列为(p k×q k),k=i,i+1,...,j,其结果矩阵的行列为(p i×q 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 iq jq k

D. 矩阵连乘问题的时间复杂度为O(n 2)

16 . 容易 （5分）动态规划的基本要素是()

A. 重叠子问题

B. 最优子结构性质

C. 自底向上的求解方式

D. 自顶向下的递归求解方式

17 . 普通 （5分）有关动态规划描述正确的是()

A. 动态规划将多阶段决策问题转化为单阶段决策问题。

B. 动态规划往往用于求解某种最优性质的问题。

C. 适用动态规划求解的问题经分解得到的各个子问题往往不是相互独立的。

D. 动态规划求解时往往采用填表的方法记录问题最优值。 E、 动态规划划分的各子问题与原问题相同,一般递归求解子问题。 F、 动态规划求解某种最优性质的问题时,整体的最优值和子问题的最优值之间存在递归关系。

18 . 普通 （5分）设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

19 . 普通 （5分）给定序列X={A, B, C, B, D, A, B}和Y={B, D, C, A, B, A}，它们的最长公共子序列是（）。

A. BCBA

B. BCDA

C. BDAB

D. BCAA

20 . 容易 （5分）按照顺序排列动态规划的求解步骤,正确的是() （1)递归定义最优值。 （2)以自底向上的方式计算出最优值,并记录相关信息。 （3）分析最优解子结构性质。 （4)构造出最优解。

A. (1),(2),(3),(4)

B. (1),(3),(2),(4)

C. (3),(1),(2),(4)

D. (1),(2),(4),(3)

最后

以上就是留胡子帅哥为你收集整理的算法设计与分析(python版)-作业四的全部内容，希望文章能够帮你解决算法设计与分析(python版)-作业四所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。