《算法分析与设计》2016年11月考试人大网校考前练习题.docVIP

算法分析与设计2016年11月考试考前练习题一、简答题1. 算法设计通常有哪些方法？（至少列出4种）并指出哪些算法具有的某个共有性质。解答:算法设计方法有分治算法，贪心算法，动态规划算法，归纳算法，回溯算法，分支限界算法等。分治算法，贪心算法，动态规划算法等算法都具有最优子结构性质。 2. Fibonacci数列如下定义：（1）请设计一个递归算法，计算F(n)。（2）分析算法的时间复杂性。解答:（1）int fibonacci(int n) If(n = 1)return 1; return fibonacci(n-1)+fibonacci(n-2); （2）T(n)=T(n-1)+T(n-2)。3. 动态规划算法的两大基本要素分别是？解答:最优子结构性质和子问题的重叠性质。4. 简述设计动态规划算法的主要步骤。解答:（1）找出最优解的性质，并刻划其结构特征（2）递归地定义最优值（3）以自底向上的方式计算出最优值（4）根据计算最优值时得到的信息，构造最优解。5. 给定如下顺序搜索算法： int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; 则最坏时间复杂性和最好时间复杂性分别是多少？解答:最坏时间复杂性是O(n)，最好时间复杂性是O(1)。6. 用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）为多少？Bool Color:OK(int k)/ for(int j=1;j=n;j+)if(akj= =1)&(xj= =xk) return false;return true;解答:O(mn)7. 下面程序段的所需要的计算时间为（ ）。int MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(int i=1;i=n;i+) int thissum=0;for(int j=i;jsum)sum=thissum;besti=i;bestj=j;return sum;解答:O(n2)8. 简述什么是稳定的排序算法？解答:如果一个排序算法保留了等值元素在输入中的相对顺序，它就被称为是稳定的。9. 算法设计的质量指标。解答:正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。10. 对下图中的有向图，应用Dijkstra算法计算从源顶点4到其它顶点间最短路径的过程。解答:11. 为什么用分治法设计的算法一般有递归调用？解答:子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。12. 简述动态规划方法所运用的最优化原理。解答:最优化原理用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，Dn也是最优的。13. 简述归并排序算法的分治方法。解答:归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。14. 简述回溯法与分支限界法的相同点。解答:分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。15. 什么是贪心选择性质和最优子结构性质？解答:当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。二、算法分析解答题1. 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，并且在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间和一个结束时间,且。如果选择了活动i，则它在半开时间区间，内占用资源。若区间，与区间，不相交，则称活动i与活动j是相容的。a）给出活动i与活动j是相容的定义。b）描述求解活动安排问题的贪心算法，并分析算法的时间复杂性。解答:a）若区间，与区间，不相交，则称活动i与活动j是相容的。b）void GreedySelector(int n, Type s, Type f, bool A) sort(s,f,n);/按照活动的结束时间的非降序排列。 A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 算法中，如果活动按照其结束时间的非降序排列，则其时间复杂性是O(n)；如果没有排序，则要考虑为n个活动排序所需要的时间，则其时间复杂性是O(nlogn)。2. O(1)空间子数组换位算法：设a0:n-1是一个n维数组，k(1 k n-1)是一个非负整数。试设计一个算法将子数组a0 : k-1与ak+1 : n-1换位。要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。解答:解： 3次反转算法：将数组ai : j反转的算法 void reverse(int a, int i, int j) while (im then output no solution; return /无解，返回end if end for k=1; xk=1 /在第1站加满油。 s1=m /s1为用汽车的当前油量可行驶至的地点与A点的距离 i=2 while s