算法设计与分析复习题目及答案Word格式.docx

1、（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。（最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质回溯算法和分支限界法的问题的解空间树不会是（ 无序树 ）.14哈弗曼编码的贪心算法所需的计算时间为（BA、O（n2n） B、O（nlogn） C、O（2n） D、O（n）21、下面关于NP问题说法正确的是（B ）A NP问题都是不可能解决的问题B P类问题包含在NP类问题中C NP完全问题是P类问题的子集D NP类问题包含在P类问题中40、背包问题的贪心算法所需的计算时间为（ ）A、O（n2n） B、O

2、（nlogn） C、O（2n） D、O（n）420-1背包问题的回溯算法所需的计算时间为（AA、O（n2n） B、O（nlogn） C、O（2n） D、O（n）.47.背包问题的贪心算法所需的计算时间为（A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）53采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 （ B ） 。56、算法是由若干条指令组成的有穷序列，而且满足以下性质（ D ）（1） 输入：有0个或多个输入（2） 输出：至少有一个输出（3） 确定性：指令清晰，无歧义（4） 有限性：指令执行次数有限，而且执行时间有限 A （1

3、）（2）（3） B（1）（2）（4） C（1）（3）（4） D （1） （2）（3）（4）57、函数32n+10nlogn的渐进表达式是（ B ）.A. 2n B. 32n C. nlogn D. 10nlogn59、用动态规划算法解决最大字段和问题，其时间复杂性为（ B ）.A.logn B.n C.n2 D.nlogn61、设f（N）,g（N）是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当NN0时有f（N）Cg（N）,则称函数f（N）当N充分大时有下界g（N）,记作f（N）（g（N）,即f（N）的阶（ A ）g（N）的阶.A.不高于 B.不低于C.等价于 D.逼近二、 填

4、空题 2、程序是 算法用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。6、算法是指解决问题的 一种方法 或 一个过程 。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。11、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束

5、条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。 30.回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。33回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数 。34.任何可用计算机求解的问题所需的时间都与其 规模 有关。35.快速排序算法的性能取决于 划分的对称性 。36. Prim算法利用 贪心 策略求解 最小生成树 问题，其时间复杂度是 O（n2） 。37. 图的m着色问题可用 回溯 法求解，其解空间树中叶子结点个数是 mn ，解空间树中每个内结点的孩子数是 m 。4.若序列X=B,C,A,D,B,C,D，Y=A,C,B

6、,A,B,D,C,D，请给出序列X和Y的一个最长公共子序列 BABCD或CABCD或CADCD。5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 8.0-1背包问题的回溯算法所需的计算时间为_o（n*2n）_,用动态规划算法所需的计算时间为_o（minnc,2n_。二、综合题（50分）1.写出设计动态规划算法的主要步骤。问题具有最优子结构性质；构造最优值的递归关系表达式；3最优值的算法描述；构造最优解；2.流水作业调度问题的johnson算法的思想。令N1=i|ai=bi；将N1中作业按ai的非减序排序得到N1，将N2中作业按bi的非增序排序得到N2；N1中作

7、业接N2中作业就构成了满足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个作业的最优调度方案，并计算最优值。步骤为：N1=1，3，N2=2，4；N1=1，3， N2=4，2；最优值为：384.使用回溯法解0/1背包问题：n=3，C=9，V=6,10,3，W=3,4,4,其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。解空间为（0,0,0）,（0,1,0）

8、,（0,0,1）,（1,0,0）,（0,1,1）,（1,0,1）,（1,1,0）,（1,1,1）。解空间树为：该问题的最优值为：16 最优解为：（1，1，0）5.设S=X1，X2，Xn是严格递增的有序集，利用二叉树的结点来存储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最

9、优值为mij，Wij= ai-1+bi+bj+aj，则mij（1=i=j=n）递归关系表达式为什么？二叉树T的平均路长P=+mij=Wij+minmik+mk+1j （1j）6.描述0-1背包问题。已知一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。三、简答题（30分） 1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为ai和bi，请写出流水作业调度问题的johnson法则中对ai和bi的排序算法。（函数名可写为sort（s,n）2.最优二叉搜索树问题的动态规划算法（设函数名binarys

10、earchtree）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+） for（j=k+1; if（sk.bsj.b） k=j; /-只移动index和tag 2.void binarysearchtree（int a,int b,int n,in

11、t *m,int *s,int *w） int i,j,k,t,l;=n+1; wii-1=ai-1; mii-1=0; for（l=0;ll+）/-l是下标j-i的差for（i=1;=n-l; 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（t=0;r-） /自底向上递归计算for（c=0; 1 ;c+） if（ tr+1ctr+1c+1） 2 ；else 3 ；3、Hanoi算法Hanoi（n,a,b,c）if （n=1） 1 ；else 2 ； 3 ；Hanoi（

12、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=Su for each vertex 3 do 4 四、算法理解题（本题10分）根据优先队列式分支限界法，求下图中从v1点到v9点的

13、单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用标记，获得中间解的结点用单圆圈框起，最优解用双圆圈框起。五、算法理解题（本题5分）设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1名选手比赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成。（1）如果n=2k，循环赛最少需要进行几天；（2）当n=23=8时，请画出循环赛日程表。六、算法设计题（本题15分）分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。七、算法设计题（本题10分）通过键盘输入一个高精度

14、的正整数n（n的有效位数240），去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】178543S=4【样例输出】136、 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。7、 “最优化原理”用数学化的语言来描述：假设为了解决某一优化

15、问题，需要依次作出n个决策D1，D2，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，Dn也是最优的。8、 某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。9、 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状

16、态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。10、 P（Polynomial问题）：也即是多项式复杂程度的问题。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。（1） !Mj&!Li+j&Ri-j+N（2） Mj=Li+j=Ri-j+N=1;（3） try（i+1,M,L,R,A） （4） Aij=0 （5） Mj=Li+j=Ri-j+N=0（1）cc）

17、 break;xi=1;c-=wi;if （i=n） xi=c/wi;（2）动态规划法 O（nc）m（i，j）是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m（i，j）的递归式如下。void KnapSack（int v,int w,int c,int n,int m11）int jMax=min（wn-1,c）;for （j=0;=jMax;j+） /*m（n,j）=0 0=wn*/mnj=vn;for （i=n-1;i1;i-） int jMax=min（wi-1,c）;j+） /*m（i,j）=m（i+1,j） 0= m

18、ij=max（mi+1j,mi+1j-wi+vi）;m1c=m2c;if（c=w1）m1c=max（m1c,m2c-w1+v1）;（3）回溯法 O（2n）cw:当前重量 cp:当前价值 bestp：当前最优值voidbacktrack（inti） /回溯法 i初值1if（in） /到达叶结点 bestp=cp; return; if（cw+wibestp） /搜索右子树 backtrack（i+1）;为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。具体算法如下：输入s, n;while（ s 0 ） i=1; /从串首开始找while （i length（n） & （ni1）& （n1=0） delete（n,1,1）; /删去串首可能产生的无用零输出n;三、算法填空1.背包问题的贪心算法 Sort（n,v,w）; int i; for （i=1; float c=M;i+） if （wi xi=1; c - =wi; if （i2.最大子段和: 动态规划算法int MaxSum（int n, int a） int sum