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

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

1． 算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?

2． 证明下面的关系成立：(参考例题1.5--1.6)

（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)

(3)n!= Θ(nn) (4)5n2-6n=Θ(n2)

1

3.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void sort(int A[],int n) 2. { 3. int i,j,temp; 4. for(i=0;i

（1） 什么时候算法所执行的元素赋值的次数最少？最少多少次？

（2） 什么时候算法所执行的元素赋值的次数最多？最多多少次？

4.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void bubblesort(int A[],int n) 2. { 3. int j,i,sorted; 4. i=sorted=0; 5. while(ii;j--) { 8. if(A[j]

2

10. 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） 可以用Θ记号来表示算法的运行时间吗？请说明。

3

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)=8

6.初始链表的内容为：3562，6381，0356，2850，9136，3715，8329，7481，写出用基数排序算法对它们进行排序的过程。

4

7.说明quick_sort算法对下面数组元素进行排序的工作原理。 23，22，27，18，45，11，63，12，69，25，32，14

8．P133例4.10执行结果，具体过程请看课本。

原图 ||

|| \\/ 2 2 3 3 2 4 4 1 4 1 5 3 5 5 1 执行结果图

9.求如下背包问题的最优解：n=7,M=15,价值P={10，5，15，7，6，18，3}，重量为w={2，3，5，7，1，4，1}。

5

10.用狄斯奎诺算法求解下图所示的单源最短路径问题。

210913610348776654958910482

11.用克鲁斯卡尔算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。

6

12.用普里姆算法求图5.15的最小花费生成树，画出最小花费生成树的生成过程。

13.把4个份额的资源分配给3项工程，给定利润表，如表6.3所示，写出资源的最优分配方 案的求解过程。

表6.3 4份资源分配给3项工程的利润表 X 0 1 2 3 4 G1(x) G2(x) G3(x)

7

7 6 5 13 12 18 16 14 19 17 16 20 19 18 22

14.有6个物体，其重量分别为5，3，7，2，3，4，价值分别为3，6，5，4，3，4。有一背包，载重量为15，物体不可分割。求装入背包的物体的最大价值，及其求解过程。

15.有4个顶点的“货郎担”问题，其费用矩阵如图所示，求从顶点1出发，最后回到顶点1的最短路线。

1A713C1F33L2G14M264H52N2I53O54D33J22P∞2B∞ ∞ 1 7 8 ∞ 5 1 7 2 ∞ 6 2 5 3 ∞

3E64K54 费用矩阵 搜索树

8

16给定背包的载重量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}

9

本文来源：https://www.bwwdw.com/article/mmoo.html