川农大算法分析期末复习.doc

- -

算法分析与设计复习题

算法分析与设计复习题.............................................................1

判断题.........................................................................................1

选择题：...................................................................................15

判断题

1. 算法就是一组有穷的规那么。

答案：正确

5. 递归定义必须是有确切含义是指必须一步比一步简单，最后是有终结的，决不能无限循

环下去。

答案：正确

6. 二分搜索方法在最坏的情况下用 O(log n)时间完成搜索任务。

答案：正确

7. 能否利用分治法完全取决于问题是否具有如下特征：利用该问题分解出的子问题的解可

以合并为该问题的解。

答案：正确

8. 分治法的根本思想是将一个规模较大的问题分解成假设干个规模较小的子问题，这些子

问题之间并不一定相互独立。

- -

11. 如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，那么称它

为多阶段决策问题。

答案：正确

12. 反复应用分治手段，不能使子问题与原问题类型一致而其规模却不断缩小。答案：错

误

13. 裴波那契数列的定义：f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2，其数据的定义形式不是

按递归定义。

答案：错误

14. 0-1 背包问题与背包问题这两类问题都可以用贪心算法求解。

答案：错误

答案：正确

18. 二分搜索法的二分查找只适用于顺序存储构造。

答案：正确

19. 要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。

答案：正确

20. 用回溯法解题一个显著特征是在搜索过程中动态产生问题的解空间。

答案：错误

21. 从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，

分治法的计算效率通常可以用递归方程来进展分析。

答案：正确

- -

量和返回地址值。

答案：正确

答案：错误

答案：正确

27. 反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小

答案：正确

28. 一个算法产生一个或多个输出，它们是同输入有某种特定关系的量

答案：正确

30. 递归边界本身并不使用递归的定义

31. 用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为

答案：正确

32. 应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题

的一个〔最优〕解。

答案：正确

33. 好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。因

此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。

答案：正确

34. 一个递归定义必须是有确切含义的，必须一步比一步简单，最后是有终结的，不能无

限循环下去。

答案：正确

35. 最优子构造性质是应用分治法的前提。

- -

38. 概率算法的一个根本特征是，对所求问题的同一个实例用同一个算法求解两次一定能

得到完全一样的效果。

39. 问题可以分解为假设干个规模较小的一样问题，即称该问题具有最优子构造性质。

40. 递推是从边界条件出发，通过递推式到达边界条件。

答案：正确

41.所有的递归函数都能找到对应的非递归定义。

答案：正确

42.定义递归函数时可以没有初始值。

答案：正确

答案：正确

45.动态规划算法求解问题时，分解出来的子问题相互独立。

答案：错误

46.满足贪心选择性质必满足最优子构造性质。

答案：错误

47.回溯法中限界函数的目的是剪去得不到最优解的子树。

答案：正确

48. 分支限界法类似于回溯法，也是一种在问题的解空间树 T 上搜索问题解的算法，两者

的搜索方式是一样的。

答案：错误

49. 任何递归算法都有递归出口。

答案：正确

- -

52. 数据元素是数据的最小单位

答案：错误

答案：错误

答案：错误

55. 数据对象是由有限个类型一样的数据元素构成的。

答案：正确

56. 数据的逻辑构造与各数据元素在计算机中如何存储有关。

答案：错误

答案：错误

60.数据的逻辑构造是指数据元素的各数据项之间的逻辑关系。

答案：错误

61.顺序存储方式只能用于存储线性构造。

答案：错误

62. 算法可以用不同的语言来描述，如果用 C 语言或 Pascal 语言等高级语言来描述，那么

算法就等同于程序。

答案：错误

63.数据的逻辑构造是指各数据元素之间的逻辑关系。

答案：正确