计算机学院2007－2008学年（下）学期期末考试试卷
《 算法设计与分析 》试卷（A）
专业 年级 ０６ 班级 姓名 学号
题号 得分
一、 简答题（每小题５分，共２０分）
１、如何理解算法的时间复杂度？如何区别表示算法渐近复杂度三个记号Ο、Ω、Θ？
２、什么是最优算法？请基于事实“以比较为基础的排序算法的时间下界是Ω(nlogn)”列举一个基于比较的最优排序算法。
３、图有宽度优先搜索和深度优先搜索算法。如果图用邻接矩阵来表示，那么这两种算法的时间复杂度是什么？如果图用邻接表来表示呢？
4、快速排序算法是根据分治策略来设计的，其基本思想是什么？快速排序算法的最坏及平均情况的时间复杂度分别是多少？
二、计算题（共１５分） 1、（7分）求解递推关系：
T(n)=6T(n−1) −9T(n−2), n=2；T(0)=T(1)=1。 2、（8分）证明：log1+log2+…+log n=Θ(nlogn)。
三、算法分析题（１０分）
考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下：如果n≤2就直接求解。否则，将序列等分成两个子序列A[1..n/2]和A[n/2+1..n]，分别找出这两子序列的最大最小元素x1,y1和x2,y2；然后据此求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。请给出该算法计算时间T(n)满足的递归方程，并解方程来确定算法的时间复杂度。假定n=2k（k为正整数）。
四、 归纳技术应用题（共１０分） １、（4分）简述基数排序算法的基本思路和算法时间复杂度； ２、（6分）考虑使用基数排序算法对下列８个数据进行排序，请给出中间排序的结果。
２７５６ ７３５２ ３７２５ ３７６２ ５２７３ ２３７５ ５７３２ ５６２７
五、 动态规划法应用题（共１５分）
考虑用动态规划法求解矩阵连乘M1M2M3M4M5的最优运算（即元素乘法次数最少）的次序，其中M1：5×6，M2：6×4，M3：4×8，M4：8×3，M5：3×5。 １、（5分）设 C[i,j]表示矩阵连乘MiMi+1…Mj按照最优次序运算所需要的元素乘法次数。请给出C[i,j]递推计算的公式。 2、（10分）根据递推公式填写下表，包括C[i,j]的值及对应的最优运算次序的加括号方式。
一
二 三 四 五 六 七 总分
- 1 -
C[1，1]＝0 M1
C[1，2]＝
C[2，2]＝
C[1，3]＝
C[2，3]＝
C[3，3]＝
C[1，4]＝
C[2，4]＝ C[3，4]＝ C[4，4]＝
C[1，5]＝
C[2，5]＝ C[3，5]＝ C[4，5]＝ C[5，5]＝
六、 贪心法应用题（共１０分） １、（4分）Prim算法是求最小生成树的贪心算法，请简述Prim算法的基本思想。
B ２、（6分）用Prim算法求下图的最小生成树。要求用图或表格15 展示25 20 主要计算过程。
20 C
G H 10 15 A 5 15 5 F D
10 5
E 七、 算法设计题（共２０分） １、（4分）简述设计回溯算法的基本步骤。２、（10分）在回溯法应用的综合性实验中，根据你做选做的题目，简要叙述你是如何用回溯法解决这个问题的（即给出求解该问题的回溯算法的几个要素）。3、（6分）本课程中学习了分治法、贪心法、动态规划法、回溯法等设计算法的基本策略，在解决问题时应如何选用这些策略设计算法？结合实验谈谈体会。
- 2 -
计算机学院2007－2008学年（下）学期期末考试试卷
《 算法设计与分析 》试卷（B）
专业 年级 ０６ 班级 姓名 学号
题号 得分
一、简答题（每小题５分，共２０分）
1、算法A的计算时间Ｔ1(n)满足递归关系式：T1 (n)=3T1 (n-1)+1，, n>1；;T1 (1)=1。算法B的计算时间Ｔ2(n)= 2n3+1000nlog10n+100n。请使用记号Θ分别表示T1 (n)和T2 (n)。 2、设G=〈 V,E〉是无向图，n=|V|，m=|E|，且m=O(n1.99)。如果要求图G的最小成生树，你愿意选择哪一个算法： Prim算法还是Kruskal算法？为什么？ ３、在有向图的深度优先搜索中，边被分为哪几类？
4．设A[1..n]是元素取值于区间[1..2n]的整型数组，考虑对A进行排序。你认为归并排序算法 MERGERSORT和基数排序算法RADIXSORT哪一个可能更快？简述原因。 二、 计算题（共１５分） １、（7分）求解递推关系：
T(n)=3T(n−1)+4T(n−2),n=2；T(0)=1,T(1)=2。 2、（8分）证明：对于任意正整数k有1k+2 k +…+nk =Θ(nk+1)。
三、算法分析题（共１０分）
考虑求下列数列的通项an：a0=0，a1=1，an=an-1+an-2（n>1）。下面是使用C语言表示的递归算法： int A(int n)
{ if (n= =0) return 0; if (n= =1) return 1;
else return A(n−1)+A(n−2); } １、（5分）分析算法的时间复杂度。 2、（5分）你能够改进算法使得用Θ(n)时间即可求出FA(n)吗？简述你的改进办法。 四、（共１０分）考虑在8个元素的集合A(1:8)=(10, 35, 5, 40, 20, 25, 30, 15)中找最大和最小元素。 1、（６分）说明用分治法求解此问题的基本思路，并画出求解过程； 2、（４分）分析求解过程中所作的元素比较次数，并将这一结果与直接求解法所需作的元素比较次数进行对比。 五、（共１５分）请使用动态规划法求解下列0-1背包问题实例：n=4个物品，大小分别为W={2,3,4,6}，价值分别为P={3,6,5,9}，背包容量为M=10。
- 3 -
一 二 三 四 五 六 七 总分
1、（５分）请给出递推计算公式。 2、（１０分）根据递推计算公式用表格展示出计算过程，并给出最优结果。 六、（共１０分）考虑用哈夫曼算法来找字符a,b,c,d,e,f的最优编码。这些字符出现在文件中的频数之比为 20:10:6:4:44:16。要求： 1、（４分）简述使用哈夫曼算法构造最优编码的基本步骤； 2、（６分）构造对应的哈夫曼树，并据此给出a,b,c,d,e,f的一种最优编码。
七、算法设计题（共２０分） １、（４分）请给出设计回溯算法的主要步骤。 2、（１０分）考虑使用回溯法解4皇后问题，解空间取为由1,2,3,4的4!种排列所组成。要求：用文字描述定义剪枝操作；画出用回溯算法找出一个解所产生的部分搜索树，并写出这个解。 3、（６分）本课程中我们学习了分治法、贪心法、动态规划法、回溯法等几种设计算法的基本策略，在解决实际问题时应如何来选用这些策略来进行算法设计？谈谈你的体会。可以结合所做过的实验情况来谈。
- 4 -