算法设计与分析复习题

算法

算法设计与分析复习题

1、 一个算法应有哪些主要特征？

2、 分治法（Divide and Conquer）与动态规划（Dynamic Programming）有什么不同？

3、 试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。

4、 求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。

5、 求解方程T(n)=2T(n/2)+1，T(1)=1，设n=2k。

6、 编写一个Quick Sorting 算法，并分析时间复杂性。

7、 利用Quick Sorting的原理，编写一个查找第k小元素的算法。

8、 编写一个Heap Sorting算法，并分析时间复杂性。

9、 编写一个算法，可以检测一个字符串是否回文（如：afaddafa，abwba等）。

10、 如果是检测一个字符串中是否包含一个回文子串，应如何编写算法。如果是

找最大的回文子串呢？

11、 设n个不同的整数排好序后存在数组T[1：n]中。若存在一个下标i，使得T[i]=i，

设计一个有效的算法找到该下标。要求时间复杂性是O(logn)。

12、 编写一个采用KMP的算法查找T的子串P，并判断匹配失败的字符是否在P

中，以此确定可滑动的最大距离。

13、 考虑一个“模糊”的算法查找T的子串P，先快速找到与P相似的子串，再

进一步确认之。

14、 设计一个算法确定K个矩阵相乘的最优次序，并分析该算法的时间复杂性。

15、 设计一个算法从数A[1：n]中同时找出最大元素和最小元素，只需要不超过

1．5n－2次比较。

16、 用分治法一个算法从数A[1：n]中同时找出最大元素，分析算法的时间复杂

性，并思考为什么是这样的结果。

17、 在一个数组中出现次数最多的元素称为“众数”，编写一个找出众数的算法，

并分析算法时间复杂性。

18、 设计一个使用Hash法的算法在数组中找出“众数”，并分析时间复杂性。

19、 设计一个时间复杂性不超过O(n2)的算法，找出n个数组成的序列中最长的单

调递增序列。

20、 从1，2， ，n中找出所有质数，设计一个比较优的算法。

21、 测试一个图是否连通图，可以用深度优先搜索算法或宽度优先搜索算法，在

什么情况下，用哪种算法更好一些？