复习题目

一选择题1、一个算法应该包含如下几条性质，除了。（A）二义性（B）有限性（C）正确性（D）可终止性2、当输入规模为n时，算法增长率最小的是。（A）5n（B）20log2n（C）2n2（D）3nlog3n3当输入规模为n时，算法增长率最大的是。AA．5nB．20log2nC．2n2D．3nlog3n4在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。DA．随机选择一个元素作为划分基准B．取子序列的第一个元素作为划分基准C．用中位数的中位数方法寻找划分基准D．以上皆可行。但不同方法，算法复杂度上界可能不同5分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。CA．问题规模相同，问题性质相同B．问题规模相同，问题性质不同B．问题规模不同，问题性质相同D．问题规模不同，问题性质不同6对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为。BA．n!B．2nC．2n+1-1D．niin1!/!7下列哪些问题不能用贪心法求解？（）A)霍夫曼编码问题B)单源最短路径问题C)0-1背包问题D)最小生成树问题8二分搜索算法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法9回溯法解旅行售货员问题时的解空间树是（）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（）。A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（）。A运行速度快B占用空间少C时间复杂度低D代码短9.实现循环赛日程表利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法10．下列算法中通常以深度优先方式系统搜索问题解的是（）。A、备忘录法B、动态规划法C、贪心法D、回溯法11．哈弗曼编码的贪心算法所需的计算时间为（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）12.下面是贪心算法的基本要素的是（）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解13.下面哪种函数是回溯法中为避免无效搜索采取的策略（）A．递归函数B.剪枝函数C。随机数函数D.搜索函数14.矩阵连乘问题的算法可由（）设计实现。A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法15、使用分治法求解不需要满足的条件是（）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解16、下列算法中不能解决0/1背包问题的是（）A贪心法B动态规划C回溯法D分支限界法17．实现合并排序利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法18．下列是动态规划算法基本要素的是（）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质19．下列算法中通常以自底向下的方式求解最优解的是（）。A、分治法B、动态规划法C、贪心法D、回溯法20实现大整数的乘法是利用的算法（）。A、贪心法B、动态规划法C、分治策略D、回溯法二填空题：1回溯算法的基本思想是在问题的状态空间树上作带剪枝的DFS搜索（或：DFS+剪枝）。2．动态规划和分治法在分解子问题方面的不同点是前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的。3．选择排序、插入排序和归并排序算法中，归并排序算法是分治算法。4、一个直接或间接调用自身的算法称为递归算法。5出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。6使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（1），在最坏情况下，搜索的时间复杂性为O（logn）。7动态规划算法的基本要素是最优子结构性质和子问题重叠性质8贪心算法的基本要素是贪心选择性质和最优子结构性质。9四后问题的搜索空间为（排列）树；0-1背包问题的搜索空间为（子集）树；巡回售货员问题的搜索空间为（满m叉）树。10有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（{1，4，8，11}）。11所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。12所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。三简答题1413121110987654f[i]122886535031S[i]1110987654321i1有4个矩阵},,,{421AAA，连乘积为421AAA。其中iA与1iA是可乘的，321,,i。在这个四矩阵连乘积问题中，不同子问题的个数为4＋C(4,2)＝10个。请写出这10个子问题．．．。A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n个C(n,2)个2有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。解：一共要要执行四次才能找到值为82的数。3现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n–1天。请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。参考解答：12345678214365873412785643218765567812346587214378563412876543214对于矩阵连乘所需最少数乘次数问题，其递归关系式为：1ikj0[,]min{[,][1,]}ikjijmijmikmkjpppij其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，ip为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：A1A2A3A4501010404030305p0p1p1p2p2p3p3p4请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。参考解答：014024034[1][1][2][4]080005010510500[1][4]min[1][2][3][4]2000060005040536000[1][3][4][4]270000503053450010500mmpppmmmpppmmppp5单源最短路径的求解。问题的描述：给定带权有向图（如下图所示）G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。6考虑使用动态规划方法求解下列问题：01背包数据如下表，求：能够放入背包的最有价值的物品集合。物品重量价值承重量432110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代iwiviW1w1=2v1=12W=52w2=1v2=103w3=3v3=204w4=2v4=15如设：V(i,j)——前i个物品中能够装入承重量j的背包中的最大总价值。请将如下递推式填写完整：V(0,j)=0（0个物品），V(i,0)=0（承重量0）V(i,j)=V(i-1,j)第i个物品不能装入，jwi（超重）V(i,j)=max{,}jwi（不超重）i在最优子集中i不在最优子集中自底向上：按行或列填写下表。答：V(0,j)=0（0个物品），V(i,0)=0（承重量0）V(i,j)=V(i-1,j)第i个物品不能装入，jwi（超重）Vj=012345i=000000010203040Vj=012345i=000000010203040V(i,j)=max{vi+V(i-1,j-wj),V(i-1,j)}jwi（不超重）i在最优子集中i不在最优子集中7请画出用回溯法解4皇后问题的解空间树和搜索空间树：解空间树：8请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20,15,10}，价值为{20,30,25}，背包容量为25时搜索空间树。答：解空间树：Vj=012345i=000000010203040Vj=012345i=000000010012121212201012222222301012223032401015253037搜索空间树：1不可行解价值=20价值=55价值=30价值=25价值=011110000001128111214151310691111110000000112345781112141531069用回溯法的搜索空间树：四算法设计题:1分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。（1）贪心算法O（nlog（n））首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体算法可描述如下：voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i=n;i++)x[i]=0;floatc=M;for(i=1;i=n;i++){if(w[i]c)break;x[i]=1;c-=w[i];}if(i=n)x[i]=c/w[i];}（2）动态规划法O(nc)m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。voidKnapSack(intv[],intw[],intc,intn,intm[][11]){intjMax=min(w[n]-1,c);for(j=0;j=jMax;j++)/*m(n,j)=00=jw[n]*/m[n][j]=0;for(j=w[n];j=c;j++)/*m(n,j)=v[n]j=w[n]*/iiiiwjwjjimvwjimjimjim0),1(}),1(),,1(max{),(nnnwjwjvjnm00),(m[n][j]=v[n];for(i=n-1;i1;i--){intjMax=min(w[i]-1,c);for(j=0;j=jMax;j++)/*m(i,j)=m(i+1,j)0=jw[i]*/m[i][j]=m[i+1][j];for(j=w[i];j=c;j++)/*m(n,j)=v[n]j=w[n]*/m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}（3）回溯法O(2n)cw:当前重量cp:当前价值bestp：当前最优值voidbacktrack(inti)//回溯法i初值1{if(in)//到达叶结点{bestp=cp;return;}if(cw+w[i]=c)//搜索左子树{cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)bestp)//搜索右子树backtrack(i+1);}