一、选择题
1. 通俗地讲，算法是指解决问题的一种方法或一个过程，描述算法的方式有很多，如（）。

A、自然语言方式
B、表格方式
C、程序设计语言
D、程序设计语言与自然语言相结合
算法的描述方式（常用的）
算法描述自然语言
流程图特定的表示算法的图形符号
伪语言包括程序设计语言的三大基本结构及自然语言的一种语言
类语言类似高级语言的语言，例如，类PASCAL、类C语言
2.算法的复杂性依赖于（）。

A、要解决问题的规模
B、算法的输入
C、算法本身的函数
D、设计者的学术水平
3. 以下描述是有关算法设计的基本步骤：
①问题的陈述②算法分析③模型的拟制④算法的实现
⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起
其中正确的顺序是（）。

A、①②③④⑤⑥
B、①③⑤②④⑥
C、②④①③⑤⑥
D、⑥①③⑤②④
4.对于含n个元素的子集树问题，最坏情况下解空间的叶结点数目为（）。

A、n!
B、2^n
C、2n+1-1
D、
1!/!
n
i
n i =
∑
5. 对于给定的问题，考虑算法复杂性的意义在于（）。

A、设计出复杂性尽可能低的算法
B、若该问题已有多种算法时，选择其中复杂性低的求解问题
C、提高算法设计的学术水平层次
D、判断算法的正确性
6.符号Ω在算法复杂度描述中表示（）。

A、紧渐近上界
B、渐近上界
C、紧渐近下界
D、渐近下界
7. 设()f n 、()g n 是定义在正数集上的正函数，如果存在正的常数C 和自然数0n ，使得当0n n ≥时有()()f n Cg n ≤，则称函数()f n 当n 充分大时有上界()g n ，记作
()(())f n O g n =，即()f n 的阶（ ）()g n 的阶。

A 、不高于
B 、不低于
C 、等价于
D 、逼近
8. 回溯法在解空间树T 上的搜索方式是（ ）。

A 、深度优先
B 、广度优先
C 、最小耗费优先
D 、活结点优先
9. 下面关于动态规划和备忘录方法的叙述中正确的是（ ）。

A 、备忘录方法是自顶向下的递归方式
B 、动态规划自底向上的，其最优值的计算不能递归定义
C 、当一个问题的所有子问题都至少需要求解一次时，用动态规划方法较好
D 、当子问题空间的部分子问题可不必求解时，用备忘录方法则较有利
10.一个四城市的旅行售货员问题，其解空间的深度为（ ）。

A 、3
B 、4
C 、5
D 、6
11. 分支限界法与回溯法都是在问题的解空间树上搜索问题的解，二者（ ）。

A 、求解目标不同，搜索方式相同 B 、求解目标不同，搜索方式也不同 C 、求解目标相同，搜索方式不同 D 、求解目标相同，搜索方式也相同
12. 下列哪些问题不可以用贪心算法求得最优解（ ）。

A 、哈夫曼编码 B 、活动安排问题 C 、0-1背包问题 D 、单源最短路径
13. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ ）。

A 、回溯法
B 、分支限界法
C 、回溯法和分支限界法
D 、回溯法求解子集树问题
14.分支限界法在解空间树T 上的一种搜索方式是（ ）。

A 、深度优先
B 、广度优先
C 、活结点优先
D 、长度优先
15. 以下关于判定问题难易处理的叙述中正确的是（ ）。

A 、可以由多项式时间算法求解的问题是难处理的
B 、需要超过多项式时间算法求解的问题是易处理的
C 、可以由多项式时间算法求解的问题是易处理的
D 、需要超过多项式时间算法求解的问题是不能处理的
二、填空题
1. 如果存在正的常数C 和0N ，使得当 N ≥N0 时，有()()f N Cg N ≤，则称函数
()f N 当N 充分大时上有界，且()g N 是它的一个上界，记为 f(N)=O(g(N)) 。

这时还说
明()f N 的阶不 （高于/低于）()g N 的阶。

2.在循环赛日程表问题中，若给定的运动员数n=2^(k-1)，则至少需要__n ___天完成比赛；n=2^k 时，则需要__n-1___天。

其中，k 为正整数。

3. 按照符号O 的定义，如果()(())g N O f N =，则()()O f O g += O(f) 。

4. 算法是由若干条指令组成的有序序列，并且具有输入、 输出 、 确定性 和有限性的性质。

5.一个直接或间接地调用自身的算法称为___递归_____，它有两个条件，一个是要直接或间接地调用自身，另一个是必须有_初始条件或非递归定义的初始值_。

6. 一个问题能够用分治法求解，说明该问题：①可以分解为规模比较小的问题且容易解决，②该问题具有 最优子结构 性质，③分解后的子问题的解可以合并为原问题的解，④分解后的各个子问题是相互 独立 的。

7. 运用动态规划法的一般步骤是：①分析最优解，②定义 建立递归关系 ，③求最优值，④构造最优解。

8. 四个物品的0-1背包问题的解空间层数为 5 ，共有 8（2^n ）个叶结点。

共有 31（[2^（n+1）]-1）个结点
9. 对解空间的搜索过程中如果运用回溯法一个中间结点有 （一次/多次）机会称为扩展结点，若使用分支限界法则有 （一次/多次）机会。

用分支限界法求解0-1背包问题时，对于每个物品j 有重量wj 和价值vj ，考虑当前物品i ，已装入背包中物品的重量和价值分别为cw 、cv ，剩余物品的价值上界为urv ，剩余容量为c ，目前已有的最优价值为bestp ，则当左儿子满足约束条件 属于可行结点时，就将它加入活结点队列中；当右儿子满足上界条件 时才将它加入活结点队列中。

10.在使用回溯法考虑求解一个具体问题时，往往需要设计出约束条件和限界条件。

装
载问题的约束条件是__
∑=≤k
i i
i C w
x 1
__；限界条件是bestw>cw+r ，其中，bestw 是当前最优
值，cw=__当前最优载重量_∑=k
i i
i c
x 1
__，r=___剩余集装箱重量__
∑+=n
k i i
w
1
_。

三、证明题
1.证明哈夫曼编码的贪心选择性质。

2.试证明活动安排问题的贪心选择性质。

3.试证明最长公共子序列问题具有最优子结构性质。

四、求下列各式时间复杂度
1.写出函数2
10log 3n n +的渐近表达式。

O(n^2)
2.
写出函数2
log n n +的渐近表达式。

3.写出函数23/42n
n +的渐近表达式。

O(2^n)
4.求1
275()(/5)(3/4)
75
C n T n C n T n T n n <⎧⎪=⎨
++≥⎪⎩的渐近表达式（1C ，2C 为常数）。

5.写出函数21log 1032413n
n n ⎛⎫
++ ⎪⎝⎭
的渐近表达式。

五、应用题
1.有0-1背包问题如下：n=4，c=20，P=（11，8，15，18），W=（5，4，4，8）。

试画出用回溯法求解时的搜索情况。

（本题6分） 解：
① n=4，c=20，P=（11，8，15，18），W=（5，4，4，8） ②
2.请用快速排序法升序排序下面实例，给出每一趟排序的结果。

（3，20，5，9，2，30，25，18，16，3） 解：
２ ３ ３ ９ ５ 30 25 18 16 20
２ ３ ↑ ５ ９ 30 25 18 16 20 ↑ 20 25 18 16 30 18 16 20 25 ↑ 16 18 ↑ 结果： ２ ３ ３ ５ ９ 16 18 20 25 30
3.画出下面字符表的哈夫曼编码对应的二叉树。

解：课本P110 至底向上
4.印刷电路板将布线区域分为方格阵列，如下图所示。

电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案，布线时，电路只能沿直线或直角布线，已经布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。

用队列式分支限界法解该问题，在下图上标记出求解过程中各个方格的标记距离和最短布线路径。

5.算法设计。

说明：任意选择所使用的算法策略；从下面两个题目中任意选择其中之一；
要求：说明所使用的算法策略；写出算法实现的核心部分。

（1）背包问题；（2）哈夫曼编码问题；（3）n后问题。