算法设计与分析复习题

《算法设计与分析复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析复习题1一个算法应有哪些主要特征？另附资料2分治法（DivideandConquer）与动态规划（DynamicProgramming）有什么不同？另附资料3试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。另附资料4编写一个递归算法求解Hanoi塔问题。VoidHanoi(intn,intfirst,intsecond,intthird){If(n==1)Move(first,third);Else{Hanoi(n-1,first,third,second);Move(first,third);Hanoi(n-1,second,

2、first,second);}}5求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。6求解方程T(n)=2T(n/2)+1，T(1)=1，设n=2k。7求解方程T(n)=aT(n/b)+n，T(1)=1，设n=2k。另附资料8编写一个QuickSorting算法，并分析时间复杂性。9利用QuickSorting的原理，编写一个查找第k小元素的算法。10编写一个HeapSorting算法，并分析时间复杂性。另附资料上有部分具体实现代码：11证明O(nlogn)是“比较”排序算法时间复杂性的下界。证明O(nlogn)是“比较”排序算法时间

3、复杂性的下界。为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。具有L片树叶的二叉树的深度至少是logL。所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。而log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1>=

4、logn+log(n-1)+log(n-2)+...+log(n/2)>=(n/2)log(n/2)>=(n/2)logn-n/2=O(nlogn)所以只用到比较的排序算法最低时间复杂度是O(nlogn)。赞12编写一个Radix算法对n个相同长度的整数排序。intmaxbit(intdata[],intn)//辅助函数，求数据的最大位数　　{　　intd=1;//保存最大的位数　　intp=10;　　for(inti=0;i=p)　　{　　p*=10;　　++d;　　}　　}　　returnd;　　}

5、　　　voidradixsort(intdata[],intn)//基数排序　　{　　intd=maxbit(data,n);　　int*tmp=newint[n];　　int*count=newint[10];//计数器　　inti,j,k;　　intradix=1;　　for(i=1;i<=d;i++)//进行d次排序　　{　　for(j=0;j<10;j++)　　count[j]=0;//每次分配前清空计数器　　for(j=0;j

6、}　　for(j=1;j<10;j++)　　count[j]=count[j-1]+count[j];//将tmp中的位置依次分配给每个桶　　for(j=n-1;j>=0;j--)//将所有桶中记录依次收集到tmp中　　{　　k=(data[j]/radix)%10;　　tmp[count[k]-1]=data[j];　　count[k]--;　　}　　for(j=0;j

7、3编写一个算法，可以检测一个字符串是否回文（如：afaddafa，abwba等）。14如果是检测一个字符串中是否包含一个回文子串，应如何编写算法。如果是找最大的回文子串呢？15设n个不同的整数排好序后存在数组T[1：n]中。若存在一个下标i，使得T[i]=i，设计一个有效的算法找到该下标。要求时间复杂性是O(logn)。16编写一个采用KMP的算法查找T的子串P，并判断匹配失败的字符是否在P中，以此确定可滑动的最大距离。17编写一个算法找出2个正文中的最长公共子序列，若要找出3个正文中的最长公共子序列，应如何编写算法。18编写一个求解8后问题的算法，并作

8、出时间复杂性分析。19试分析回溯法与分支定界法的异同之处。20采用分支定界法编写