算法分析与设计 复习题
判断题 ....................................................................................... 1 选择题： ................................................................................. 15
判断题
1. 算法就是一组有穷的规则。 答案：正确
2. 概率算法中蒙特卡罗算法得到的解必是正确的。 答案：错误
3. 程序和算法一样，都是某种程序设计语言的具体实现。 答案：错误
4. 合并排序算法是渐近最优算法。 答案：正确
5. 递归定义必须是有确切含义是指必须一步比一步简单，最后是有终结的，决不能无限循环下去。 答案：正确
6. 二分搜索方法在最坏的情况下用O(log n)时间完成搜索任务。 答案：正确
7. 能否利用分治法完全取决于问题是否具有如下特征：利用该问题分解出的子问题的解可以合并为该问题的解。 答案：正确
8. 分治法的基本思想是将一个规模较大的问题分解成若干个规模较小的子问题，这些子问题之间并不一定相互独立。 答案：错误
9. 递归算法的效率往往很低，费时和费内存空间。 答案：正确
10. 当一个问题具有最优子结构性质时只能用动态规划方法求解。 答案：错误
11. 如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为多阶段决策问题。 答案：正确
12. 反复应用分治手段，不能使子问题与原问题类型一致而其规模却不断缩小。 答案：错误
13. 裴波那契数列的定义：f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2，其数据的定义形式不是按递归定义。 答案：错误
14. 0-1背包问题与背包问题这两类问题都可以用贪心算法求解。 答案：错误
15. 证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。 答案：错误
16. 子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。 答案：正确
17. 概率算法允许在执行过程中随机地选择下一个计算步骤。 答案：正确
18. 二分搜索法的二分查找只适用于顺序存储结构。 答案：正确
19. 要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。 答案：正确
20. 用回溯法解题一个显著特征是在搜索过程中动态产生问题的解空间。 答案：错误
21. 从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。 答案：正确
22. 多阶段决策问题中，每一个阶段可能有若干个决策可供选择 答案：正确
23. 拉斯维加斯算法不会得到不正确的解，但有时找不到解。 答案：正确
24. 在通往边界条件的递归调用过程中，系统用堆栈保存的每次调用的中间结果是局部变量
和返回地址值。 答案：正确
25. 要想在电脑上扩大所处理问题的规模，有效的途径是提高算法的计算复杂度。 答案：错误
26. 程序必须满足算法具有数据输出的性质。 答案：正确
27. 反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小 答案：正确
28. 一个算法产生一个或多个输出，它们是同输入有某种特定关系的量 答案：正确
29. 最优子结构性质特征反映了递归思想的应用 答案：正确
30. 递归边界本身并不使用递归的定义 答案：正确
31. 用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作总量来确定的。 答案：正确
32. 应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。 答案：正确
33. 好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。 答案：正确
34. 一个递归定义必须是有确切含义的，必须一步比一步简单，最后是有终结的，不能无限循环下去。 答案：正确
35. 最优子结构性质是应用分治法的前提。 答案：正确
36. 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。 答案：正确
37. 有些数据结构如二叉树等，由于其本身的递归特性、特别适合用递归的形式来描述。 答案：正确
38. 概率算法的一个基本特征是，对所求问题的同一个实例用同一个算法求解两次一定能得到完全相同的效果。 答案：错误
39. 问题可以分解为若干个规模较小的相同问题，即称该问题具有最优子结构性质。 答案：错误
40. 递推是从内边界条件出发，通过递推式达到边界条件。 答案：正确
41.所有的递归函数都能找到对应的非递归定义。 答案：正确
42.定义递归函数时可以没有初始值。 答案：错误
43.动态规划算法的基本要素是最优子结构。 答案：正确
44.最优子结构性质是指原问题的最优解包含其子问题的最优解。 答案：正确
45.动态规划算法求解问题时，分解出来的子问题相互独立。 答案：错误
46.满足贪心选择性质必满足最优子结构性质。 答案：错误
47.回溯法中限界函数的目的是剪去得不到最优解的子树。 答案：正确
48. 分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。 答案：错误
49. 任何递归算法都有递归出口。 答案：正确
50. 递归算法的执行效率比功能相同的非递归算法的执行效率高。 答案：错误
51. 递归算法不能转换成对应的非递归算法。 答案：错误
52. 数据元素是数据的最小单位 答案：错误
53. 数据对象就是一组数据元素的集合 答案：错误
54. 任何数据结构都具备三个基本运算：插入、删除和查找。 答案：错误
55. 数据对象是由有限个类型相同的数据元素构成的。 答案：正确
56. 数据的逻辑结构与各数据元素在计算机中如何存储有关。 答案：错误
57. 如果数据元素值发生改变，则数据的逻辑结构也随之改变。 答案：错误
58. 逻辑结构相同的数据，可以采用多种不同的存储方法。 答案：正确
59. 逻辑结构不相同的数据，必须采用不同的存储方法来存储。 答案：错误
60.数据的逻辑结构是指数据元素的各数据项之间的逻辑关系。 答案：错误
61.顺序存储方式只能用于存储线性结构。 答案：错误
62. 算法可以用不同的语言来描述，如果用C语言或Pascal语言等高级语言来描述，则算法就等同于程序。 答案：错误
63.数据的逻辑结构是指各数据元素之间的逻辑关系。 答案：正确
64.数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、节点和数据域。 答案：正确
65.数据的物理结构是指数据在计算机内的实际存储形式。 答案：正确