算法设计和分析期末试题汇总.doc

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）动态规划算法的主要步骤Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。 程序题 试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。 2.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括： （1）删除一个字符。 （2）插入一个字符。 （3）将一个字符改为另一个字符。 请写出该算法。 答案： AABDB BBABB 时间 空间 输出 有限性 指令 动态规划 回溯法 分支限界法 最优子结构 重叠子问题 系统性 跳跃性 系统性 跳跃性 6. （O(h(n)) ） O（mn） O(mn) O(L) 分治策略 贪心选择性质 （1）找出最优解的性质，并刻划其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造最优解。 （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; 利用该问题分解出的子问题的解可以合并为该问题的解； （4） 2. 程序题 1.解：int greedy(vecterintx,int n) { int sum=0,k=x.size(); for(int j=0;jk;j++) if(x[j]n){ cout”No solution”endl; return -1; } For(int i=0,s=0;ik;i++){ S+=x[i]; if(sn){sum++;s=x[i];} } return sum; } 2.解：此题用动态规划算法求解： int dist() { int m=a.size(); int n=b.size(); vectorintd(n+1，0); for(int i=1;i=n;i++)d[i]=i; for(i=1;i=m;i++){ int y=i-1; for(int j=1;j=n;j++){ int x-y; y=d[j]; int z=j1?d[j-1]:i; int del=a[i-1]==b[j-1]?0:1; d[j]=min(x+del,y+1,z+1); } } return d[n]; } 一、填空题（每小题3分，共30分） 1、 2、3、( 记号在算法复杂性的表示法中表示 。 5、由分治法产生的子问题往往是 ，这就为使用 提供了方便。 6、 7、8、最优子结构性质的含义是。 9、。 10、拉斯维加斯算法找到的解一定是。 二、选择题（每小题2分，共20分）1、利用（）算法实现。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法、下列不是的是（ ）。A、 B、 C、 D、列算法中通常以自顶向下的方式求解最优解的是（ ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法在对问题的解空间树进行有哪些信誉好的足球投注网站的方法中,一个活结点有多次机会成为活结点的是( ) A、回溯法 B、分支限界法C、回溯法和分支限界法 D、动态规划 5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策