算法分析与设计

一、单选题 （题数：25，共 50.0 分）

1

时间复杂度T(n)=2T(n/3)+O(n)的解为()。

（2.0分）

• 
  

• A、

  O(n)

• B、

  O(n)

• C、

  O(nlogn)

• D、

  O(nlogn)

我的答案：A

2

用回溯法解0-1背包问题时,解空间可构造为( )的形式。（2.0分）

• 
  

• A、

  排列树

• B、

  最小堆

• 
  

• C、

  子集树

• D、

  最大堆

我的答案：C

3

时间复杂度T(n)=T(n-1)+O(n)的解为()。

（2.0分）

• 
  

• A、

  O(n)

• 
  

• B、

  O(n)

• C、

  O(nlogn)

• D、

  O(nlogn)

我的答案：B

4

算法的时间复杂性函数用T(n)表示,其中参数n是指(  )。

（2.0分）

• 
  

• A、

  问题规模

• B、

  运行时间

• C、

  输入量

• D、

  输出量

我的答案：A

5

二分搜索算法中,如果待查找元素x不在已排好序的n个元素中,则完成该搜索任务需用(  )时间。

（2.0分）

• 
  

• A、

  O(nlogn)

• 
  

• B、

  O(logn)

• C、

  O(n)

• D、

  O(n)

我的答案：B

6

回溯法求解问题时,用于剪去不会产生更优解的结点的函数称为( )。（2.0分）

• 
  

• A、

  上界函数

• 
  

• B、

  限界函数

• C、

  约束函数

• D、

  下界函数

我的答案：B

7

f(n)= 10n,g(n)= log10,满足f(n)=(  )(g(n))。

（2.0分）

• 
  

• A、

  O

• B、

  Ω

• 
  

• C、

  θ

• D、

  β

我的答案：C

8

求A1、A2、A3、A4四个矩阵连乘，需尝试哪些断开位置

（2.0分）

• 
  

• A、

  1、2、3

• B、

  1、2、3、4

• C、

  2、3、4

• D、

  2、3

我的答案：A

9

f(n)= 4 ,g(n)= 4(3),满足f(n)=(  )(g(n))。

（2.0分）

• 
  

• A、

  O

• 
  

• B、

  Ω

• C、

  θ

• D、

  β

我的答案：B

10

?设有0-1背包实例，有3件物品，其重量分别为7,3,6，价值分别为5,12,9，且背包最大容量为10。问：背包内装入哪些物品可以不超重并且达到最大价值。用动态规划法求解该问题，表格中缺失的数据a,b,c依次为：

0	1	2	3	4	5	6	7	8	9	10
										c
0	0	0	12	12	12	12	12	12	a	b
0	0	0	0	0	0	0	5	5	5	5

（2.0分）

• 
  

• A、

  12，12，17

• B、

  12，17，17

• C、

  17，21，21

• 
  

• D、

  12，17，21

我的答案：B

11

以下哪个时间复杂度效率最低(  )。

（2.0分）

• 
  

• A、

  2

• B、

  n

• 
  

• C、

  nlogn

• D、

  n

我的答案：C

12

f(n)= 30(logn)10,g(n)= 30n,满足f(n)=(  )(g(n))。

（2.0分）

• 
  

• A、

  O

• B、

  Ω

• C、

  θ

• D、

  β

我的答案：A

13

一批级别相同的客户同时到达某银行办理业务,业务所需办理时间不一,应如何安排能够使得客户平均满意度最高( )。（2.0分）

• 
  

• A、

  随机安排办理次序

• B、

  优先业务时间长的客户优先

• 
  

• C、

  业务时间短的客户

• D、

  让客户抓阄决定次序

我的答案：C

14

在回溯法求解0-1背包问题时,对第i层的右儿子使用限界函数bound(i+1)判断是否有更优解,该限界函数内部计算过程采用的是( )算法。（2.0分）

• 
  

• A、

  动态规划

• 
  

• B、

  贪心法

• C、

  回溯法

• D、

  分治法

我的答案：C

15

时间复杂度T(n)=2T(n/2)+O(n)的解为()。

（2.0分）

• 
  

• A、

  O(n)

• B、

  O(n)

• 
  

• C、

  O(nlogn)

• D、

  O(nlogn)

我的答案：C

16

算法的复杂性函数S(n)表示( )。（2.0分）

• 
  

• A、

  时间复杂度

• 
  

• B、

  空间复杂度

• C、

  规模复杂度

• D、

  问题复杂度

我的答案：B

17

二分搜索算法中,原问题分解出()个规模较小的相同子问题。（2.0分）

• 
  

• A、

  0

• 
  

• B、

  1

• C、

  2

• D、

  3

我的答案：B

18

使用贪心算法解决活动安排问题时使用了(  )优先的贪心选择策略。

（2.0分）

• 
  

• A、

  最早开始活动

• 
  

• B、

  最早结束活动

• C、

  时间最短活动

• D、

  时间最长活动

我的答案：B

19

矩阵A、B和C的维数是：5*5、5*2，2*7，则A、B、C连乘的计算量最少为

（2.0分）

• 
  

• A、

  140

• 
  

• B、

  120

• C、

  245

• D、

  175

我的答案：B

20

一般背包问题使用贪心策略求解,当物品i无法整个装入剩余背包空间C时则该物品可装入背包的价值为( )。（2.0分）

• 
  

• A、

  C* w[i]/v[i]

• 
  

• B、

  C*v[i]/w[i]

• C、

  (C-w[i])*v[i]/ w[i]

• D、

  v[i]*w[i]/C

我的答案：B

21

f(n)= logn,g(n)= log(100n),满足f(n)=(  )(g(n))。

（2.0分）

• 
  

• A、

  O

• B、

  Ω

• 
  

• C、

  θ

• D、

  β

我的答案: C

22

回溯法求解0-1背包问题时,第i层的左儿子是否可行所用约束函数为( )。（2.0分）

• 
  

• A、

  cw+w[i]<=c

• B、

  cw<=c

• C、

  cp>=bestp

• D、

  cp+v[i]>=bestp

我的答案：A

23

f(n)= log4,g(n)= nlogn,满足f(n)=(  )(g(n))。

（2.0分）

• 
  

• A、

  O

• B、

  Ω

• C、

  θ

• D、

  β

我的答案：A

24

f(n)= logn,g(n)= 100logn,满足f(n)=(  )(g(n))。

（2.0分）

• 
  

• A、

  O

• 
  

• B、

  Ω

• C、

  θ

• D、

  β

我的答案：C

25

在回溯法和分支限界法中,判断结点是否包含可行解的函数称之为(  )。

（2.0分）

• 
  

• A、

  限界函数

• 
  

• B、

  约束函数

• C、

  可行函数

• D、

  上界函数

我的答案：B

二、填空题 （题数：1，共 10.0 分）

1

设有0/1背包实例，有四件物品，其重量分别为4,5,4,2，价值分别为1.5,5,8,1，且背包最大容量为12。问：背包内装入哪些物品可以不超重并且达到最大价值。使用回溯法搜索解空间树如下，请按顺序补充空白处的值(小数点后数字写全)。

（10.0分）

我的答案:

第一空： 

7.5

第二空： 

9.75

第三空： 

14.125

第四空： 

14.25

第五空： 

14.375

三、判断题 （题数：20，共 20.0 分）

1

分治法的基本思想是将原问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。（1.0分）

我的答案： √ 

2

回溯法采用深度优先搜索解空间树,分支限界法采用广度优先搜索解空间树。因此它们都需要特定的数据结构来存储活结点。（1.0分）

我的答案： ×

3

为了求得所有解,回溯法必须搜索解空间树中的所有叶子结点。（1.0分）

我的答案： ×

4

回溯法中,剪枝函数就是约束函数。（1.0分）

我的答案：  ×

5

动态规划算法、贪心算法和回溯算法都可以求解0-1背包问题的最优解,但是贪心算法的效率最高。（1.0分）

我的答案： ×

6

分治算法只能用递归技术来实现。（1.0分）

我的答案： ×

7

渐进复杂度符号O是指当规模充分大时复杂性的一个上界。（1.0分）

我的答案： √

8

算法复杂度通常是指平均情况下的算法复杂度。（1.0分）

我的答案： ×

9

刻画出最优解的结构特征是使用动态规划算法的关键性一步。（1.0分）

我的答案： √

10

分支限界法采用广度优先或最小耗费优先的方式搜索问题的解空间,其求解目标是找出满足约束条件的一个解或在满足约束条件的解中找出在某种意义下的最优解。（1.0分）

我的答案： √

11

回溯法搜索子集树时的时间复杂度为O(n!)。（1.0分）

我的答案： ×

12

优先队列分支限界法中的优先队列只能用堆来实现。（1.0分）

我的答案： ×

13

动态规划算法的核心思想是避免重复计算。（1.0分）

我的答案： √

14

分支限界法通常采用队列来存储活结点,并且每个活结点只有一次被扩展的机会。（1.0分）

我的答案： √

15

回溯法可以求得问题的一个解或所有解。（1.0分）

我的答案： √

16

回溯法比较适合解决组合数较大的问题,并且一定能求得最优解。（1.0分）

我的答案： √

17

分支限界法求解问题时,其最优解通常是通过结点的父结点信息不断回溯得到的。（1.0分）

我的答案： ×

18

动态规划算法和贪心算法都要求问题具有最优子结构性质,因此用动态规划能求得最优解的问题,贪心算法也可以求得最优解。（1.0分）

我的答案： √

19

二分搜索技术不要求n个元素有序。（1.0分）

我的答案： ×

20

旅行售货员问题的解空间可表示为一棵排列树,因此,用回溯法求解该问题时需要先创建排列树。（1.0分）

我的答案： ×

四、编程题 （题数：1，共 20.0 分）

1

无纸化办公设备采购

无纸化办公系统需采购终端设备、服务器以及会议音响。现有四家公司参加招标，每家公司均可供应三种设备。每家公司都提交了设备后期维护费用以及设备价格。

试设计一个算法，给出维护费用不超过5的最低成本采购方案。

注：单位统一忽略不计，成本不含后期维护费，仅设备价格总和。

1.下载附件，将两行注释符之间的代码补充完整并调试；

2. 把两行注释符之间的代码填写在答案栏中(注：上传附件不得分)。