软考辅导—数据结构与算法.pdf

软考辅导主要内容考点分析 数据结构与算法概述 数据结构知识点复习 算法知识点复习模拟练习第七部分算法:分值：216分（每年）:分数比重：22%:重要知识点：1、时间复杂度2、穷举法、迭代法、递推法、递归法、分治法、动态规划法、回溯法、贪心法分支限界法t 第七部分算法 一3。蛮力法(穷举法)A蛮力法(brute force method):也称穷举法(enumerate)法，是蛮力策 略的一种表现形式。它是根据问题中的条件将可能的情况一一列举 出来，逐一尝试从中找出满足问题条件的解。但有时列举出的 情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考 虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数 目。A用蛮力法解决问题，通常从两个方面进行算法设计：1、找出穷举范围：分析问题所涉及的各种情况。2、找出约束条件：分析问题的解需要满足的条件，并用逻辑表 达式表示。A应用：顺序查找、简单选择排序、冒泡排序、0/1背包、哈密顿回路、旅行家问题。最近点对和凸包问题。第七部分算法【例】解数字迷：A B C A BX AD D D D D D穷举范围：A:3-9（A=l,2时积不会得到六位数），B:0-9,C:0-9 六位数表示为A*10000+B*1000+C*100+A*10+B,共尝试800 次。约束条件：每次尝试，先求六位数与A的积，再测试积的各位是否 相同，若相同则找到了问题的解。测试积的各位是否相同比 较简单的方法是，从低位开始，每次都取数据的个位，然后 整除10,使高位的数字不断变成个位，并逐一比较。main()int A,B,C,D,E,El,F,Gl,G2,i;for(A=3;A=9;A+)for(B=0;B=9;B+)for(C=0;C=9;C+)(F=A*10000+B*1000+C*100+A*10+B;E=F*A；E1=E;G1=E1 mod 10;for(i=l;i=5;i+)(G2=G1;El=El/10;Gl=El mod 10;if(GlG2)break;if(i=6)print(F,”，A,=，E);虽然巧妙和高效的算法很少来自于蛮力法，但是,蛮力法也是一种重要的算法设计技术：(1)理论上，蛮力法可以解决计算领域的各种问题。例如：求序列中的最大值、n个数的和等。(2)蛮力法经常用来解决一些较小规模的问题。(3)对于一些重要的问题(例如：排序、查找、字 符串匹配)蛮力法可以产生一些合理的算法，他们具备 一些实用价值，而且不受问题规模的限制。(4)蛮力法可以作为某类问题时间性能的底限，来 衡量同样问题的更高效算法。A迭代法：使用计算机解决问题的一种基本方法。它利用计算机对一 组指令进行重复执行，在每次执行这组指令时，都从变量的原值推 出它的一个新值。即能找出个函数，不断将结果当做变量带入，就 叫迭代。1、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一 个直接或间接的不断由旧值地推出新值的变量，这个变量就是迭 代变量；2、建立迭代关系。即如何从变量的前一个值推出其下一个值的公 式。迭代关系式的建立是解决迭代问题的关键，通常可以使用递 推的方法来完成；3、对迭代过程加以控制，以保证迭代过程在有限次内结束。第七部分算法例1:一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下 一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的 兔子都不死去，问到第12个月时，该饲养场共有兔子多少只？分析：第1个月时兔子的只数为由,第2个月时兔子的只数为u2,第3个月时兔子的只数为由,根据题意，“这种兔子从出生的下一 个月开始，每月新生一只兔子”，则有%=1,%=Ui+Ui x 1=2,u3=u2+u2 x 1=4.根据这个规律，可以归纳出下面的递推公式：Un=/一1 X 2(n 2)对应Un和Un一 1，定义两个迭代变量y和X,可将上面的递推公式 转换成如下迭代关系：y=x*2 x=y让计算机对这个迭代关系重复执行11次，就可以算出第12个月时 的兔子数。第七部分算法2。递推法A递推法：在数列中，建立起后项和前项的关系数列的后一组数由前 一组数表示，运算，就是递推。其实广义的看，那几个数列关系可 以看成多元函数，其中的变量是一个向量，其实没有实质性差别。(1)顺推法从初始条件入手，一步步地按递推关系递推，直至求 出最终结果。如：斐波那契数列例：求斐波那契数列第10项。已知斐波那契数列第1项为1,第2项也 为2,递推关系是当前项等于前2项之和。Fn=fn-l+fn-2(n3)of2=2；for(m=3;m=800);disk=800;oilk=(k-l)*400+(800-disk)*(2*k+l);for(m=0 t;m=k-l;m+)输出(800-dis k-m,oil k-m);第七部分算法递归法A递归法:递归算法本质上将较复杂的处理归结为简单处理，直到最简单的处 理，在处理的递归调用过程中，系统用堆栈把每次调用的中间结果 保存在栈区，直至求出最简值，然后返回调用函数，返回过程中，中间结果相继出栈恢复，它的执行效率相对比较低。int fib(int f)if(n=l)f=l;else if(n=2)f=2;else f=fib(n-l)+fib(n-2)A思想：将一个难以直接解决的大问题，划分成一些规模较小的子问 题，以便各个击破，分而治之。1、分解：将要求解的原问题划分成k个较小规模的子问题，对这 k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子 问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足 够小，很容易求出其解为止；2、合并：再将子问题的解合并为一个更大规模的问题的解，自底 向上逐步求出原问题的解。A应用：大整数乘法、矩阵乘法、归并排序、快速排序、循环赛日程 安排、最近点对问题、凸包问题A归并排序(1)划分：将待排序序列7 G，弓划分为两个长度相等的 子序列，1，乙/2和乙/2+1，；rl.rn/2|rn/2+l.Tn 却J 分(2)求解子问题：分别对这两个子序列进行归并排序(递 归调用)，得到两个有序子序列；(3)合并：将这两个有序子序列合并成一个有序序列o第七部分算法I例:对序列进行排序:19 13 05 27 01 26 31 16个步(19)(13)(05)(27)(01)(26)(31)(16)求解 _1 J _1求解(13,19)(05,27)(01,26)(16,31)合并 1-T-1 1-j-1(05,13,19,27)(01,16,26,31)(01,05,13,16,19，26，27，31)算法4.3归并排序void MergeSort(int r,int rl,int s,int t)(if(s=t)rls=rs;else(m=(s+t)/2;Mergesort(r9 rl5 s9 m);归并排序前半个子序列Mergesort(r,rl,m+1,t);归并排序后半个子序列Merge(rl,r,s9 1);/合并两个已排序的子序列二路归并排序的时间代价是O(log2)二路归并排序在合并 过程中需要与原始记录序列同样数量的存储空间，因此其空 间复杂性为第七部分算法动态规划法（200812试题四）A思想：在求解问题中，对于每一步决策，列出各种可能的局部解，再 依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一 步都经过筛选，以每一步都是最优解来保证全局是最优解，这种求解 方法称为动态规划法。1、约束条件：有n个输入，它的解由这n个输入的一个子集组成，这 个子集必须满足某些事先给定的条件，这些条件称为约束条件。2、可行解：满足约束条件的解称为问题的可行解。3、目标函数：满足约束条件的可行解可能不只一个，为了衡量这些 可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给 出，这些标准函数称为目标函数。4、最优化问题：使目标函数取得极值（极大或极小）的可行解称为 最优解，这类问题就称为最优化问题。A应用：矩阵连乘、多段图的最短路径、最长公共子序列、最优二叉排 序树。第七部分算法动态规划法矩阵连乘*给定n个矩阵 AnA2K.,An/，其中A,与Ai1是可乘的，i=l,2,n l。考察这n个矩阵的连乘积A I 4 2 A 白由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的 计算次序。这种计算次序可以用加括号的方式来确定。白若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全 加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出 矩阵连乘积。2:动态规划法矩阵连乘给定n个矩阵AiA，.,其中Aj与Aj+1是可乘的，i=l,2，,n-L如何确定计算矩阵连乘积的计算次序，使得依 此次序计算矩阵连乘积需要的数乘次数最少。矩阵A和B课程的条件是矩阵A的列数等于矩阵B的行数。若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C=AB是一 个p*r矩阵。在上述计算C的标准算法中，主要计算量在三 重循环，总共需要pqr次数乘。第七部分算法动态规划法矩阵连乘设有四个矩阵A、B、C、D,它们的维数分别是:A=50 x 10 B=10 x 40 C=40 x 30 D=30 x 5总共有五种加括号的方式(A(BC)D)(A(B(CD)(AB)(CD)(AB)C)D)(A(BC)D)五种方式计算的次数分别为：16000,10500,36000,87500,34500第七部分算法动态规划法矩阵连乘。穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的 数乘次数，从中找出一种数乘次数最少的计算次序。期动态规划法将矩阵连乘积AjAi+iAj简记为这里（j考察计算Ai:j的最优 计算次序。设这个计算次序在矩阵Ak和Ak+i之间将矩阵链断开，iWkq,则 其相应完全加括号方式为（AA+1Ak）（Ak+1Ak+2.Aj）o计算量：Ai:k的计算量加上Ak+l:j的计算量，再加上Ai:k和Ak+l:j相 乘的计算量 第七部分算法）期建立递归关系设计算Ai:j,lijn,所需要的最少数乘次数mi,j,则原问题的最 优值为ml,n当i=j时，Ai:j=Ai,因此，mi,i=O,i=l,2,.,n当ivj时,mi,j=mi,k+mk+l,j+p,“左 p.这里4的维数为Pw X上可以递归地定义mi,j为:j 0 i=j 一jmin 机i,左+加左+1,力+PrPkPj i j ikj Jk的位置只有j-i种可能p0：6=30,35,15,5,10,20,251 2 3 4 5 6(a)计算次序(b)123456i 101575078759375118751512520262543757125105003075025005375401000350050500060m22+m35+p,p2p5=0+2500+35x15x20=13000m25=miJ m23+m45+pxp3p5=2625+1000+35x5x20=7125m24+m5 5+夕旧2=4375+0+35 x 1 Ox 20=11375123456101575078759375118751512520262543757125105003075025005375401000350050500060用来记录计算矩阵链Ai:j的最优加括号方式为：(Ai:sij)(Asij+l:j)1234561 101133320233330333404550560(b)miD(C)siD阡JAJAJAlAlAlA:A A A A A A 以 i O H O h H h W-、L n J L a j L a j L n j L n J L n j11 二二1 二二 一二 1 1二 一二 1 a二一 八-I 二一【二 一AI 1 1AI 二一【二一 6幺-幺一幺-幺J幺一幺一 12 3 4 5 6数数数数数数035 53 15 53 150 1 502 0152 022 rL m23=m22+m33+plp2p3 625=0+0+35*15*534=m33*n44+p2p3p41 50=0+0+15*5*1045=n44+m55+p3p4p5 000=0+0+5*10*205J6=m55+iii66*p4p5p6000=0+0+10*20*25l3=mll*ni23*p0plp3875=0+2625+30*35*524=m23*n44+plp2p4375=2625+0+35*15*1035=m33*m45*p2p3p5 2500=0+1000+15*5*20p46=m45+m66*p3p4p61 3500=1000+0+5*10*25kl4=ml3+m44+p0plp49375=7875+0+30*35*10k25=m23*m45+plp2p57125=2625+1000+35*15*20k36=m33+m46*p2p3p65375=0+3500+15*5*25kl5=ml3+m45*p0plp511875=7875+1000+30*35*20p26=m23*m46*plp2p610500=2625+3500+35*15*25kl6=ml3+m46*p0plp615125=7875+3500+30*35*25AlA6,第七部分算法整 辛回溯法（200911试题四）A思想：回溯法也叫试探法，它是一种系统的搜索问题解的方法。回溯 法的基本思想：从一条路往前走，能走得通就继续走，走不通就退回 最近的交叉路口继续走下一条路.初始时，令解向量X为空，然后，从根结点出发，选择Si的第一个 元素作为解向量X的第一个分量，即Xi=an,如果X=（xJ是问题的部分 解，则继续扩展解向量X,选择S2的第一个元素作为解向量X的第2个 分量，否则，选择Si的下一个元素作为解向量X的第一个分量，即xl=a12o依此类推，一般情况下，如果X=（XpX2,X）是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种 情况：1、如果X=（m，X2,看+1）是问题的最终解，则输出这个解。如果问题 只希望得到一个解，则结束搜索，否则继续搜索其他解；第七部分算法回溯法2、如果X=（X1，X2,Xi+1）是问题的部分解，则继续构造解向量的下一 个分量；3、如果X=（X1，X2,七+1）既不是问题的部分解也不是问题的最终解，则存在下面两种情况：如果Xi+1=%+Ik不是集合Si+1的最后一个元素，则令Xi+1=ai+ik+1，即选择Si+i的下一个元素作为解向量X的第i+1个分量；如果x i+广a i+ik是集合S i+1的最后一个元素，就回溯到X=（xi，x2,xj,选择Si的下一个元素作为解向量X的第i个分量，假设xi=aik,如 果aik不是集合&的最后一个元素，则令=aik+i；否则，就继续回溯到 X=（X,x2,x j一 J；A应用：图的着色、哈密顿回路、八皇后问题、批处理作业调度。第七部分算法回溯法-八皇后问题显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，皇 后问题的可能解用一个元向量X=（x%，/）表示，其中，1W运并 且1q日，即第冷皇后放在第力行第七列上。由于两个皇后不能位于同一列上，所以，解向量X必须满足约束 条件：（式8.1）若两个皇后摆放的位置分别是G“和（/,引，在棋盘上斜率为-1 的斜线上，满足条件U-个 在棋盘上斜率为1的斜线上，满足 条件+综合两种情况，由于两个皇后不能位于同一斜线上,所以，解向量x必须满足约束条件：I，一闻 HI/一同（式8.2）第七部分算法为了简化问题，下面讨论四皇后问题。四皇后问题的解空间树是一个完全4叉树，树的根结点 表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋 盘中第1行的可能摆放位置，从第2层结点到第3层结点对应 皇后2在棋盘中第2行的可能摆放位置，依此类推。第七部分算法-一回溯法-八皇后问题回溯法求解4皇后问题的搜索过程(a)(b)(c)(d)(e)QQXQXXX XQQX XXQQQQXXQ(f)(g)(h)(i)(j)void Queue(int n)n皇后问题for(i=l;i=l)(x k=x k+l;在下一列放置第k个皇后while(xk=n&!Place(k)x k=x k+l;/搜索下一列if(xk=n&k=n)/得到一个解，输出 for(i=l;i=n;i+)coutxi;return;L.else if(xk=n&kn)else xk=O;重置xk,回溯k=k-l;bool Place(int k)考察皇后k放置在xk列是否发生冲突for(i=l;iiXi=Cj10 x.1（1 i C)!4.1 xi=l;将第i个物品放入背包i 4.2 C=C-wi;!4.3 i+;i 5.xi=C/wi;算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。国此，其时间复杂性为0(10g2)。A思想：分支定界（branch and bound）算法是一种在问题的解空间树上 搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优 先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题 的解空间树进行搜索，它的搜索策略是：1.产生当前扩展结点的所有孩子结点；2.在产生的孩子结点中，抛弃那些不可能产生可行解（或最优 解）的结点；3.将其余的孩子结点加入活结点表；4.从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解（最优解）或活结点表为空。分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索 树的某些支，提高搜索效率。第七部分算法*分支限界法TSP问题TSP问题是指旅行家要旅行个城市，要求各个城市经 历且仅经历一次然后回到出发城市，并要求所走的路程最短。00 3 1 5C=3 oo 6 71 6 oo 45 7 4 oo8 9 2 3892300(b)无向图的代价矩阵图9.4无向图及其代价矩阵第七部分算法*分支限界法TSP问题采用贪心法求得近似解为1 一3一5一4一2一 1,其路径长度为 1+2+3+7+3=16,这可以作为TSP问题的上界。把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径 长度为1+3+1+3+2=10,但是还有一个信息量更大的下界：考虑一个TSP问 题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个 城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两 个元素相加再除以2,再对这个结果向上取整，就得到了一个合理的下界。必=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14于是，得到了目标函数的界14,16。需要强调的是，这个解并不是一 个合法的选择(可能没有构成哈密顿回路)，它仅仅给出了一个参考下界。第七部分算法。分支限界法TSP问题部分解的目标函数值的计算方法左一 1法=(22屯匕+/+行不在路径上的最小偌+行最小的两个元为小i=l r：wU r,HJL J例如图9.4所示无向图，如果部分解包含边(1,4),则该部分 解的下界是必=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。支限界法TSP问题第七部分算法1startlbl42-3lb=1621 一2 ZF14672-4lb=16C=00315830067931600428 X2 5 lb=19574003892300154 一2 lbl81 一3Z143-2Z169101116124一5 lbl55-2 1193 一4必=153-5必=14、5 X1 一5|必=19|35 6829734425117X35工1144-27165-2Z20应用分支限界法求解图9.4所示无向图的TSP问题，其搜索空间如图9.5 所示，具体的搜索过程如下(加黑表示该路径上已经确定的边)：(1)在根结点1,根据限界函数计算目标函数的值为 仍=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14;(2)在结点2,从城市1到城市2,路径长度为3,目标函数的值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,将结点2加入待处理结点表PT中；点结点3,从城市1到城市3,路径长度为1,目标函数的值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,将结点3加入表PT中；在结点4,从 城市1到城市4,路径长度为5,目标函数的值为(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16,将结点4加入表PT中；在结点5,从 城市1到城市5,路径长度为8,目标函数的值为(1+8)+(3+6)+(1+2)+(3+5)+(2+8)/2=19,超出目标函数的界，将结点5丢弃；第七部分算法-4Hl：分支限界法TSP问题(3)在表PT中选取目标函数值极小的结点2优先进行搜索；(4)在结点6,从城市2到城市3,目标函数值为(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16,将结点6加入表PT中；在结点7,从城市2到城市4,目标函数值为(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16,将 结点7加入表PT中；在结点8,从城市2到城市5,目标函数值为(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19,超出目标函数的界，将结点8丢弃(5)在表PT中选取目标函数值极小的结点3优先进行搜索；(6)在结点9,从城市3到城市2,目标函数值为(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16,将结点9加入表PT中；在结点 10,从城市3到城市4,目标函数值为(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15,将 结点10加入表PT中；在结点11,从城市3到城市5,目标函数值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,将结点 11 加入表PT中；第七部分算法2:分支限界法TSP问题(7)在表PT中选取目标函数值极小的结点11优先进行搜索；(8)在结点12,从城市5到城市2,目标函数值为(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19,超出目标函数的界，将结点 12丢 弃；在结点13,从城市5到城市4,目标函数值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,将结点 13加入表PT 中;(9)在表PT中选取目标函数值极小的结点13优先进行搜索；(10)在结点14,从城市4到城市2,目标函数值为(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16,最后从城市2回到城市 1,目标函 数值为(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16,由于结点 14为叶子结点，得到一个可行解，其路径长度为16;第七部分算法。分支限界法TSP问题(11)在表PT中选取目标函数值极小的结点10优先进行搜索；(12)在结点15,从城市4到城市2,目标函数的值为(1+3)+(3+7)+(1+4)+(7+4)+(2+3)/2=18,超出目标函数的界，将结点 15丢 弃；在结点16,从城市4到城市5,目标函数值为(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15,将结点 16加入表PT中；(13)在表PT中选取目标函数值极小的结点16优先进行搜索；(14)在结点17,从城市5到城市2,目标函数的值为(1+3)+(3+9)+(1+4)+(3+4)+(9+3)/2=20,超出目标函数的界，将结点 17丢4；(15)表PT中目标函数值均为16,且有一个是叶子结点14,所以，结 点14对应的解1一3一5一4-2-1即是TSP问题的最优解，搜索过程结束。J start 必=14(1,2)14(1,3)14(1,4)16(a)扩展根结点后的状态6 3)14(1,4)16(1,2,3)16(1,2,4)16(b)扩展结点2后的状态(1,4)16(1,2,3)16(1,2,4)16(1,3,2)16(1,3,4)15(1,3,5)14(c)扩展结点3后的状态15;472力=18(d)扩展结点11后的状态(1,4)16L2,3)16(12 4)16(1,3,2)16(1,3,4)15(1,3,5,4)14(e)扩展结点13后的状态(1,4)16(12 3)16(12 4)16(1,3,2)16(1,3,4)15(1,3,5,4,2)1615;472力=18扩展结点10后的状态(1,4)16(12 3)16(1,2,4)16(1,3,2)16(1,3,5,4,2)16(1,3,4,5)15(g)扩展结点16后的状态，最优解为1t35t4t2t1(1,4)16(12 3)16(1,2,4)16(1,3,2)16(1,3,5,4,2)16婷 算法9.1TSP问题i 1.根据限界函数计算目标函数的下界down;采用贪心法得到上界up;2.将待处理结点表PT初始化为空；3.for(i=l;i=l)5.1 i=k+l;5.2 xi=l;5.3 while(xi=n)531如果路径上顶点不重复，则5.3.1.1 才艮据式9.2计算目标函数值1b;5.3.1.2 if(lb200505为在状态空间树中_(53)_,可以利用LC-检索(LeastCost Search)快速找到一个答案结点。在进行LC检索时，为避免算法过 分偏向于作纵深检查，应该(54)o(53)A.找出任一个答案结点 B.找出所有的答案结点C找出最优的答案结点 D.进行遍历(54)A.使用精确的成本函数c(.)来作LC检索B.使用广度优先检索C使用深度优先检索D.在成本估计函数6(.)中考虑根结点到当前结点的成本(距离)第七部分算法p 真题200505利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest path problem)时,设有向图G=共有n个结点，结点编 号ln,设C是G的成本邻接矩阵，用Dk(i,j)即为图G中结点i到j并 且不经过编号比k还大的结点的最短路径的长度(Dk(i,j)即为图G中 结点i到j的最短路径长度)，则求解该问题的递推关系式为(56)o(56)A.Dk(i,j)=Dk-l(i,j)+C(i,j)B.Dk(i,j)=miiiDk-l(i,j),Dk-l(i,j)+C(i,j)C.Dk(i,j)=Dk-l(i,k)+Dk-l(k,j)D.Dk(i,j)=minDk-l(i,j),Dk-l(i,k)+Dk-l(k,j)t 第七部分算法2:真题200511设求解某问题的递归算法如下：求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为(53);设算法Move的计算时间为k,当n=4时，算法F的计算时间为-(54)-o F(intn)!(53)A.T(n)=T(n-l)+lC.T(n)=2T(n-l)+l(54)A.14kC.16ktf(n=l)3D;如D;B.T(n)=2T(n-l)D.T(n)=2T(n+l)+lB.15kD.17k第七部分算法:真题200511利用贪心法求解0/1背包问题时，(55)能够确保获得最优解。用 动态规划方法求解0/1背包问题时，将“用前i个物品来装容量是X的背 包”的0/1背包问题记为KNAP(l,i,X),设X)是KNAP(l,i,X)最优解的效 益值，第j个物品的重量和放入背包后取得效益值分别为Wj和p(j=ln)o 则依次求解fo(X)、0(X)、/(X)的过程中使用的递推关系式为(56)_。(55)A.优先选取重量最小的物品 B.优先选取效益最大的物品C优先选取单位重量效益最大的物品 D.没有任何准则(56)A.fi(X)=minfi.1(X),fi.1(X)+pi B.fi(X)=maxfi.1(X),fi.1(X-Wi)+pi)C.fi(X)=minfi_1(X-Wi),fi.1(X-Wi)+pi)D.fi(X)=maxfi_1(X-Wi),fi_1(X)+pi)第七部分算法:真题200611(58)算法策略与递归技术的联系最弱。(58)A.动态规划B.贪心C.回溯D.分治对于具有n个元素的一个数据序列，若只需得到其中第k个元素之 前的部分排序，最好采用(59),使用分治(Divide and Conquer)策略的是(60)算法。(59)A.希尔排序 B.直接插入排序 C.快速排序 D.堆排序(60)A.冒泡排序 B.插入排序 C.快速排序 D.堆排序第七部分算法2:真题200705设商店有10元、5元、2元和1元的零币，每种零币的数量充足。售 货员给顾客找零钱时，零币的数量越少越好。例如给顾客找零29元：先选2张10元币，然后选择1张5元币，再选择两张2元币。以上的找 零钱方法采用了(62)策略。(62)A.分治 B.贪心 C.动态规划 D.回溯 200711迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短 路径问题，该算法运用了(63)算法策略。(63)A.贪心 B.分而治之 C.动态规划 D.试探+回溯200711关于算法与数据结构的关系，(64)是正确的。(64)A.算法的实现依赖于数据结构的设计B.算法的效率与数据结构无关C数据结构越复杂，算法的效率越高D.数据结构越简单，算法的效率越高若一个问题既可以用迭代方式也可以用递归方式求解，则(65)方 法具有更高的时空效率。(65)A.迭代 B.递归C.先递归后迭代 D.先迭代后递归第七部分算法200805 一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作 都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法 具有_(62)_特性。(62)A.有穷性 B.可行性 C.确定性 D.健壮性斐波那契数列为：1 =0F(n)=1用递归算法求解F时需要执行_(63)_次“+”运算，该方法采用 的算法策略是_(64)_。(63)A.5 B.6 C.7 D.8(64)A.动态规划 B.分治 C.回溯 D.分支限界第七部分算法:真题200811给定一组长度为n的无序序列，将其存储在一维数组a0nl中。现 采用如下方法找出其中的最大元素和最小元素：比较a0和an-l,若 a0较大，则将二者的值进行交换；再比较al和an-2,若al较大，则交换二者的值；然后依次比较a2和an-3、a3 an-4 使得 每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前 n/2个元素中查找最小元素，在后n/2个元素查找最大元素，从而得到整 个序列的最小元素和最大元素。上述方法采用的算法设计策略是(64)。(64)A.动态规划法 B.贪心法 C.分治法 D.回溯法设某算法的计算时间表示为递推关系式T(n尸T(n-l)+n(n0)及 T(0)=l,则该算法的时间复杂度为(65)。(65)A.O(lgn)B.O(n Ign)C.O(n)D.O(n2)2:真题200905现有16枚外形相同的硬币，其中有一枚比真币的重量轻的假币，若 采用分治法找出这枚假币，至少比较(63)次才能够找出该假币。(63)A.3B.4C.5D.6以下的算法设计方法中，(64)(64)A.回溯方法B.分治法以获取问题最优解为目标。C.动态规划D.递推归并排序采用的算法设计方法属于(65)。(65)A.归纳法 B.分治法 C.贪心法D.回溯方法第七部分算法:真题200911某算法的时间复杂度表达式为T(n尸aiP+bnlgn+cn+d,其 中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时 间复杂度为(63)。(63)A.O(i2)B.O(n)C.O(nlgn)D.0(1)L/O/G/OThank You!