《2014-2015算法设计与分析考试题》由会员分享，可在线阅读，更多相关《2014-2015算法设计与分析考试题（9页珍藏版）》请在金锄头文库上搜索。
1、2014-2015 学期算法设计与分析试题1. 一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特 殊类型问题的一系列运算，此外，算法还应具有以下五个重要特 性:,。2. 算法的复杂性有和之分，衡量一个算法好坏的标准是。3. 某 一 问 题 可 用 动 态 规 划 算 法 求 解 的 显 著 特 征 是4. 若序列 X二B,C,A,D,B,C,D, Y二A,C,B,A,B,D,C,D，请给出序列 X和 Y 的一个最长公共子序列。5. 用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含。6. 动 态 规 划 算 法 的 基 本 思 想 是 将 待 求 解 问 题 分 解 成
2、 若 干，先求解，然后从这些的 解得到原问题的解。7. 以深度优先方式系统搜索问题解的算法称为。8. 0-1背包问题的回溯算法所需的计算时间为,用动态规划算法所需的计算时间为。9. 动态规划算法的两个基本要素是和。10. 二分搜索算法是利用实现的算法。二、综合题（50 分）1. 写出设计动态规划算法的主要步骤。2. 流水作业调度问题的johnson算法的思想。3. 若n=4,在机器Ml和M2上加工作业i所需的时间分别为a和b ,ii且(a,a,a,a) = (4,5,12,10), (b ,b ,b ,b ) = (8,2,15,9)求 4 个作业l 234l 234的最优调度方案,并计算最优
3、值。4. 使用回溯法解 0/1 背包问题：n=3, C=9, V二6,10,3, W二3,4,4,其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。5. 设S二X, X, , X 是严格递增的有序集，利用二叉树的结点12n来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形，(1)在二叉搜索树的内结点中找到X=X，其概率i为b。(2)在二叉搜索树的叶结点中确定XE(X,X ),其概率为ii i+1a。在表示S的二叉搜索树T中，设存储元素X的结点深度为C；叶iii结点(X,X )的结点深度为
4、d,则二叉搜索树T的平均路长p为多i i+1i少？假设二叉搜索树Tij=X, X ,，X最优值为mij,i i+1jWij= a +b + +b +a，则 mij(1=i=j=b；将N中作业按a的非减序排1i i 2i i1i序得到N 将N中作业按b的非增序排序得到N N 中作业12i21接N 中作业就构成了满足Johnson法则的最优调度。23. 步骤为：N1二1, 3, N2=2, 4；N =1, 3, N =4, 2；12最优值为：384. 解空间为(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)。解空间树为：
5、该问题的最优值为：16 最优解为：(1，1，0)5. 二叉树 T 的平均路长 P二m bi*(l + Ci) + Y aj*dji=1j=0 mij=Wij+minmik+mk+1j (1=i=jj)6. 已知一个背包的容量为C,有n件物品，物品i的重量为W,价值i为V，求应如何选择装入背包中的物品，使得装入背包中物品的总i价值最大。三、简答题void sort(flowjope s,int n)int i,k,j,l;for(i=1;i=n-1;i+)/选择排序k=i;while(kn) break;/没有 a 跳出elsefor(j=k+1;jsj.a) k=j;swap(si.index
6、,sk.index);swap(si.tag,sk.tag); Z记下当前第一个bi的下标for(i=l;i=n-1;i+)k=i;for(j=k+1;j=n;j+)if(sk.bsj.b) k=j;swap(si.index,sk.index); /只移动 index 和 tag2.void binarysearchtree(int a,int b,int n,int *m,int *s,int *w) int i,j,k,t,l;for(i=1;i=n+1;i+) wii-1=ai-1;mii-1=0;for(l=0;l=n-1;l+)/l 是下标 j-i 的差for(i=1;i=n-l;i+) j=i+l;wij=wij-1+aj+bj; mij=mii-1+mi+1j+wij;sij=i; for(k=i+1;k=j;k+) t=mik-1+mk+1j+wij; if(tmij) mij=t;sij=k;
