文档库

最新最全的文档下载
当前位置:文档库 > 武汉大学计算机学院《算法设计与分析》考试试卷

武汉大学计算机学院《算法设计与分析》考试试卷

武汉大学计算机学院

2007---2008学年第一学期2005级

《算法设计与分析》考试试卷(A)

1、(10分)证明:若f?(n)=O(g?(n)), f?(n)=O(g?(n)),则有:

f?(n)* f?(n)= O(g?(n))* O(g?(n))

2、(10分)设f(n)为单调递减函数,利用不等式

武汉大学计算机学院《算法设计与分析》考试试卷

证明:= O(log n)。

3、(10分)用归纳法证明递归关系:

武汉大学计算机学院《算法设计与分析》考试试卷

T(n

的解为T(n)=,n=0,1,2….

4、(10分)试用RadixSort算法对下面数组进行排序,写出排序的详细过程:

1455,5677,5323,8122,4901,6647,1123,8762

5、(10分)给定数组含25个元素的数组如下,利用SELECT算法求数组中第13小的元素,在应用SELECT算法时,要求每组含有的元素个数为7而不是5,另外,当元素个数是6时,直接求解:

8,33,17,51,57,49,35,11,25,37,14,2,3, 13,52,12,6,29,32,54,5,16,22,23,7

6、(12分)给定两个字符串X=(A,B,C,B,D,A,B)和Y=(B,D,C,A,B,A),考虑利用动态规划方法求解这两个字符串的最长公共子序列问题:

(1)利用动态规划算法求出上述两个字符串的最长公共子序列,要求写出动态规划方程和详细的求解过程,不需要写出具体的算法;

(2)请给出一个最长公共子序列的表达式,并说明你的依据。

7、(12分)假设有一个包含100,000个字符的数据文件要压缩存储,各字符