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

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

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

2、{7.temp=A[i];8.A[i]=A[j];149.A[j]=temp;10.}11.}（1）什么时候算法所执行的元素赋值的次数最少？最少多少次？（2）什么时候算法所执行的元素赋值的次数最多？最多多少次？4.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1.voidbubblesort(intA[],intn)2.{3.intj,i,sorted;4.i=sorted=0;145.while(ii;j--){8.if(A[

3、j]

4、的递归方程：（1）f(n)=5f(n-1)-6f(n-2)f(0)=1f(1)=014（2）f(n)=4f(n-1)-4f(n-2)f(0)=6f(1)=86.初始链表的内容为：3562，6381，0356，2850，9136，3715，8329，7481，写出用基数排序算法对它们进行排序的过程。147.说明quick_sort算法对下面数组元素进行排序的工作原理。23，22，27，18，45，11，63，12，69，25，32，14148．P133例4.10执行结果，具体过程请看课本。原图

5、

6、

7、

8、/223321134154

9、455执行结果图9.求如下背包问题的最优解：n=7,M=15,价值P={10，5，15，7，6，18，3}，重量为w={2，3，5，7，1，4，1}。1410.用狄斯奎诺算法求解下图所示的单源最短路径问题。1411.用克鲁斯卡尔算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。12.用普里姆算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。1413.把4个份额的资源分配给3项工程，给定利润表，如表6.3所示，写出资源的最优分配方案的求解过程。表6.34份资源分配给3项工程的利润表X01234G1(x

10、)713161719G2(x)612141618G3(x)5181920221414.有6个物体，其重量分别为5，3，7，2，3，4，价值分别为3，6，5，4，3，4。有一背包，载重量为15，物体不可分割。求装入背包的物体的最大价值，及其求解过程。1415.有4个顶点的“货郎担”问题，其费用矩阵如图所示，求从顶点1出发，最后回到顶点1的最短路线。∞∞178∞5172∞6253∞费用矩阵搜索树16给定背包的载重量M=20；有6个物体，价值分别为11，8，15，18，12，6，重量分别为5，3，2，10，4，2。说明用回溯法求解上

11、述0/1背包问题的过程。画出搜索树，节点按照生成顺序编号，并在节点旁边标出生成该节点时所执行动作的结果。1417.有如下0/1背包问题，画出它们的搜索树，在节点旁边标出相应的上界；写出最后的最优解，及相应的最大价值。M=15，P={6，7，8，3，1}，w={5，7，10，5，2}14