2014年9月份考试算法设计分析第一次作业.doc

1、2014年 9月份考试算法设计分析第一次作业 一、单项选择题（本大题共 50分，共 20 小题，每小题 2.5 分） 1. 算法分析的两个主要方面是（ ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂度和程序复杂度 2. 计算机算法指的是（ ）。 A. 计算方法 B. 排序方法 C. 解决问题的方法和过程 D. 调度方法 3. Java 的类一般有 4个部分组成：请选出不属于的一个 （ ） A. 类名 B. 数据成员 C. 方法 D. 组 4. 多阶段决策问题 ,就是要在 可以选择的那些策略中间 ,选取一个（ ）策略 ,使在预定的标准下达到最好的效

2、果。 A. 最优 B. 最差 C. 平衡 D. 任意 5. 快速排序法的基本思想是对输入的子数组按以下三个步骤进行排序（ ）。 A. 分解，合并，递归求解 B. 合并，递归求解，分解 C. 递归求解，分解，合并 D. 分解，递归求解 , 合并 6. 程序可以不满足算法性质的（ ） A. 输入 B. 输出 C. 确定性 D. 有限性 7. 根据排序元素所在位置的不同，排序分（ ）。 A. 内排序和外排序 B. 首排序和尾排序 C. 顺序 排序和逆序排序 D. 堆排序和栈排序 8. 算法必须具备输入、输出和（ ）等 5个特性。 A. 可执行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C.

3、 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 9. 大型程序设计一般用（ ）数据类型来描述算法。 A. 逻辑 B. 抽象 C. 简明 D. 复杂 10. JAVA 程序主要有以下两种类型（ ） A. 应用程序和 APPLET 应用程序和理论程序 B. 系统程序和应用程序 C. 系统程序和理论程序 D. D 系统程序和 APPLET 应用程序 11. 动 态规划算法是（ ）递归的。 A. 自底向上 B. 自顶向下 C. 自左至右 D. 自右至左 12. 在最接近点对问题中，严格的说，最接近点对可能（ ）。 A. 有无数对 B. 恰好一对 C. 多于一对 D. 少于一对 13. 与分治法

4、不同的是，适合于用动态规划求解的问题（ ） A. 经分解得到子问题往往不是互相独立的 B. 经分解得到子问题往往是互相独立的 C. 经分解得到子问题往往是互相交叉的 D. 经分解得到子问题往往是任意的 14. 二分搜索算法的基本思想是将 n个元素分成个数大致相同的两半，取an/2与 x 进行比较：如果（ ），则只要在数组 a的左半部继续搜索 x。 A. x an/2 B. x=an/2 C. xan/2 D. x=an/2 15. 适用动态规划的问题必须满足（ ） A. 最优化原理 B. 无前效性 C. 最优化原理和后效性 D. 最优化原理和无后效性 16. 直接或间接的调用自身的算法称为（

5、）。 A. 贪心算法 B. 递归算法 C. 迭代算法 D. 动态规划算法 17. 在多数情况下，当算法在执行过程中面临一个选择是，随机性选择常比最优选择省时，因此概率算法可 在很大程度上（）。 A. 增加算法复杂性 B. 降低算法复杂性 C. 保持原有算法复杂性 D. 复杂性不确定 18. 二分查找只适用（ ）存储结构。 A. 堆 B. 顺序 C. 任意顺序 D. 栈 19. 舍伍德算法的精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的（ ） A. 依赖性 B. 关联性 C. 重复性 D. 排斥性 20. 应用分治法的两个前提是（ ）。 A. 问题的可分性和解的可归

6、并性 B. 问题的可分性和解的存在性 C. 问题的复杂性和解的 可归并性 D. 问题的可分性和解的复杂性 二、判断题（本大题共 50 分，共 20 小题，每小题 2.5 分） 1. 概率算法中蒙特卡罗算法得到的解必是正确的？ ( ) 2. 程序和算法一样，都是某种程序设计语言的具体实现。 （ ） 3. 递归定义必须是有确切含义是指必须一步比一步简单 ,最后是有终结的 ,决不能无限循环下去？ ( ) 4. 二分搜索方法在最坏的情况下用 O(log n)时间完成搜索任务。（ ） 5. 具体的动态规划算法是多种多样的，但它们具有相同的填表格式。 ( ) 6. 分治法的基本思想是将一个规模较大 的问题

7、分解成若干个规模较小的子问题，这些子问题之间并不一定相互独立（ ） 7. 当一个问题具有最优子结构性质时只能用动态规划方法求解。 ( ) 8. 矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。（ ） 9. 由于矩阵乘法满足结合律。所以计算举证的连乘积不可以有许多不同的计算次序？ ( ) 10. 快速排序法是基于分治策略的。 （ ） 11. 贪心算法并不从整体最优考虑 ,它所做出的选择只是在某种意义上的局部最优选择？ ( ) 12. 如果 U 是 G的一个完全子图，则它也定义了一个空子图，反之亦然。（ ） 13. 0-1 背包问题与背包问题这两类问题都可以用贪心算法求解。（ ） 14. 对

8、于 （ n）当 n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。 ( ) 15. 数据模型可以认为是现实世界部分现象的抽象 ( ) 16. 分治策略是将一个规模为 n的问题分成 k个规模较小而结构与原问题相似的子问题 ( )。 17. 二分搜索法的二分查找只适用于顺序存储结构。 （ ） 18. 概率算法中使用的随机数只是一定程度上的随机，即伪随机数。（ ） 19. 程序 =算法 +数据结构 ( ) 20. 合并排序算法的基本思想是将待 排序的元素分成大小大致相同的 2个子集合 ( ) 答案： 一、单项选择题（ 50分，共 20 题，每小题 2.5 分） 1. A 2. C 3. D 4. A 5. D 6. D 7. A 8. B 9. B 10. A 11. A 12. C 13. A 14. A 15. D 16. B 17. B 18. B 19. B 20. A 二、判断题（ 50 分，共 20 题，每小题 2.5 分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.