算法设计与分析考试题目及答案.doc

《算法设计与分析考试题目及答案.doc》由会员分享，可在线阅读，更多相关《算法设计与分析考试题目及答案.doc（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法分析及设计期末复习题一、 选择题1.应用Johnson法则流水作业调度采用算法是（D）A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法2.Hanoi塔问题如下图所示。现要求将塔座A上所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题移动规则。由此设计出解Hanoi塔问题递归算法正确为：（B）A. void hanoi(int n, int A, int C, int B) if (n 0) hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); Hanoi塔B. void hanoi(int n, in

2、t A, int B, int C) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); C. void hanoi(int n, int C, int B, int A) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C, int A, int B) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 3. 动态

3、规划算法基本要素为（C）A. 最优子结构性质及贪心选择性质B重叠子问题性质及贪心选择性质C最优子结构性质及重叠子问题性质D. 预排序及递归调用4. 算法分析中，记号O表示（B）， 记号表示（A）， 记号表示（D）。5. 以下关于渐进记号性质是正确有：（A）A.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 6. 能采用贪心算法求最优解问题，一般具有重要性质为：（A）A. 最优子结构性质及贪心选择性质B重叠子问题性质及贪心选择性质C最优子结构性质及重叠子问题性质D. 预排序及递归调用7. 回溯法在问题解空间树中，按（D）策略，从根结点出发搜索解空间树。A 广度优先

4、 B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题解空间树中，按（A）策略，从根结点出发搜索解空间树。 A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树算法框架程序。void backtrack (int t) if (tn) output(x); else for (int i=t;in) output(x); else for (int i=0;in) output(x); else for (int i=0;in) output(x); else for (int i=t;i0，存在正数与n0 0使得对所有nn

5、0有：0 f(n)0，存在正数与n0 0使得对所有nn0有：0 cg(n) 0，存在正数与n0 0使得对所有nn0有：0 f(n)0，存在正数与n0 0使得对所有nn0有：0 cg(n) f(n) ；二、 填空题1. 下面程序段所需要计算时间为（ ）。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;2. 有11个待安排活动，它们具有下表所示开始时间

6、及结束时间，如果以贪心算法求解这些活动最优安排（即为活动安排问题：在所给活动集合中选出最大相容活动子集合），得到最大相容活动子集合为活动（ 1，4，8，11 ）。1413121110987654fi122886535031Si1110987654321i3. 所谓贪心选择性质是指（所求问题整体最优解可以通过一系列局部最优选择，即贪心选择来达到）。4. 所谓最优子结构性质是指（问题最优解包含了其子问题最优解）。5. 回溯法是指（具有限界函数深度优先生成法）。6. 用回溯法解题一个显著特征是在搜索过程中动态产生问题解空间。在任何时刻，算法只保存从根结点到当前扩展结点路径。如果解空间树 中从根结点到

7、叶结点最长路径长度为h(n)，则回溯法所需计算空间通常为（O(h(n)7. 回溯法算法框架按照问题解空间一般分为（子集树）算法框架及（排列树）算法框架。8. 用回溯法解0/1背包问题时，该问题解空间结构为（子集树）结构。9.用回溯法解批处理作业调度问题时，该问题解空间结构为（排列树）结构。10.用回溯法解0/1背包问题时，计算结点上界函数如下所示，请在空格中填入合适内容：Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n

8、& wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) （b += pi/wi * cleft）; return b;11. 用回溯法解布线问题时，求最优解主要程序段如下。如果布线区域划分为方格阵列，扩展每个结点需O(1)时间，L为最短布线路径长度，则算法共耗时 ( O(mn) )，构造相应最短距离需要（O(L)）时间。for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (grid

9、nbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) & (nbr.col = finish.col) break; / 完成布线 Q.Add(nbr); 12. 用回溯法解图m着色问题时，使用下面函数OK检查当前扩展结点每一个儿子所相应颜色可用性，则需耗时（渐进时间上限）（O（mn）。Bool Color:OK(int k)/ for(int j=1;j=n;j+)if(akj= =1)&(xj= =xk) return false;retur

10、n true;13. 旅行售货员问题解空间树是（排列树）。三、 证明题1. 一个分治法将规模为n问题分成k个规模为nm子问题去解。设分解阀值n0=1，且adhoc解规模为1问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题解合并为原问题解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n问题所需计算时间，则有：通过迭代法求得T（n）显式表达式为：试证明T（n）显式表达式正确性。2. 举反例证明0/1背包问题若使用算法是按照pi/wi非递减次序考虑选择物品，即只要正在被考虑物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题及背包问题

11、不同）。证明：举例如：p=7,4,4,w=3,2,2,c=4时，由于7/3最大，若按题目要求方法，只能取第一个，收益是7。而此实例最大收益应该是8，取第2，3 个。3. 求证：O(f(n)+O(g(n) = O(maxf(n),g(n) 。证明：对于任意f1(n) O(f(n) ，存在正常数c1与自然数n1，使得对所有nn1，有f1(n) c1f(n) 。类似地，对于任意g1(n) O(g(n) ，存在正常数c2与自然数n2，使得对所有nn2，有g1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。则对所有 n n3，有f

12、1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .4. 求证最优装载问题具有贪心选择性质。（最优装载问题：有一批集装箱要装上一艘载重量为c轮船。其中集装箱i重量为Wi。最优装载问题要求确定在装载体积不受限制情况下，将尽可能多集装箱装上轮船。设集装箱已依其重量从小到大排序，(x1,x2,xn)是最优装载问题一个最优解。又设 。如果给定最优装载问题有解，则有。） 证明：四、 解答题1. 机器调度问题。问题描述：现在有n件任务与无限多台机器，

13、任务可以在机器上得到处理。每件任务开始时间为si，完成时间为fi，si n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi;5. 用分支限界法解装载问题时，对算法进行了一些改进，下面程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做原因，即采用这样方式，算法在执行上有什么不同。/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列

14、if (i bestw & i 0 故Ew+rbestw总是成立。也就是说，此时右子树测试不起作用。为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到最优值是所求问题子集树中所有可行结点相应重量最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw值。7. 最长公共子序列问题：给定2个序列X=x1,x2,xm与Y=y1,y2,yn，找出X与Y最长公共子序列。 由最长公共子序列问题最优子结构性质建立子问题最优值递归关系。用cij记录序列Xi与Yj最长公共子序列长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j

15、=0时，空序列是Xi与Yj最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：在程序中，bij记录Cij值是由哪一个子问题解得到。（1） 请填写程序中空格，以使函数LCSLength完成计算最优值功能。void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1

16、j; bij=2; else cij=cij-1; bij=3; （2） 函数LCS实现根据b内容打印出Xi与Yj最长公共子序列。请填写程序中空格，以使函数LCS完成构造最长公共子序列功能（请将bij取值及（1）中您填写取值对应，否则视为错误）。void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); cout0 ) printf(%dn ,k); f(k-1); f(k-1); 一、填空题（20分）1.一个算法就是一个有穷规则集合，其中之规则规定了解决某一特殊类型问题一

17、系列运算，此外，算法还应具有以下五个重要特性:_,_,_,_,_。2.算法复杂性有_与_之分，衡量一个算法好坏标准是_。3.某一问题可用动态规划算法求解显著特征是_。4.若序列X=B,C,A,D,B,C,D，Y=A,C,B,A,B,D,C,D，请给出序列X与Y一个最长公共子序列_。5.用回溯法解问题时，应明确定义问题解空间，问题解空间至少应包含_。 6.动态规划算法基本思想是将待求解问题分解成若干_，先求解_，然后从这些_解得到原问题解。7.以深度优先方式系统搜索问题解算法称为_。8.0-1背包问题回溯算法所需计算时间为_,用动态规划算法所需计算时间为_。9.动态规划算法两个基本要素是_与_。

18、10.二分搜索算法是利用_实现算法。二、综合题（50分）1.写出设计动态规划算法主要步骤。2.流水作业调度问题johnson算法思想。3.若n=4，在机器M1与M2上加工作业i所需时间分别为ai与bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业最优调度方案，并计算最优值。4.使用回溯法解0/1背包问题：n=3，C=9，V=6,10,3，W=3,4,4,其解空间有长度为30-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。5.设S=X1，X2，Xn是严格递增有序集，利

19、用二叉树结点来存储S中元素，在表示S二叉搜索树中搜索一个元素X，返回结果有两种情形，（1）在二叉搜索树内结点中找到X=Xi，其概率为bi。（2）在二叉搜索树叶结点中确定X（Xi，Xi+1），其概率为ai。在表示S二叉搜索树T中，设存储元素Xi结点深度为Ci；叶结点（Xi，Xi+1）结点深度为di，则二叉搜索树T平均路长p为多少？假设二叉搜索树Tij=Xi，Xi+1，Xj最优值为mij，Wij= ai-1+bi+bj+aj，则mij(1=i=j=n)递归关系表达式为什么？6.描述0-1背包问题。三、简答题（30分）1.流水作业调度中，已知有n个作业，机器M1与M2上加工作业i所需时间分别为ai与

20、bi，请写出流水作业调度问题johnson法则中对ai与bi排序算法。（函数名可写为sort(s,n)）2.最优二叉搜索树问题动态规划算法（设函数名binarysearchtree)）答案：一、填空1确定性 有穷性 可行性 0个或多个输入 一个或多个输出2.时间复杂性 空间复杂性 时间复杂度高低 3. 该问题具有最优子结构性质 4.BABCD或CABCD或CADCD 5.一个（最优）解 6.子问题 子问题 子问题 7.回溯法 8. o(n*2n) o(minnc,2n)9.最优子结构 重叠子问题二、综合题1.问题具有最优子结构性质；构造最优值递归关系表达式； 最优值算法描述；构造最优解；2.

21、令N1=i|ai=bi；将N1中作业按ai非减序排序得到N1，将N2中作业按bi非增序排序得到N2；N1中作业接N2中作业就构成了满足Johnson法则最优调度。3.步骤为：N1=1，3，N2=2，4；N1=1，3， N2=4，2；最优值为：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)。解空间树为：ABCFEDGKJIHONML11100001011010该问题最优值为：16 最优解为：（1，1，0）5.二叉树T平均路长P=+ mij=Wij+minmik+mk+1j (1=i=jj)6.已知一个

22、背包容量为C，有n件物品，物品i重量为Wi，价值为Vi，求应如何选择装入背包中物品，使得装入背包中物品总价值最大。三、简答题1.void sort(flowjope s,int n) int i,k,j,l; for(i=1;i=n-1;i+)/-选择排序 k=i; while(kn) break;/-没有ai，跳出 else for(j=k+1;jsj.a) k=j; swap(si.index,sk.index); swap(si.tag,sk.tag); l=i;/-记下当前第一个bi下标 for(i=l;i=n-1;i+) k=i; for(j=k+1;j=n;j+) if(sk.bs

23、j.b) k=j; swap(si.index,sk.index); /-只移动index与tag swap(si.tag,sk.tag); 2.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

24、=mik-1+mk+1j+wij;if(tmij) mij=t;sij=k;一、 填空题（本题15分，每小题1分）1、 算法就是一组有穷 ，它们规定了解决某一特定类型问题 。2、 在进行问题计算复杂性分析之前，首先必须建立求解问题所用计算模型。3个基本计算模型是 、 、 。3、 算法复杂性是 度量，是评价算法优劣重要依据。4、 计算机资源最重要是 与 资源。因而，算法复杂性有 与 之分。5、 f(n)= 62n+n2，f(n)渐进性态f(n)= O( )6、 贪心算法总是做出在当前看来 选择。也就是说贪心算法并不从整体最优考虑，它所做出选择只是在某种意义上 。7、 许多可以用贪心算法求解问题一

25、般具有2个重要性质： 性质与 性质。二、简答题（本题25分，每小题5分）1、 简单描述分治法基本思想。2、 简述动态规划方法所运用最优化原理。3、 何谓最优子结构性质？4、 简单描述回溯法基本思想。5、 何谓P、NP、NPC问题三、算法填空（本题20分，每小题5分）1、n后问题回溯算法(1)用二维数组ANN存储皇后位置,若第i行第j列放有皇后,则Aij为非0值,否则值为0。(2)分别用一维数组MN、L2*N-1、R2*N-1表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;j=0;r-) /自底向上递归计算for(c=0; 1 ;c+) if( tr+1ctr+1c

26、+1) 2 ；else 3 ；3、Hanoi算法Hanoi(n,a,b,c)if （n=1） 1 ；else 2 ； 3 ；Hanoi(n-1,b, a, c);4、Dijkstra算法求单源最短路径du:s到u距离 pu:记录前一节点信息Init-single-source(G,s)for each vertex vVG do dv=; 1 ds=0Relax(u,v,w)if dvdu+w(u,v)then dv=du+wu,v; 2 dijkstra(G,w,s)1. Init-single-source(G,s) 2. S= 3. Q=VG4.while Q do u=min(Q) S

27、=Su for each vertex 3 do 4 四、算法理解题（本题10分）根据优先队列式分支限界法，求下图中从v1点到v9点单源最短路径，请画出求得最优解解空间树。要求中间被舍弃结点用标记，获得中间解结点用单圆圈框起，最优解用双圆圈框起。五、算法理解题（本题5分）设有n=2k个运动员要进行循环赛，现设计一个满足以下要求比赛日程表：每个选手必须及其他n-1名选手比赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成。（1）如果n=2k，循环赛最少需要进行几天；（2）当n=23=8时，请画出循环赛日程表。六、算法设计题（本题15分）分别用贪心算法、动态规划法、回溯法设计0-1背包

28、问题。要求：说明所使用算法策略；写出算法实现主要步骤；分析算法时间。七、算法设计题（本题10分）通过键盘输入一个高精度正整数n(n有效位数240)，去掉其中任意s个数字后，剩下数字按原左右次序将组成一个新正整数。编程对给定n 与s，寻找一种方案，使得剩下数字组成新数最小。【样例输入】178543S=4【样例输出】13一、填空题（本题15分，每小题1分）1规则 一系列运算2. 随机存取机RAM(Random Access Machine)；随机存取存储程序机RASP(Random Access Stored Program Machine)；图灵机(Turing Machine)3. 算法效率4. 时间、空间、时间复杂度、空间复杂度52n6最好 局部最优选择7. 贪心选择 最优子结构二、简答题（本题25分，每小题5分）6、 分治法基本思想是将一个规模为n问题分解为k个规模较小子问题，这些子问题互相独立且及原问题相同；对这k个子问题分别求解。如果子问题规模仍然不够小，则再划分为k个子问题，如此递归进行下去，直到问题规模足够小，很容易求出其解为止；将求出小规模问题解合并为一个更大规模问题解，自底向上逐步求出原来问题解。7、 “最优化原理”用数学化语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，Dn，如若这个