计算机算法设计与分析期末考试复习题剖析

1、1、A、2、A、3、A、二分搜索算法是利用（A分治策略B、动态规划法下列不是动态规划算法基本步骤的是（找出最优解的性质最大效益优先是（分支界限法C、B、构造最优解AB、动态规划法4、A、5.A、6A、在下列算法中有时找不到问题解的是（蒙特卡罗算法B、拉斯维加斯算法回溯法解旅行售货员问题时的解空间树是（子集树B排列树）实现的算法。贪心法D、回溯法A）。C、算出最优解的一搜索方式。C、贪心法）。C、舍伍德算法A深度优先生成树）。C、下列算法中通常以自底向上的方式求解最优解的是（备忘录法B动态规划法衡量一个算法好坏的标准是（A运行速度快B占用空间少C、贪心法7、C）。C时间复杂度低D、定义最优解D、

2、回溯法D、数值概率算法D、BD、回溯法代码短广度优先生成树）。8、以下不可以使用分治法求解的是A棋盘覆盖问题B选择问题9、实现循环赛日程表利用的算法是（A、分治策略B动态规划法D）。C归并排序D0/1C、10、下列随机算法中运行时有时候成功有时候失败的是A数值概率算法B舍伍德算法C拉斯维加斯算法11下面不是分支界限法搜索方式的是（A、广度优先B最小耗费优先C、最大效益优先12下列算法中通常以深度优先方式系统搜索问题解的是（A、备忘录法B动态规划法13.备忘录方法是那种算法的变形。A、分治法B动态规划法C、BC、贪心法）贪心法14哈弗曼编码的贪心算法所需的计算时间为（A、O（n2）B、O（nlo

3、gn）15分支限界法解最大团问题时，活结点表的组织形式是（A、最小堆B最大堆16最长公共子序列算法利用的算法是（A、分支界限法B动态规划法17实现棋盘覆盖算法利用的算法是（A、分治法B动态规划法18. 下面是贪心算法的基本要素的是（A、重叠子问题B构造最优解19. 回溯法的效率不依赖于下列哪些因素（A.满足显约束的值的个数C.计算限界函数的时间C、O（2n）C、背包问题）。贪心法C）蒙特卡罗算法）。D、深度优先D回溯法D、C栈BC贪心法A贪心法C贪心选择性质）D、D回溯法）。O（n）BD、）。数组回溯法）。）。D回溯法）。）。C、DB.计算约束函数的时间D.确定解空间的时间D、D回溯法定义最优

4、解20. 下面哪种函数是回溯法中为避免无效搜索采取的策略（A.递归函数B.剪枝函数21. 下面关于NP问题说法正确的是ANP问题都是不可能解决的问题CNP完全问题是P类问题的子集C。随机数函数B）BP类问题包含在NP类问题中DNP类问题包含在P类问题中BD.搜索函数22、蒙特卡罗算法是（A、分支界限算法B）的一种。B、概率算法C、贪心算法D、回溯算法23.下列哪一种算法不是随机化算法（A.蒙特卡罗算法B.拉斯维加斯算法）C）C.动态规划算法D.舍伍德算法是贪心算法与动态规划算法的共同点。C贪心选择性质B）动态规划算法C、活结点表的组织形式是（C栈A）实现的算法。C、贪心法D、回溯法24. （D

5、A、重叠子问题B构造最优解25. 矩阵连乘问题的算法可由（A、分支界限算法26. 分支限界法解旅行售货员问题时，A、最小堆B最大堆27. Strassen矩阵乘法是利用（A、分治策略B、动态规划法29、使用分治法求解不需要满足的条件是（A子问题必须是一样的B子问题不能够重复用相同的方法解30、下面问题（B）不能使用贪心法解决。A单源最短路径问题BN皇后问题C31、下列算法中不能解决0/1背包问题的是（A贪心法B动态规划C回溯法D分支限界法32、回溯法搜索状态空间树是按照（C）的顺序。A中序遍历B广度优先遍历C深度优先遍历D层次优先遍历33、下列随机算法中运行时有时候成功有时候失败的是A数值概率

6、算法B舍伍德算法C拉斯维加斯算法34实现合并排序利用的算法是（A、分治策略B动态规划法35下列是动态规划算法基本要素的是（A、定义最优解B构造最优解B、A）。D、最优子结构性质设计实现。贪心算法C子问题的解可以合并最小花费生成树问题A）C）D蒙特卡罗算法）。C贪心法DC、算出最优解36下列算法中通常以自底向下的方式求解最优解的是（A、分治法B动态规划法37采用广度优先策略搜索的算法是（A、分支界限法B动态规划法38、合并排序算法是利用（AA、分治策略B、动态规划法C、贪心法39、在下列算法中得到的解未必正确的是（A、蒙特卡罗算法B、拉斯维加斯算法40、背包问题的贪心算法所需的计算时间为（A、O

7、（n2n）B、O（nlogn）41实现大整数的乘法是利用的算法（A、贪心法B动态规划法420-1背包问题的回溯算法所需的计算时间为A、O（n2n）B、O（nlogn）43采用最大效益优先搜索方式的算法是（A、分支界限法B动态规划法44贪心算法与动态规划算法的主要区别是（C、AC、）。D、回溯算法A）。D、数组原问题和子问题使D背包问题D、回溯法D、子问题重叠性质B贪心法）。D回溯法）。贪心法）实现的算法。D、回溯法B）。C、舍伍德算法BC、O（2n）CC、AD、D、D回溯法数值概率算法O（n）C、A）。分治策略O（2n）C贪心法）。）。D、D、回溯法O（n）D回溯法A、最优子结构B贪心选择性质

8、C构造最优解D、定义最优解45. 实现最大子段和利用的算法是（B）。A、分治策略B动态规划法C贪心法D、回溯法46. 优先队列式分支限界法选取扩展结点的原则是（C）。A、先进先出B后进先出C结点的优先级D、随机47. 背包问题的贪心算法所需的计算时间为（B）。AO(n2n)BO(nlogn)C0(2n)D、O(n)48、广度优先是（A）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法49、舍伍德算法是（B)的一种。A、分支界限算法B、概率算法C、贪心算法D、回溯算法50、在下列算法中有时找不到问题解的是（B）。A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法51下

9、列哪一种算法是随机化算法（D）A.贪心算法B.回溯法C.动态规划算法D.舍伍德算法52.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A、重叠子问题B最优子结构性质C贪心选择性质D、定义最优解53.采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（B）。AO(n2n)BO(nlogn)CO(2n)D、O(n)54.以深度优先方式系统搜索问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪心算法D、回溯算法55.实现最长公共子序列利用的算法是（B）。A、分治策略B动态规划法C贪心法D、回溯法二、填空题1.算法的复杂性有时间复杂性

10、和空间复杂性之分。2、程序是算法用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条_指令_是清晰的，无歧义的。4、矩阵连乘问题的算法可由动态规划设计实现。5、拉斯维加斯算法找到的解一定是_正确解。6、算法是指解决问题的_一种方法_或_一个过程_。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是_递归算法。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为回溯法_。10、数值概率算法常用于数值问题的求解。11、计算一个算法时间复杂度通常可以计算循环次数_、基本操作的频率_或计算步。12、利用概率的性质

11、计算近似值的随机算法是数值概率算法，运行时以一定的概率得到正确解的随机算法是蒙特卡罗算法。14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法,分支限界法。15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题_。17、矩阵连乘问题的算法可由_动态规划_设计实现。18、拉斯维加斯算法找到的解一定是正确解。19、贪心算法的基本要素是贪心选择_质和_最优子结构性质。21.动

12、态规划算法的基本思想是将待求解问题分解成若干子问题，先求解_子问题，然后从这些_子问题的解得到原问题的解。算法是由若干条指令组成的有穷序列，且要满足输入，输出、确定性和有限性四条性质。23、大整数乘积算法是用_分治法_来设计的。24、以广度优先或以最小耗费方式搜索问题解的算法称为_分支限界法_。25、舍伍德算法总能求得问题的一个解。贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。27快速排序算法是基于分治策略的一种排序算法。28.动态规划算法的两个基本要素是_最优子结构性质和重叠子问题一性质。30. 回溯法是一种既带有_系统性又带有_跳跃性_的搜索算法。31.

13、分支限界法主要有队列式（FIFO）分支限界法和优先队列式一分支限界法。32. 分支限界法是一种既带有系统性又带有跳跃性_的搜索算法。33. 回溯法搜索解空间树时，常用的两种剪枝函数为_约束函数和限界函数。34. 任何可用计算机求解的问题所需的时间都与其_规模_有关。35. 快速排序算法的性能取决于划分的对称性。1. 背包问题的贪心算法2.最大子段和：动态规划算法3.贪心算法求装载问题4.贪心算法求活动安排问题5.快速排序6.排列问题1分治法的基本思想时将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。2

14、设计动态规划算法的主要步骤为：（1）找出最优解的性质，并刻划其结构特征（2）递归地定义最优值（3）以自底向上的方式计算出最优值（4）根据计算最优值时得到的信息，构造最优解。3. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。4. 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。不同点：（1）求解目标不同；（2）搜索方式不同；（3）对扩展结点的扩展方式不同；（4

15、）存储空间的要求不同。5用回溯法搜索子集树的算法为：6. 分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）禾9用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。7. 用分支限界法设计算法的步骤是：（1）针对所给问题，定义问题的解空间（对解进行编码）；分（2）确定易于搜索的解空间结构（按树或图组织解）；（3）以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效

16、搜索。8. 常见的两种分支限界法的算法框架(1)队列式(FIFO)分支限界法：按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。(2)优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。9. 回溯法中常见的两类典型的解空间树是子集树和排列树。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需0(2n)计算时间。当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要0(n!)计算时间。10. 分支限界法的搜索策略是

17、：在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。五)掌握分治算法实例：二分查找、合并排序、冒泡排序、矩阵乘法1 、二分查找：例4二分搜索问题给定排好序的线性表a0:n-1二分搜索递归算法Binarysearch(a,n1,n2,x)if(n1>n2)return(-1);m=(n1+n2)/2;if(x=am)return(m);el

18、seif(x<am)Binarysearch(a,n1,m-1,x);elseBinarysearch(a,m+1,n2,x);复杂度O(logn)2、合并排序：例6合并排序问题设线性表a1:n，将其按从小到大排序。基本思路:1 将a1:n分为a1:n/2和an/2+1:n两个表2 各自单独排序，3 再将排好序的两个表合并为一个表合并排序算法Mergesort(a,left,right)if(left<right)i=(left+right)/2;Mergesort(a,left,i);Mergesort(a,i+1,right);Merge(a,b,left,i,right);c

19、opy(a,b,left,right);合并排序算法中合并算法Merge(a,b,left,l,right)k=left;k仁left;k2=i+1;while(k1<=landk2<=right)if(ak1<ak2)bk=ak1;k1+;k+;elsebk=ak2;k2+;k+;if(k1=i)for(l=k2;l<=right;l+)bk=al;k+;elsefor(l=k1;l<=i;l+)bk=al;k+;合并排序算法分析Merge()函数最多3n次赋值，3n次比较0(1)n=1T(n)=2T(n/2)+6nn>1解方程得：T(n)=n+6nlog

20、2n=O(nlog2n)3、矩阵乘法：汝nxn处随49的观积刃6C=AXBU旳毎十兀秦u侶做n次乘法*n-F次加法#玮有门盏个开亲，计漳吋I旬刈Ofn齐.feStn刘52旳畑数砖，21111G1=A11B11+A12B21C21=A21B11+A22B21Cl2=A11Bl2+A12B22C22=1B12+A22B22成为8个n/2阶矩阵乘积，4个n/2阶矩阵加法。如杲以数的乘法作为基本运算，则可得到分块矩阵乘法的递归方程8(O(1)n=2T(n)=8T(n/2)n>2代入递归方程得T(n)=n320世纪60年代末期。Strassen给出了以下算法:M=A1(B12-B22)M=(Ah+

21、A12)B22MI=(A21+A22)B11M=A22(B21-B11)M=(Aii+A22)(B11+B22)M6=(Ai2-A22)(B21+B22)M7=(Aii-A21)(B11+B12)Oi=MB+M4-M2+M6G2=M+MO2=M+MOi=M5+M-M3M7使用了7个n/2阶矩阵乘积，18个n/2阶矩阵加法，其算法复杂度为0(n1)2.81=log27算法procedureSTRASSEN(n,A,B,C);beginifn=2thenMATRIX-MULTIPLY(A,B,C)elsebegin将矩阵A和B依(1)式分块；STRASSEN(n/2,A11,B12-B22,M1)

22、;STRASSEN(n/2,A11+A12,B22,M2);STRASSEN(n/2,A21+A22,B11,M3);STRASSEN(n/2,A22,B21-B11,M4);STRASSEN(n/2,A11+A22,B11+B22,M5);STRASSEN(n/2,A12-A22,B21+B22,M6);STRASSEN(n/2,A11-A21,B11+B12,M7);end;end;3、快速排序：例7快速排序对输入的数组ap:r按以下三个步骤进行：分：中的元排序。(1) 分解(Divide),以ap为基准元素将ap:r划分为三部ap:q-1,aq,aq+1:r,使得ap:q-1中的元素小于

23、aq,aq+1:r素大于aq.(2) 递归求解(Conquer),通过递归调用快速排序算法分别对ap:q-1，aq+1:r(3) 合并(merge),由于已排好序，合并不需作什么快速排序递归算法：Quicksort(a,p,r)if(p<r)q=partition(a,p,r);Quicksort(a,p,q-1);Quicksort(a,p,q-1);快速排序算法分析Partition(a,p,r)计算时间为0(r-p+1),即f(n)=n最好情况，每次q=(p+r)/20(1)n=1T(n)=2T(n/2)+nn>1解方程得：T(n)=n+nlog2n=O(nlog2n)最坏情

24、况，每次q=p或q=rO(1)n=1T(n)=T(n-1)+nn>1解方程得：T(n)=O(n第三章(六) 、掌握贪心策略基本思想及基本性质，并能证明贪心选择性质1、贪心策略基本思想：和动态规划类似,贪心法用于多阶段的决策过程,每个阶段都有可供选择的多种决策,各个阶段的决策构成一个决策序列.贪心法的目标是选取一个最优的决策序列.2、基本性质：贪心法选择决策的原则是局部最优,而不是全局最优。如果一个问题的整体最优解可以通过一系列局部最优选择来实现,称该问题具有贪心选择性质.贪心选择性质是贪心法可行的一个基本要素.它是保证贪心法的求解结果为最优解的条件.最优子结构性质3、证明：(七) 、掌握

25、贪心策略实例：最小生成树、背包问题、作业调度问题1、背包问题：给定n个重量为(W1,W2,Wn),价值为(V1,V2,-Vn)的物品和一个容量为C的背包,要求选择部分物品装进背包,使得背包内物品价值总和最大.1) 问题的解(X1,x2,Xn)0<Xi<12) 约束条件刀Xiw<C3) 目标函数刀XiVi达到最大解题思路:1) 尽可能多选择价值大的物品.2) 尽可能多选择重量轻的物品.3) 尽可能多选择价值/重量比大的物品.贪心法的一般过程1) 根据题意选取一种度量标准或贪心策略.2) 按度量标准对n个输入排序.3) 按序做出贪心选择.4) 检查该选择是否与前面的选择构成可行解

26、.5) 如果可行,则将该选择加入解中,否则不加入.6) 继续做下一步选择.Greedy-knapsack()将物品按V/W从大到小排序for(i=1;i<=n;i+)Xi=0;for(i=1;i<=n;i+)if(Wi<c)Xi=1;c=c-WielseXi=cu/Wi;break;outputX1Xn第四章(八) 掌握动态规划的基本思想及解题步骤1、动态规划的基本思想：动态规划是和过程最优化概念紧密联系的.在过程进行中,在客观条件允许范围内选择最好的措施控制过程的发展,以期最好的完成任务.动态规划用于多阶段的决策过程,每个阶段都有可供选择的多种决策,各个阶段的决策构成一个决

27、策序列.动态规划的目标是选取一个最优的决策序列2、解题步骤：动态规划法设计步骤 找出最优解的性质,并刻画其结构(最优子结构)特征. 递归地定义最优值,导出递推公式. 以自底向上的方式计算最优值. 根据计算最优值时得到的信息,构造最优解.形式：如：1)问题的解:边的序列,每一步决策选择一条边<AC>,<CF>,<FI>,<IJ>,<JL>2)约束条件:两个顶点之间有边存在3)可行解:满足约束条件的解4) 目标函数:解中边的权值和达到最小5) 最优解:使目标函数取极值的可行解(九) 、掌握动态规划实例：投资分配问题、货币分配问题、0-1背

28、包问题1投资分配问题：总资源数为a,工程个数为n。给每个工程投资不同，所获得的利润也不同。现给定各个工程的资源利润表和资源总数，问:如何分配资源，才能获得最大利润。记Fn(a)为给n个工程投资资源数为a时可获得的最大利润,则有：Fn(a)=maxGi(xi)+G2(x2)+Gn(xn)xl+X2+Xn=a如果给第n项工程投资X，给前n-1项工程投资a-x，贝UFn(a)=maxFn-i(a-x)+Gn(x)X(0,1,a)记Fk(z)为给k个工程投资总资源数为z时可以获得的最大利润，则有递推公式：Fk(z)=maxFk-i(z-x)+Gk(x)Z(0,1,a)X(0,1,-,z)Fi(z)=G

29、i(z)利用这一递推公式,我们可以得出该问题的算法。投资问题算法Investing(m,n,gij)for(j=0;j<=m;j=j+i)fij=gij;dij=jfor(i=2;i<=n;i=i+i)for(j=0;j<=m;j=j+i)fij=0;for(k=0;k<=j;k=k+i)s=fi-ij-k+gikif(s>fij)fij=s;dij=k构造最优解m总投资数额。n工程总项数。gIJ存放资源利润表，I为工程号，J为投资数额构造最优解s=mxn=dnmfor(k=n-1;k>0;k=k-1)s=s-xk+1;xk=dks;for(k=1;k<

30、;=n;k=k+1)outputxkoutputfnmdIJ给前I项工程投资额为J,获最大利润时第I项的投资额20/1背包问题：给定n个重量为(W1,W2,Wn),价值为(V1,V2,-Vn)的物品和一个容量为C的背包,要求选择部分物品装进背包,使得背包内物品价值总和最大.1) 问题的解(XI,x2,Xn)xi=0,12) 约束条件刀Xiw<=C3) 目标函数刀XiVi达到最大0/1背包问题的特征第一步决策第n种物品是否装入背包.剩余问题是给定n-1个重量为(wi,W2,wn-i),价值为(V1,V2,V-1)的物品和一个容量为C-Wn*Xn的背包的0/1背包问题递归地定义最优值,导出递推公式.V(n,c)=maXV(n-1,C),V(n-1,C-Wn)+Vn0i=0V(i,j)=V(i-1,j)j<WimaXV(i-1,j),V(i-1,j-Wi)+Vij>=Wi0/1背包问题的算法Knapsack()for(i=1;i<=n;i+)Vi0=0for(j=1;j<=C;j+)V0