算法设计与分析期中考试试题.pdf

《算法设计与分析期中考试试题.pdf》由会员分享，可在线阅读，更多相关《算法设计与分析期中考试试题.pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、期中试题期中试题 一一、填空题填空题 1. 一 个 算 法 就 是 一 个 有 穷 规 则 的 集 合 ， 具 有 以 下 五 个 重 要 特性:_,_,_,_,_。 2. f(n)= 62n+n2，f(n)的渐进性态 f(n)= O( ) 3.动态规划算法的两个基本要素是_和_。 4.贪心算法的两个基本要素是_和_ 。 5.下面程序段的所需要的计算时间为_ 。 6.有 11 个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合） ，得到的最大相容活动子集合为活动_。 二二、算法填空算法填空 1

2、.1.最大子段和最大子段和: : 动态规划算法动态规划算法 int MaxSum(int n, int a) 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; 14 13 12 11 10 9 8 7 6 5 4 fi 12 2 8 8 6 5 3 5 0 3 1 Si 11 10 9 8 7 6 5 4 3 2 1 i int su

3、m=0, b=0； /sum 存储当前最大的 bj, b 存储 bj for(int j=1； j0) b+= aj ； else ； /一旦某个区段和为负，则从下一个位置累和 if(bsum) ; return sum； 2 2. .贪心算法求装载问题贪心算法求装载问题 template void Loading(int x, Type w, Type c, int n) int *t = new int n+1; ; for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; ; 3 3.

4、 .快速排序快速排序 template void QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); ; /对左半段排序 ; /对右半段排序 三、简答题 1、简单描述分治法的基本思想。 2、简述设计动态规划算法的主要步骤 四四、解答题解答题 1. 现 Hanoi 塔问题的递归方程为：h(n)2h(n1) 1h(1)1 ， 求 h(n)的非递归表达式。 2. 已知1( )*()iikkijr rAa，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50， r7=6， 求矩阵链积

5、A1A2A3A4A5A6的最佳求积顺序。 （要求：给出计算步骤） 3. 假设有 7 个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量 M150，如果使用贪心方法求解此背包问题，请回答： （1） 对各个物品进行排序时，依据的标准都有哪些？ （2） 使用上述标准分别对 7 个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。并比较上述解中哪个是最优的？ 4. 对于下图使用 Dijkstra 算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30