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

1算法设计与分析期末考试复习题1．算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?2．证明下面的关系成立：(参考例题1.5--1.6)（1）logn!=Θ(nlogn)(2)2n=Θ(2n+1)(3)n!=Θ(nn)(4)5n2-6n=Θ(n2)23.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1.voidsort(intA[],intn)2.{3.inti,j,temp;4.for(i=0;in-1;i++)5.for(j=i+1;jn;j++)6.if(A[j]A[i]){7.temp=A[i];8.A[i]=A[j];9.A[j]=temp;10.}11.}（1）什么时候算法所执行的元素赋值的次数最少？最少多少次？（2）什么时候算法所执行的元素赋值的次数最多？最多多少次？4.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1.voidbubblesort(intA[],intn)2.{3.intj,i,sorted;4.i=sorted=0;5.while(in-1&&!sorted){6.sorted=1;7.for(j=n-1;ji;j--){8.if(A[j]A[j-1]){9.temp=A[j];310.A[j]=A[j-1];11.A[j-1]=temp;12.sorted=0;13.}14.}15.i=i+1;16.}17.}（1）算法所执行的元素比较次数最少是多少次？什么时候达到最少？（2）算法所执行的元素比较次数最多是多少次？什么时候达到最多？（3）算法所执行的元素赋值次数最少是多少次？什么时候达到最少？（4）算法所执行的元素赋值次数最多是多少次？什么时候达到最多？（5）用О、和Ω记号表示算法的运行时间。（6）可以用Θ记号来表示算法的运行时间吗？请说明。45.解下面的递归方程：（1）f(n)=5f(n-1)-6f(n-2)f(0)=1f(1)=0（2）f(n)=4f(n-1)-4f(n-2)f(0)=6f(1)=86.初始链表的内容为：3562，6381，0356，2850，9136，3715，8329，7481，写出用基数排序算法对它们进行排序的过程。57.说明quick_sort算法对下面数组元素进行排序的工作原理。23，22，27，18，45，11，63，12，69，25，32，148．P133例4.10执行结果，具体过程请看课本。原图||||\/223321134154455执行结果图9.求如下背包问题的最优解：n=7,M=15,价值P={10，5，15，7，6，18，3}，重量为w={2，3，5，7，1，4，1}。610.用狄斯奎诺算法求解下图所示的单源最短路径问题。12345678910210967103848965411.用克鲁斯卡尔算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。712.用普里姆算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。13.把4个份额的资源分配给3项工程，给定利润表，如表6.3所示，写出资源的最优分配方案的求解过程。表6.34份资源分配给3项工程的利润表X01234G1(x)713161719G2(x)612141618G3(x)518192022814.有6个物体，其重量分别为5，3，7，2，3，4，价值分别为3，6，5，4，3，4。有一背包，载重量为15，物体不可分割。求装入背包的物体的最大价值，及其求解过程。15.有4个顶点的“货郎担”问题，其费用矩阵如图所示，求从顶点1出发，最后回到顶点1的最短路线。ABCDEFGHIJKLMNOP171234∞512653342423631552434232费用矩阵搜索树∞∞178∞5172∞6253∞916给定背包的载重量M=20；有6个物体，价值分别为11，8，15，18，12，6，重量分别为5，3，2，10，4，2。说明用回溯法求解上述0/1背包问题的过程。画出搜索树，节点按照生成顺序编号，并在节点旁边标出生成该节点时所执行动作的结果。17.有如下0/1背包问题，画出它们的搜索树，在节点旁边标出相应的上界；写出最后的最优解，及相应的最大价值。M=15，P={6，7，8，3，1}，w={5，7，10，5，2}