算法 复习题选择题精选.doc

文档介绍：一、选择题
通俗地讲，算法是指解决问题的一种方法或一个过程，描述算法的方式有很多，如
（ ）o
A、自然语言方式
C、程序设计语言
算法的描述方式（常用的）
算法描述自然语言
流程图 特定的表示算法的图形符号
B、表格方式
D、程序设计语言与自然语言相结合
伪语言 包括程序设计语言的三大基本结构及自然语言的一种语言
类语言 类似高级语言的语言，例如，类PASCAL,类C语言
算法的复杂性依赖于（ ）。
B、算法的输入
D、设计者的学术水平
A、要解决问题的规模
C、算法本身的函数
以下描述是有关算法设计的基本步骤：
①问题的陈述 ②算法分析 ③模型的拟制 ④算法的实现
⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起
其中正确的顺序是（ ）o
A、①②③④⑤⑥ B、①③⑤②④⑥
C、②④①③⑤⑥ D、⑥①③⑤②④
对于含n个元素的子集树问题，最坏情况下解空间的叶结点数目为（）。
A、n! B、2A n C、2n+1-1 D、£加川
J=1
对于给定的问题，考虑算法复杂性的意义在于（ ）。
A、 设计出复杂性尽可能低的算法
B、 若该问题已有多种算法时，选择其中复杂性低的求解问题
C、 提高算法设计的学术水平层次
D、 判断算法的正确性
符号。在算法复杂度描述中表示（ ）。
A、紧渐近上界B、渐近上界 C、紧渐近下界
D、渐近下界
设f(n)、g(n)是定义在正数集上的正函数，如果存在正的常数C和自然数％,
使得当n>n0时有f (n) < Cg(n),则称函数f(n)当n充分大时有上界g("),记作 f(n) = O(g(n)),即/(“)的阶( )g(")的阶。
A、不高于 B、不低于 C、等价于 D、逼近
&回溯法在解空间树T上的搜索方式是( )。
A、深度优先
B、广度优先 C、最小耗费优先
D、活结点优先
下面关于动态规划和备忘录方法的叙述中正确的是( )。
A、 备忘录方法是自顶向下的递归方式
B、 动态规划自底向上的，其最优值的计算不能递归定义
C、 当一个问题的所有子问题都至少需要求解一次时，用动态规划方法较好
D、 当子问题空间的部分子问题可不必求解时，用备忘录方法则较有利
—个四城市的旅行售货员问题，其解空间的深度为( )=
A、3 B、4 C、5 D、6
分