计算机学院 2007－2008 学年（下）学期期末考试试卷 《 算法设计与分析 》试卷（A） 专业 年级 06 班级 姓名 学号 题号 一 得分 二 三 四 五 六 七 总分 一、 简答题（每小题 5 分，共 20 分） 1、如何理解算法的时间复杂度？如何区别表示算法渐近复杂度三个记号O 、W 、Q ？ 2、什么是最优算法？请基于事实“以比较为基础的排序算法的时间下界是W 一个基于比较的最优排序算法。 3、图有宽度优先搜索和深度优先搜索算法。如果图用邻接矩阵来表示，那么这两种算法的 (nlogn)”列举 时间复杂度是什么？如果图用邻接表来表示呢？ 4、快速排序算法是根据分治策略来设计的，其基本思想是什么？快速排序算法的最坏及平 均情况的时间复杂度分别是多少？ 二、计算题（共 15 分） 1、（7 分）求解递推关系： T(n)=6T(n-1) -9T(n-2), n=2；T(0)=T(1)=1。 (nlogn)。 2、（8 分）证明：log1+log2+… +log n=Q 三、算法分析题（10 分） 考虑在序列 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 为正整数）。 四、 归纳技术应用题（共 10 分） 1、（4 分）简述基数排序算法的基本思路和算法时间复杂度； 2、（6 分）考虑使用基数排序算法对下列8 个数据进行排序，请给出中间排序的结果。 2756 7352 3725 3762 5273 2375 5732 5627 五、 动态规划法应用题（共 15 分） 考虑用动态规划法求解矩阵连乘 M1M2M3M4M5 的最优运算（即元素乘法次数最少）的 次序，其中 M1：5· 6，M2：6· 4，M3：4· 8，M4：8· 3，M5：3· 5。 1、（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[1，5]＝ C[2，5]＝ C[3，4]＝ C[3，5]＝ C[4，4]＝ C[4，5]＝ C[5，5]＝ A 5 D 5 E 10 15 20 15 H F 10 15 B C 25 展 示 六、 贪心法应用题（共 10 分） 1、（4 分）Prim 算法是求最小生成树的贪心算法，请简述 Prim 算法的基本思想。 2、（6 分）用 Prim 算法求下图的最小生成树。要求用图或表格 主要计算过程。 七、 算法设计题（共 20 分） 1、（4 分）简述设计回溯算法的基本步骤。2、（10 分）在回溯法应用的综合性实验中，根据 你做选做的题目，简要叙述你是如何用回溯法解决这个问题的（即给出求解该问题的回溯算 法的几个要素）。3、（6 分）本课程中学习了分治法、贪心法、动态规划法、回溯法等设计 算法的基本策略，在解决问题时应如何选用这些策略设计算法？结合实验谈谈体会。 - 2 - 20 G 5 

计算机学院 2007－2008 学年（下）学期期末考试试卷 《 算法设计与分析 》试卷（B） 专业 年级 06 班级 姓名 学号 题号 一 得分 二 三 四 五 六 七 总分 一、简答题（每小题 5 分，共 20 分） 1、算法 A 的计算时间Ｔ1(n)满足递归关系式：T1 (n)=3T1 (n-1)+1，, n>1；;T1 (1)=1。算法 B 的计算时间Ｔ2(n)= 2n3+1000nlog10n+100n。请使用记号Q 分别表示 T1 (n)和 T2 (n)。 2、设 G=Æ V,Eæ 是无向图，n=|V|，m=|E|，且 m=O(n1.99)。如果要求图 G 的最小成生树，你愿 意选择哪一个算法： Prim 算法还是 Kruskal 算法？为什么？ 3、在有向图的深度优先搜索中，边被分为哪几类？ 4．设 A[1..n]是元素取值于区间[1..2n]的整型数组，考虑对 A 进行排序。你认为归并排序算 法 MERGERSORT 和基数排序算法 RADIXSORT 哪一个可能更快？简述原因。 二、 计算题（共 15 分） 1、（7 分）求解递推关系： T(n)=3T(n- 1)+4T(n- 2),n=2；T(0)=1,T(1)=2。 2、（8 分）证明：对于任意正整数 k 有 1k+2 k +…+n k =Q 三、算法分析题（共 10 分） (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); (n)时间即可求出FA(n)吗？简述你的改进办法。 } 1、（5 分）分析算法的时间复杂度。 2、（5 分）你能够改进算法使得用Q 四、（共 10 分）考虑在 8 个元素的集合 A(1:8)=(10, 35, 5, 40, 20, 25, 30, 15)中找最大和最小 元素。 1、（6 分）说明用分治法求解此问题的基本思路，并画出求解过程； 2、（4 分）分析求解过程中所作的元素比较次数，并将这一结果与直接求解法所需作的元素 比较次数进行对比。 五、（共 15 分）请使用动态规划法求解下列 0-1 背包问题实例：n=4 个物品，大小分别为 W={2,3,4,6}，价值分别为 P={3,6,5,9}，背包容量为M=10。 - 3 - 

1、（5 分）请给出递推计算公式。 2、（10 分）根据递推计算公式用表格展示出计算过程，并给出最优结果。 六、（共 10 分）考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码。这些字符出现在文件中 的频数之比为 20:10:6:4:44:16。要求： 1、（4 分）简述使用哈夫曼算法构造最优编码的基本步骤； 2、（6 分）构造对应的哈夫曼树，并据此给出a,b,c,d,e,f 的一种最优编码。 七、算法设计题（共 20 分） 1、（4 分）请给出设计回溯算法的主要步骤。 2、（10 分）考虑使用回溯法解 4 皇后问题，解空间取为由 1,2,3,4 的 4!种排列所组成。要求： 用文字描述定义剪枝操作；画出用回溯算法找出一个解所产生的部分搜索树，并写出这个解。 3、（6 分）本课程中我们学习了分治法、贪心法、动态规划法、回溯法等几种设计算法的基 本策略，在解决实际问题时应如何来选用这些策略来进行算法设计？谈谈你的体会。可以结 合所做过的实验情况来谈。 - 4 -