算法设计期中试卷

选择题：(每题2分，共30分)

1.

衡量一个算法好坏的标准是（ C ）。

A.运行速度快 B.占用空间少 C.时间复杂度低 D.代码短 2.

当输入规模为n时，算法增长率最快的是（ C ）。

2

A.12n B. 100log2n C.2n3.

渐进算法分析是指（ B ）。

D.3nlog3n

A. 算法在最好情况、最坏情况和平均情况下的代价

B. 当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析 C. 数据结构所占用的空间

D. 在最小输入规模下算法的资源代价 4.

当上下限表达式相等时，我们使用下列（ C ）来描述算法代价？

A.大O 表示法 B.大Ω 表示法

C.θ表示法 D.小o表示法 5.

二分搜索算法是利用（ A ）实现的算法。

A.分治策略 B.动态规划法 C.贪心法 D.回溯法 6.

下列不是动态规划算法基本步骤的是（ A ）。 A.找出最优解的性质 B.构造最优解 C.算出最优解 D.定义最优解 7.

动态规划算法的基本要素为（ C ）。 A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 8.

能采用贪心算法求最优解的问题，一般具有的重要性质为（ A ）。 A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用

1

9. 备忘录方法是那种算法的变形。（ B ）。

A．分治法

B.动态规划法 C.贪心法

D.回溯法

10. 实现大整数乘法利用的算法是（ A ）。

A.分治策略

B.动态规划法

C.贪心法

D.回溯法

11. 使用分治法求解不需要满足的条件是（ A ）。

A. 子问题必须是一样的 B. 子问题不能够重复 C. 子问题的解可以合并

D. 原问题和子问题使用相同的方法解

12. 贪心算法与动态规划算法的主要区别是（ B ）。

A.最优子结构 B.贪心选择性质 C.构造最优解 D.定义最优解 13. 实现最长公共子序列利用的算法是（ B ）。 A.分治策略

B.动态规划法

C.贪心法 D.回溯法

14. 使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索

总共需要比较的次数是（ A ）。

A.10 B.11 C.500 D.1000 15. 关于0-1背包问题以下描述正确的是（ D ）。 A. 可以使用贪心算法找到最优解 B. 能找到多项式时间的有效算法

C. 使用动态规划算法可求解任意0-1背包问题

D. 对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做 0-1背包问题

二、 填空题：(每空1分，共10分)

1.

一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此

算法的复杂性有 时间 复杂性和 空间 复杂性之分。 2. 3.

一个直接或间接调用自身的算法称为 递归 算法。

出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这

些子问题的规模都大致 相等 。 4. 5.

大整数乘积算法是用 分治法 来设计的。 快速排序算法的性能取决于 划分的对称性 。

2

6.

已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：

解此递归方程可得T(n)=O（ nlogn ）。 7. 8. 9.

递归通常用 栈 来实现。

最优二叉搜索树即是 最小平均路长 二叉搜索树。 任何可用计算机求解的问题所需的时间都与其 规模 有关。

三、 简答题：（每小题10分，共30分）

1. 简述归动态规划算法的基本步骤，以及动态规划算法与分治法的异同。 设计动态规划算法的主要步骤为：（4分）

（1）找出最优解的性质，并刻划其结构特征。 （2）递归地定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（3分）

两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。（3分）

2. 与顺序查找算法相比，二分查找算法的时间复杂性有多大程度的降低？它是如何提

高算法的效率的？有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功？

答：顺序查找的时间是O(n)，折半查找O(log n) 降低了一个数量级。采用分治策略，每一次比较可以排除一半的数据。共需要比较4次才能找到82.

3. 简述归并排序算法和快速排序算法的分治方法。并对下列实例数据

A=(38,27,55,50,13,49,65)排序，写出采用快速排序算法，数组A第一次被分割的过程。

答：归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。

数组A第一次被分割的过程如下： 38 27 55 50 13 49 65

3

13 27 55 50 38 49 65

13 7 38 50 55 49 65

四、 算法分析题：（每题10分，共30分）

1. 有16个选手参加循环赛，循环赛一共进行15天，每个选手必须与其他的 15个选

手各赛一场，每个选手一天只比赛一次；设计一个满足上述要求的比赛日程表，并简述采用的算法基本思路。

2. 对于矩阵连乘所需最少数乘次数问题，其递归关系式为：

其中m[i,j]为计算矩阵连乘Ai?Aj所需的最少数乘次数，pi-1为矩阵Ai的行，pi为矩阵的列。现有四个矩阵，其中各矩阵位数分别为：

A1 50?10 p0?p1 A2 10?40 p1?p2 A3 40?30 P2?p3 A4 30?5 p3?p4 (1) 在这个四矩阵连乘积问题中，请问不同子问题的个数总共有多少个？并请把所有的

子问题列出来。

(2) 请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。要

求写出求解过程，并将结果填入m[4][4]。

3. 请用动态规划解下列0-1背包问题，写出递归式及求解过程。共有4个物品，背包

重量C=5，下表中列出每个物品的重量和价值。

物品 1

重量（公斤） 价值（美元） 2 4

12