资源描述：
《《算法分析与设计》期末考试复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《算法分析与设计》期末复习题贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。不足之处：如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解
2、，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加
3、以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。一、选择题1.应用Johnson法则的流水作业调度采用的算法是（D）A.贪心算法B.分支限界法C.分治法D.动态规划算法2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）A.voidhanoi(intn,intA,intC,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,
4、C,B,A);}}Hanoi塔B.voidhanoi(intn,intA,intB,intC){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}D.voidhanoi(intn,intC,intA,intB){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}C.voidhanoi(intn,intC,intB,intA){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hano
5、i(n-1,C,B,A);}}3.动态规划算法的基本要素为（C）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用4.算法分析中，记号O表示（B），记号表示（A），记号表示（D）。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界渐进精确界记号E.非紧下界5.以下关于渐进记号的性质是正确的有：（A）A.B.C.O(f(n))+O(g(n))=O(min{f(n),g(n)})D.6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A.最优子结构性质与贪心
6、选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用7.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先8.分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A．广度优先B.活结点优先C.扩展结点优先D.深度优先9.程序块（A）是回溯法中遍历排列树的算法框架程序。voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x
7、[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}A.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}B.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}C.D.voidback
8、track(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}10.回溯法的效率不依赖于以下哪一个因素？（C）A.产生x[k]
