文本内容:
《算法设计与分析》期中试卷
1、叙述分治算法的基本思想及一般算法设计模式;
2、叙述动态规划算法的基本步骤及动态规划算法的基本要素;
3、改进课本P74的Lcs算法,使改进算法不用数组b亦可在O(m+n)的时间内构造最长公共序列;
4、求下列函数的渐近表达式
1.3n2+10n
2.n2/10+2n321+1/n4logn3510log3n
5、对于下列各组函数发f(n)和g(n),确定f(n)=O(gn)或者f(n)=W(gn)或者f(n)=θ(gn),并简述理由
1.f(n)=logn2gn=logn+5;
2.f(n)=logn2gn=√n;3f(n)=ngn=logn2;
4.f(n)=nlogn+ngn=logn;
5.f(n)=
10.gn=log10;
6.f(n)=log2ngn=logn
7.f(n)=2ngn=3n;
8.f(n)=2ngn=100n2;
6、设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当搜索元素x不再数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j当搜索元素在数组中时,i和j相同,均为x在数组中的位置
7、设a[0:n-1]是有n个元素的数组,k(0=k=n-1)是非负整数试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位要求算法在最坏的情况下耗时On且只用到O1的辅助空间
8、在一个由元素组成的表中出现次数最多的元素称为众数试写一个寻找众数的算法,并分析其计算复杂性
9、设计一个On2时间的算法,找出由n个数组成的序列的最长单调递增子序列
10、给定n中物品和一背包,物品i的重量是ω,体积是bi,其价值为vi,背包的容量为C,容积为D问应该如何选择装入背包中的物品,使得装入背包中的物品的总价值最大?在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包,不能将物品i装入背包多次,也不能只装入部分的物品i试设计一个解此问题的动态规划算法,并分析算法的计算复杂性。