一、选择题
1. 通俗地讲，算法是指解决问题的一种方法或一个过程，描述算法的方式有很多，如（ ）。
A、自然语言方式 C、程序设计语言
B、表格方式
D、程序设计语言与自然语言相结合
算法的描述方式（常用的） 算法描述 自然语言
流程图 特定的表示算法的图形符号
伪语言 包括程序设计语言的三大基本结构及自然语言的一种语言 类语言 类似高级语言的语言，例如，类PASCAL、类C语言
2.算法的复杂性依赖于（ ）。 A、要解决问题的规模 C、算法本身的函数
3. 以下描述是有关算法设计的基本步骤： ①问题的陈述
②算法分析
③模型的拟制
④算法的实现
B、算法的输入
D、设计者的学术水平
⑤算法的详细设计 ⑥文档的编制，应与其它环节交织在一起 其中正确的顺序是（ ）。 A、①②③④⑤⑥ C、②④①③⑤⑥
4.对于含n个元素的子集树问题，最坏情况下解空间的叶结点数目为（ ）。 A、n!
5. 对于给定的问题，考虑算法复杂性的意义在于（ ）。 A、设计出复杂性尽可能低的算法
B、若该问题已有多种算法时，选择其中复杂性低的求解问题 C、提高算法设计的学术水平层次 D、判断算法的正确性
6.符号?在算法复杂度描述中表示（ ）。 A、紧渐近上界 B、渐近上界
C、紧渐近下界
D、渐近下界
B、2^n
C、2
n+1
B、①③⑤②④⑥ D、⑥①③⑤②④
-1
D、?n!/i!
i?1n7. 设f(n)、g(n)是定义在正数集上的正函数，如果存在正的常数C和自然数n0，使得当n?n0时有f(n)?Cg(n)，则称函数f(n)当n充分大时有上界g(n)，记作
f(n)?O(g(n))，即f(n)的阶（ ）g(n)的阶。
A、不高于
8. 回溯法在解空间树T上的搜索方式是（ ）。 A、深度优先
9. 下面关于动态规划和备忘录方法的叙述中正确的是（ ）。 A、备忘录方法是自顶向下的递归方式
B、动态规划自底向上的，其最优值的计算不能递归定义
C、当一个问题的所有子问题都至少需要求解一次时，用动态规划方法较好 D、当子问题空间的部分子问题可不必求解时，用备忘录方法则较有利
10.一个四城市的旅行售货员问题，其解空间的深度为（ ）。 A、3
11. 分支限界法与回溯法都是在问题的解空间树上搜索问题的解，二者（ ）。 A、求解目标不同，搜索方式相同 C、求解目标相同，搜索方式不同
12. 下列哪些问题不可以用贪心算法求得最优解（ ）。 A、哈夫曼编码 B、活动安排问题
13. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ ）。
A、回溯法
B、分支限界法
D、回溯法求解子集树问题
C、0-1背包问题 D、单源最短路径 B、求解目标不同，搜索方式也不同 D、求解目标相同，搜索方式也相同
B、4
C、5
D、6
B、广度优先
C、最小耗费优先
D、活结点优先
B、不低于
C、等价于
D、逼近
C、回溯法和分支限界法
14.分支限界法在解空间树T上的一种搜索方式是（ ）。 A、深度优先
15. 以下关于判定问题难易处理的叙述中正确的是（ ）。 A、可以由多项式时间算法求解的问题是难处理的
B、广度优先
C、活结点优先
D、长度优先
B、需要超过多项式时间算法求解的问题是易处理的 C、可以由多项式时间算法求解的问题是易处理的 D、需要超过多项式时间算法求解的问题是不能处理的
