算法设计与分析期末复习题

1、算法设计与分析期末考试复习题1 算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?2 证明下面的关系成立：(参考例题1.5-1.6)（1）logn!=(nlogn) (2)2n=(2n+1)(3) n!= (nn) (4)5n2-6n=(n2)3.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1. void sort(int A,int n)2. 3.int i,j,temp;4.for(i=0;in-1;i+)5.for(j=i+1;jn;j+)6.if(AjAi) 7.temp=Ai;8.Ai=Aj;9.Aj=temp;10.11. （1） 什么时

2、候算法所执行的元素赋值的次数最少？最少多少次？（2） 什么时候算法所执行的元素赋值的次数最多？最多多少次？4.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1. void bubblesort(int A,int n)2. 3.int j,i,sorted;4.i=sorted=0;5.while(ii;j-) 8.if(AjAj-1) 9.temp=Aj;10.Aj=Aj-1;11.Aj-1=temp;12.sorted=0;13.14.15.i=i+1;16.17. （1） 算法所执行的元素比较次数最少是多少次？什么时候达到最少？（2） 算法所执行的元素比较次数最多是多

3、少次？什么时候达到最多？（3） 算法所执行的元素赋值次数最少是多少次？什么时候达到最少？（4） 算法所执行的元素赋值次数最多是多少次？什么时候达到最多？（5） 用、和记号表示算法的运行时间。（6） 可以用记号来表示算法的运行时间吗？请说明。5.解下面的递归方程： （1）f(n)=5f(n-1)-6f(n-2) f(0)=1 f(1)=0 （2）f(n)=4f(n-1)-4f(n-2) f(0)=6 f(1)=86.初始链表的内容为：3562，6381，0356，2850，9136，3715，8329，7481，写出用基数排序算法对它们进行排序的过程。7.说明quick_sort算法对下面数组元

4、素进行排序的工作原理。 23，22，27，18，45，11，63，12，69，25，32，148P133例4.10执行结果，具体过程请看课本。 原图 | | / 2 23321134 154455 执行结果图9.求如下背包问题的最优解：n=7,M=15,价值P=10，5，15，7，6，18，3，重量为w=2，3，5，7，1，4，1。10.用狄斯奎诺算法求解下图所示的单源最短路径问题。 11.用克鲁斯卡尔算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。12.用普里姆算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。13.把4个份额的资源分配给3项工程，给定利润表，如

5、表6.3所示，写出资源的最优分配方案的求解过程。 表6.3 4份资源分配给3项工程的利润表X 0 1 2 3 4 G1(x) 7 13 16 17 19 G2(x) 6 12 14 16 18 G3(x) 5 18 19 20 22 14.有6个物体，其重量分别为5，3，7，2，3，4，价值分别为3，6，5，4，3，4。有一背包，载重量为15，物体不可分割。求装入背包的物体的最大价值，及其求解过程。15.有4个顶点的“货郎担”问题，其费用矩阵如图所示，求从顶点1出发，最后回到顶点1的最短路线。 1 7 8 5 1 7 2 6 2 5 3 费用矩阵 搜索树16给定背包的载重量M=20；有6个物体，价值分别为11，8，15，18，12，6，重量分别为5，3，2，10，4，2。说明用回溯法求解上述0/1背包问题的过程。画出搜索树，节点按照生成顺序编号，并在节点旁边标出生成该节点时所执行动作的结果。17