MOOC数据结构与算法Python版-第六周测验

1 单选(2分)

下列哪个算法使用到了分治策略？D

• A.

  迷宫寻路

• B.

  单词最短编辑距离

• C.

  博物馆大盗问题

• D.

  二分查找

2单选(2分)

函数值缓存最适合使用哪种Python中的数据类型？B

• A.

  集合

• B.

  字典

• C.

  栈

• D.

  列表

3 单选(2分)

已知数列G(x)满足：

• G(1)=G(2)=G(3)=1
• G(x)=G(x-1)+G(x-2)+G(x-3) (x≥4)

根据递推式写出求数列值的递归算法，问原始算法与采用函数值缓存的算法时间复杂度分别为多少？A

• A.

  O(3^n); O(n)

• B.

  O(2^n); O(1)

• C.

  O(2^n); O(n)

• D.

  O(n^3); O(n^2)

4 单选(2分)

博物馆大盗问题中，若共有10件宝物，背包总重为20单位，使用动态规划算法求解时需要建立多大的数组？C

• A.

  11x20

• B.

  12x22

• C.

  11x21

• D.

  12x20

5 单选(2分)

以下哪个说法是正确的？D

• A.

  “单词最短编辑距离”问题可使用贪心法解决

• B.

  相比于函数值缓存，动态规划的优势在于不需要额外的存储空间

• C.

  “字符串匹配”问题中不能应用动态规划思想

• D.

  贪心法适用于局部最优等同于总体最优的问题求解

6 多选(3分)

以下是使用递归算法对 求解的不完整代码：

1. def solveNQueen(N):
2. pool = # 
3. def queen(cur=0):
4. if cur == len(pool):
5. return # 
6. res = # 
7. for col in range(len(pool)):
8. pool[cur], flag = col, True
9. for row in range(cur):
10. if pool[row] == col or abs(col - pool[row]) == cur - row:
11. flag = False
12. break
13. if flag:
14. res += queen(cur+1)
15. return res
16. return queen(0)
17. # test
18. print(solveNQueen(8))

阅读代码，选出正确的选项 ABCD

• A.

  A处可以填“[0]*N”

• B.

  若X处填"[list(pool)]"，Y处填"[]"，该函数可返回N皇后问题的所有解

• C.

  若X处填"1"，Y处填"0"，该函数可返回N皇后问题解的个数

• D.

  A处可以填“[None]*N”

7 多选(3分)

以下哪些问题可用动态规划算法解决？CD

• A.

  后缀表达式求值

• B.

  列表排序

• C.

  单词最短编辑距离

• D.

  斐波那契数列求值

8 多选(3分)

以下哪些说法是正确的？ABD

• A.

  动态规划可以减少算法的时间复杂度

• B.

  动态规划不能减少算法的空间复杂度

• C.

  函数值缓存可以减少算法的空间复杂度

• D.

  函数值缓存可以减少算法的时间复杂度