算法分析与设计试题.doc

一、 选择题（20分）1最长公共子序列算法利用的算法是（B ）。A、分支界限法B、动态规划法C、贪心法D、回溯法2实现棋盘覆盖算法利用的算法是（A ）。A、分治法B、动态规划法C、贪心法D、回溯法3.下面是贪心算法的基本要素的是（C ）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解4.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数 B. 计算约束函数的时间 C. 计算限界函数的时间 D. 确定解空间的时间5.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ）A递归函数B.剪枝函数 C。随机数函数D.搜索函数6采用最大效益优先搜索方式的算法是（A ）。A、分支界限法B、动态规划法C、贪心法D、回溯法7贪心算法与动态规划算法的主要区别是（B ）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解8. 实现最大子段和利用的算法是（B ）。A、分治策略B、动态规划法C、贪心法D、回溯法9.优先队列式分支限界法选取扩展结点的原则是（C ）。A、先进先出B、后进先出C、结点的优先级D、随机10.下列算法中通常以广度优先方式系统搜索问题解的是（A ）。A、分支限界法B、动态规划法C、贪心法D、回溯法二、填空题（22分 每空2分）1.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、确定性和 有限性 四条性质。2、大整数乘积算法是用 分治法 来设计的。3、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。4、舍伍德算法总能求得问题的 一个解 。5、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。6.快速排序templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /对左半段排序 QuickSort (a,q+1,r); /对右半段排序 7. 哈密顿环问题的算法可由 回溯法 设计实现。 8.贪心算法 不一定 产生最优解。9.算法中通常以深度优先方式系统搜索问题解的是 回溯法 。三、 算法设计与分析（25分）1.用欧几里德迭代算法求两个数的最小公倍数（10分）#includeusing namespace std;int Gcd(int m,int n)if(m=0)return n;if(n=0)return m;int t=mn?n:m;while(m%t|n%t)t-;return t;int main()int a,b;coutInput a & b (0=aab;int m=a*b/Gcd(a,b);coutThe Least Common Multiple is:mendl;return 0;2、试用动态规划算法实现最大子矩阵和问题：求矩阵A的一个子矩阵，使其各元素之各为最大。（15分）解：解答如下：int MaxSum2(int m,int n,int *a) int sum=0;int *b=new intn+1;for(int i=1;i=m;i+) for(int k=1;k=n;k+) bk=0; .（5分） for(int j=i;j=m;j+) for(int k=1;ksum) sum=max; return sum; .（10分） int MaxSum(int n,int *a) int sum=0,b=0; for(int i=1;i0) b+=ai; else b=ai; if(bsum) sum=b;Return sum; .（15分）四、简答题（33分）1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M150，如果使用贪心方法求解此背包问题，使收益最大，请写出求解过程请写出求解过程。（10分）物品ABCDEFG重量35306050401025价值10403050354030解：使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。2. 写出分治算法MaxMin算法对下列实例中找最大数和最小数的过程。（10分）数组 A=(48,12,61,3,5,19,32,7) 解：1、 48,12,61,3, 5,19,32,7 表中元素多于二， 对半分割2、48,12 61,3 5,19 32,7 表中元素多于二， 对半分割3、 4861, 123 1932，57求前半部分的最大最小和后半部分的最大最小，两个半部分的大者为最大，小者为最小4、 6132 35 两个半部分的大者为最大，小者为最小5、 61 3 寻找结束3. 写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。（13分）52 4 8 4 3 8631 5 4 5 2 2 1 674各边的代价如下：C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1C(5,8)=4， C(6,8)=5 ，C(7,8)=6解 ：Cost(4,8)=0Cost(3,7)= C(7,8)+0=6 ，Cost(3,6)= C(6，8)+0=5, Cost(3,5)= C(5，8)+0=4 Cost(2,4)= minC(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5) = min1+ 5, 2+4=6 Cost(2,3)= minC(3，6)+ Cost(3,6) = min4+5=9 Cost(2,2)= minC(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7) = mi