算法设计与分析期末试卷A卷

A卷一、选择题1.二分搜索算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2.回溯法解旅行售货员问题时的解空间树是（A）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树3.下列算法中通常以自底向上的方式求解最优解的是（B）。A、备忘录法B、动态规划法C、贪心法D、回溯法4．下面不是分支界限法搜索方式的是（D）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）6．分支限界法解最大团问题时，活结点表的组织形式是（B）。A、最小堆B、最大堆C、栈D、数组7、下面问题（B）不能使用贪心法解决。A单源最短路径问题BN皇后问题C最小花费生成树问题D背包问题8.下列算法中不能解决0/1背包问题的是（A）A贪心法B动态规划C回溯法D分支限界法9.背包问题的贪心算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）10.背包问题的贪心算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）二、填空题1.算法的复杂性有复杂性和复杂性之分。2.算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。其中算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。4.动态规划算法的两个基本要素是.性质和性质。5.回溯法是一种既带有又带有的搜索算法；分支限界法是一种既带有又带有的搜索算法。6.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为。7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）。BoolColor::OK(intk){//for(intj=1;j=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}8.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为nm的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时，构造相应的最短距离需要时间。for(inti=0;iNumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//该方格未标记grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布线Q.Add(nbr);}}9.快速排序算法是基于的一种排序算法。10.是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别三．简答题1.设计动态规划算法的主要步骤是怎么的？请简述。2.分治法所能解决的问题一般具有哪几个特征？请简述。3.分支限界法的搜索策略是什么？四．计算题1.已知非齐次递归方程：f(n)bf(n1)g(n)f(0)c，其中，b、c是常数，g(n)是n的某一个函数。则f(n)的非递归表达式为：nnnii1f(n)cbbg(i)。现有Hanoi塔问题的递归方程为：h(n)2h(n1)1h(1)1，求h(n)的非递归表达式。2.给定带权有向图（如下图所示）G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。五．程序题4321{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代1.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。2.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：（1）删除一个字符。（2）插入一个字符。（3）将一个字符改为另一个字符。请写出该算法。答案：一、AABDBBBABB二、1.时间空间2.输出有限性指令3.动态规划回溯法分支限界法4.最优子结构重叠子问题5.系统性跳跃性系统性跳跃性6.（O(h(n))）7.O（mn）8.O(mn)O(L)9.分治策略10.贪心选择性质三、1.（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。2.（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。3.在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。四、1.解：利用给出的关系式，此时有：b=2,c=1,g(n)=1,从n递推到1，有：n1n1n1ii1n1n22nh(n)cbbg(i)22...221212.五．程序题1.解：intgreedy(vecterintx,intn){603050105{1，2，3，4，5}4603050103{1，2，4，3}3903050104{1，2，4}21003060102{1，2}11003010-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代intsum=0,k=x.size();for(intj=0;jk;j++)if(x[j]n){cout”Nosolution”endl;return-1;}For(inti=0,s=0;ik;i++){S+=x[i];if(sn){sum++;s=x[i];}}returnsum;}2.解：此题用动态规划算法求解：intdist(){intm=a.size();intn=b.size();vectorintd(n+1，0);for(inti=1;i=n;i++)d[i]=i;for(i=1;i=m;i++){inty=i-1;for(intj=1;j=n;j++){intx-y;y=d[j];intz=j1?d[j-1]:i;intdel=a[i-1]==b[j-1]?0:1;d[j]=min(x+del,y+1,z+1);}}returnd[n];}