2022年算法分析与设计习题集整理 .pdf

《2022年算法分析与设计习题集整理 .pdf》由会员分享，可在线阅读，更多相关《2022年算法分析与设计习题集整理 .pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计习题集整理第一章算法引论一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。2、多项式10()mmA na na na的上界为 O(nm)。3、算法的基本特征：输入、输出、确定性、有限性、可行性。4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为：O(n3)。for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj;6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。7、算法设计的基本要求：

2、正确性和 可读性。8、计算下面算法的时间复杂度记为：O(n2)。for（i 1；in;i+）y=y+1;for（j 0；j=2n；j+）x；9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。10、算法是指解决问题的方法或过程。11、算法由 操作、控制结构、数据结构三要素组成。二、简答题：1、按照时间复杂度从低到高排列：O(4n2)、O(logn)、O(3n)、O(20n)、O(2)、O(n2/3),O(n!)应该排在哪一位？答：O(2)，O(logn)，O(n2/3)，O(20n)，O(4n2)，O(3n)，O(n!)2

3、、什么是算法？算法的特征有哪些？答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2）特征：1)算法有零个或多个输入；)算法有一个或多个输出；3)确定性；)有穷性名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 30 页 -3、给出算法的定义？何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？for(j=1;j=n;j+)(1)for(i=1;i=n;i+)(2)cij=0;(3)for(k=1;k=n;k+)(4)cij=cij+aik*bkj;(5)答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问

4、题结果的处理过程。2）算法的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。所需资源越多，表明算法的复杂性越高 3）该算法的主要元操作是语句5，其执行次数是n3次。故该算法的时间复杂度记为 O(n3).4、算 法A 和 算 法B 解 同 一 问 题，设 算 法A 的 时 间 复 杂 性 满 足 递 归 方 程1n,n)2/n(T4)n(T1n,1)n(T，算法 B 的时间复杂性满足递归方程1n,n)4/n(aT)n(T1n,1)n(T，若要使得算法A 时间复杂性的阶高于算法B时间复杂性的阶，a 的最大整数值可取多少？答：分别记算法A和算法 B的时间复杂性为)n(TA和)n(TB，

5、解相应的递归方程得：)n(O)n(T2A4a,)n(O4a,)nlogn(O4a,)n(O)n(TalogB4依题意，要求最大的整数a 使得)n(TB)n(TA。显然，当 a4 时，)n(TB(n)TA2alog4a2 写出其相应的递归算法？Int F(int n)if(n=1)return 1;else if(n=2)return 2;else return F(n-1)+F(n-2);2、设 a,b,c是 3 个塔座。开始时，在塔座a 上有一叠共n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a 上的这一叠圆盘移到塔座 b 上，并仍按同样顺序叠

6、置。在移动圆盘时应遵守以下移动规则：规则 1：每次只能移动1 个圆盘；规则 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则 3：在满足移动规则1 和 2 的前提下，可将圆盘移至a,b,c中任一塔座上。写出该问题的解题步骤？并写出其相应的递归算法？解：第一步：将n1 个盘子看成一个整体，从A移到 C；第二步：将第n 个盘子移到B;第三步：将n1 个盘子看成一个整体，从C移到 B；写出其相应的递归算法：void hanoi(int n,int a,int b,int c)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);名师资料总结-精

7、品资料欢迎下载-名师精心整理-第 4 页，共 30 页 -第二章分治算法（2）分治算法一、填空题：1、在快速排序、插入排序和合并排序算法中，插入排序算法不是分治算法。2、合并排序算法使用的是分治算法设计的思想。3、二分搜索算法是利用分治算法思想 设计的。二、简答题：1、适合用分治算法求解的问题具有的基本特征？答：1)该问题的规模缩小到一定的程度就可以容易解决;2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。4）利用该问题分解出子问题解可以合并为该问题解;2、分治算法基本思想，解题步骤？三、算法

8、设计题：1、改写二分查找算法：设 a1 n 是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x 不在数组中时，返回小于x 的最大元素位置i，和大于 x 的最小元素位置j；当搜索元素x 在数组中时，i 和 j 相同，均为x 在数组中的位置。并分析其时间复杂度？解：int binsearch(int an,int x,)/x待查数据int mid,i,j;low=1;int high=n;while(lowx)high=mid-1;/继续在左边查找else /(amid=2）个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题：1）将数据等分为两组（两组数据

9、可能差1），目的是分别选取其中的最大（小）值。2)递归分解直到每组元素的个数2,可简单地找到最大(小)值.3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。、名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 30 页 -第三章动态规划算法一、填空题：1、动态规划算法中存储子问题的解是为了避免重复求解子问题。2、（最优子结构）是问题能用动态规划算法求解的前提。3、矩阵连乘问题的算法可由（动态规划）算法设计实现。二、判断题：1、动态规划算法基本要素的是最优子结构。（）2、最优子结构性质是指原问题的最优解包含其子问题的最优解。（）3、动态规划算法求解问题时，分解出来的子问题

10、相互独立。（X）三、简答题：1、动态规划算法解题步骤？答：找出最优解的性质，并刻划其结构特征;（即原问题的最优解，包含了子问题的最优解）递归地定义最优值;（即子问题具有重叠性，由子问题定义原问题）以自底向上的方式计算出最优值;根据计算最优值时得到的信息，构造最优解;2、动态规划算法基本思想？答：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题；但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次；如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间

11、算法。3、动态规划与分治算法异同点？4、动态规划算法的基本要素？名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 30 页 -四、算法设计与计算题：1、12,mXx xxL和12,nYyyyL的最长公共子序列为12,kZz zzL。问：若用 c ij记录序列12,iiXx xxL和12,jjYy yyL公共子序列长度。求：用动态规划法求解时,计算最优值的递归公式？设计计算最优值的算法？以及构造最优解的算法？2、长江游艇俱乐部在长江上设置了n 个游艇出租站1,2 n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间的租金为r(i

12、，j)，其中 1=ij=n；求：用动态规划法求解时,计算最优值（最少租金）的递归公式？设计计算最优值（最少租金）的算法？并分析其时间复杂度？解：计算最优值算法public static void matrixChain(int p,int m,int s)int n=p.length-1;for(int i=1;i=n;i+)mii=0;/1个站 for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;m i j=mii +mi+1 j;s i j=i;/断点位置在i 处 for(int k=i+1;k j;k+)int t =m i k +

13、mk+1 j;if(t mij)m i j=t;s i j=k;构造最优解算法public void traceback(int s,int I,int j)if(i=j)return;traceback(s,i,s i j);traceback(s,s i j+1,j);jijkrkirjijir,1,min0,jki名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 30 页 -System.out.println(“A”+i+“，”+s i j+“A”+s i j+1+“,”+j)/(m i,s i j )(m s i j+1,j )时间复杂度：O(n3)第 4 章 贪心算法一

14、、填空题：1、某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱,且取款的张数最少，统计所需各种币值(100,50,20,10,5,2,1元共七种)的张数。贪心算法如下：void greedy_zhaoling(float GZ,int B,int S )/GZ应发工资 for(j=1,j=7;j+)/贪心选择，依次给最大币种 A=GZ/B j;/A表示对应j 币种张数 S j=S j+A ;/S j存放对应j 币种总张数 GZ=GZ-A*B j ;for(i=1;i=7;i+)print(B i,“-”,S i );/输出币种和对应张数 2、贪心算法的两个基本要素是（贪心选择性）和

15、（最优子结构）。3、给定 n 种物品和一个背包。物品i 的重量是 Wi，其价值为Vi，背包的容量为M，应如何选择装入背包的物品，使得装入背包中物品的总价值最大。贪心算法如下：float greedy_knapsack(float M,float w,float p,float x )/x 背包问题最优解,w 物品重量，P 物品价值 int n=w.length;float pp=0;float mm M;/pp计算当前总价值，mm 背包剩余载重for(int i=1;i=n;i+)float ww i=p i/w i ；/计算物品单位价值ww x i=0;/初始化Mergesort(w,n);

16、/按单位价值将物品排序，便于贪心选择for(int i=1;i=n;i+)/贪心选择，总是选择价值最大放入背包 if(w i=mm)/当前物品小于背包剩余载重 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 30 页 -x i=1;mm=mm-w i ;pp=pp+p i ;else x i=mm/w i;pp=pp+x i*p i;break;/i部分放入背包 return pp;二、判断题：1、满足贪心选择性质必满足最优子结构性质。（X ）三、简答题：1、贪心算法的基本思想？2、贪心算法的基本要素？3、贪心算法与动态规划算法的异同?四、算法设计题：1、假设有7 个物品，它们的

17、重量和价值如下表所示。若这些物品均可以被分割，且背包容量 M 150，如果使用贪心方法求解此背包问题（背包不超载的前提下，装载的物品价值达到最大）。利用贪心算法求解该问题时，为了进行贪心选择，首先应该做什么？然后进行贪心装载，给出一种正确的物品装载顺序？并给出其最优装载方案？利用贪心思想设计该普通背包问题的贪心算法？分析其时间复杂度？解：1）依据不同的标准对这些物品进行排序，标准有重量、价值、单位价值；2）重量从小到大：FGBAEDC,得到的贪心解为：FGBAE 全部放入,D 放入 20%，得到价值为 165；价值从大到小：DFBEGCA，得到的贪心解为：DFBE 全部放入,G 放入 80%，

18、得到价值为 189；单位价值从大到小：FBGDECA，得到的贪心解为：FBGD 全部放入,E 放入 87.5%，得到价值为190.625；物品A B C D E F G 重量35 30 60 50 40 10 25 价值10 40 30 50 35 40 30 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 30 页 -3)显然使用单位价值得出最佳转载方案。、2、设有 n个活动集合，其中每个活动都要求使用同一资源，如足球场，而在同一时间只能有一个活动使用该资源。每个活动 i 都有一个要求使用该资源起始时间si 和结束时间fi，且 si n)/搜索到叶子节点 sum+;/着色方案

19、数加1 for(int i=1;i=n;i+)system.out.print(x i);/输出解,顶点 i 着颜色 x i else /搜索到中间节点 for(int i=1;i=m;i+)x t=i;/顶点 t 着颜色 i=1 m if(ok(t)backtrack(t+1);boolean ok(int k)/当前着色顶点与以前相邻顶点是否同色1 2 3 4 5 名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 30 页 -for(int j=1;j=n;j+)if(a k j&(x j=x k)/数组 a是图的邻接矩阵 /当前顶点 k 到 j 有边：a k j，且色同：x

20、 j=x k return false;else return true;算法分析（m种颜色，n 个节点）计算限界函数，一重for循环时间复杂度：O(n);在 最 坏 的 情 况 下 每 一 个 内 节 点 都 需 要 判 断 约 束，内 节 点 个 数：1+m+m2+m3+mn-1=(mn-1)/(m-1)个；故图的 m着色问题的回溯算法，时间复杂度为：O(n*mn)。名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 30 页 -第六章分支限界算法一、填空题1、按照活结点表的组织方式的不同，分支限界法包括队列式分支限界算法和优先队列式分支限界算法两种形式。2、回溯法与分支限界法

21、搜索方式不同，回溯法按深度优先搜索解空间，分支限界法按广度优先或最小耗费优先搜索解空间。3、队列分支限界算法中，通常用队列实现，体现先进先出原则的原则。4、优先队列式分支限界算法，通常采用堆实现。6、回溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构,其解空间结构通常有 3 种形式，分别是子集树、排列树、满 m叉树。二、判断题1、分支限界法类似于回溯法，也是一种在问题的解空间树T 上搜索问题解的算法，两者的搜索方式是相同的。（X）三、简答题1、简述分支限界法的基本思想与解题步骤？2、分支限界算法与回溯算法异同点？四、算法设计题1、01 背包问题：假设有 3 个物品，它们的重量和价值如

22、下表所示。若这些物品均不可以被分割，且背包容量 M 10，问应该如何装入使背包中物品的总价值最大？用分支限界算法求解该01 背包问题：构造求解该问题的解空间树？给出队列式分支限界算法的求解过程？如法1：队列式（FIFO 先进先出）分支限界法?从根结点1 开始；将活结点组织成一个队列；?初始时活结点队列为空，结点加入队列，结点1 为当前扩展结点；92?结点1 的孩子结点2、9 为可行结点，故舍弃当前结点1，将2、9 加入活结点队列；1?先进先出原则，2 作为当前扩展结点，其孩子结点3、6；由于结点3 是不可行结点舍弃；将结点6 加入活结点队列；69?先进先出原则，9 作为当前扩展结点，其孩子结点

23、10、13;结点10、13 是可行结点加入活结点队列；13106设计该 01 背包问题的分支限界算法？并分析其时间复杂度？（队列式分支限界，带上界函数）物品A B C 重量6 5 5 价值42 25 30 名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 30 页 -、多段图最短路径问题求：构造求解该问题的解空间树？给出队列式分支限界算法的求解过程？设计该问题的分支限界算法？并分析其时间复杂度？（队列式分支限界，带上界函数）解：2）求解过程：名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 30 页 -）算法描述：法:队列式分支限界法double shortest(

24、int i)while(true)/队列不空，搜索问题的解空间 for(int j=1;j=n;j+)/儿子结点入队 if(a i j Float.MAX_VALUE)/顶点 i 到顶点 j 可达 dist j=dist i+a i j;/dist i记录源到顶点的距离 p j=enode.i;/p j记录顶点j 的前驱 enQueue(v j,j);/结点 j 加入队列 ew=(Integer)queue.remove().intValue();/取队首下一扩展结点 if(ew=-1)/同一层尾部标记ew=-1：同一层结点处理结束 if(queue.isEmpty()return dist

25、i;/判断队列是否为空else queue.put(new Integer(-1);/同层结点尾部标志ew=(Integer)queue.remove().intValue();/取下一扩展结点 i+;/进入下一层 时间复杂度：名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 30 页 -第七章概率算法1、什么叫概率算法？答：概率算法允许算法在执行的过程中随机选择下一个计算步骤。2、概率算法有一个基本特征？答：基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。3、概率算法可以分为哪4 类？答：1)数值概率算法2)蒙特卡罗算法3)拉斯维加斯算法4)舍伍德

26、算法4、在概率算法中使用的 随机数都是一定程度上随机的，即伪随机数；一般随机数通过线性同余法方法产生。第八章 NP 完全性理论1、什么是易解问题？什么是难解问题？难解问题分为哪两类？答：1）易解问题：人们将存在多项式时间算法的问题称为易解问题;2）难解问题：将需要在指数时间内解决的问题称为难解问题；3）难解问题有两类：1）不可判定问题 2）非决定的难处理问题。2、什么是不可判定问题？什么是非决定的难处理问题？答：1）不可判定问题：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。2）非决定的难处理问题：这类问题是可判定的（即可解的）。但是，这类问题即使使用非决定的计算机

27、，也不能在多项式时间内求解它们。3、什么是P类问题？什么是NP完全问题？答：1）P 类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。2）NP完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。4、列出几个典型的NP完全问题？答：（1）图着色问题COLORING（2）路径问题LONG-PATH （3）顶点覆盖问题VERTEX-COVER（4）子集和问题SUBSET-SUM（5）哈密尔顿回路问题HA

28、M-CYCLE（6）旅行商问题TSP（7）装箱问题BIN-PACKING，能否用 k 个箱子来装n 个物品；名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 30 页 -第九章近似算法1、所有 NP完全问题都还没有多项式时间的算法，然而许多 NP完全问题都具有很重要的意义，对于这类问题通常可以采取以下几种解题策略？答：）只对问题的特殊实例求解；）用动态规划或分支限界法求解。）启发式方法求解）只求近似解2、利用近似算法求解NP完全问题时，近似算法应该满足下面两个基本的要求？答：1）算法的时间复杂性：要求算法能在n 的多项式时间内完成。2）解的近似程度：算法的近似解应满足一定的精度。

29、通常，用来衡量精度的标准有近似比和相对误差。1、二分搜索算法是利用（A）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（A）。A、找出最优解的性质B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A）的一搜索方式。A、分支界限法B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（B）。A、分支界限法B、动态规划法C、贪心法D、回溯法名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 30 页 -5.回溯法解 TSP问题时的解空间树是（A）。A、子集树B、排列树C、深度优先生成树D、广度

30、优先生成树6下列算法中通常以自底向上的方式求解最优解的是（B）。A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C）。A 运行速度快 B 占用空间少 C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D）。A 棋盘覆盖问题 B 选择问题 C 归并排序D 0/1 背包问题 9.实现循环赛日程表利用的算法是（A）。A、分治策略B、动态规划法名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 30 页 -C、贪心法D、回溯法10、实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法11下面不是分支界限法搜索方式的是（D

31、）。A、广度优先B、最小耗费优先 C、最大效益优先D、深度优先12下列算法中通常以深度优先方式系统搜索问题解的是（D）。A、备忘录法B、动态规划法C、贪心法D、回溯法名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 30 页 -13.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A、重叠子问题B、最优子结构性质C、贪心选择性质 D、定义最优解14广度优先是（A）的一搜索方式。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15 背包问题的贪心算法所需的计算时间为（B）。A、O（n2）n B、O（nlogn）C、O（2）n D、O（n）16实现最大子段和利

32、用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 30 页 -17实现棋盘覆盖算法利用的算法是（A）。A、分治法B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是（C）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解19.回溯法的效率不依赖于下列哪些因素（D）A.满足显约束的值的个数 C.计算限界函数的时间B.计算约束函数的时间 D.确定解空间的时间20.下面哪种函数是回溯法中为避免无效搜索采取的策略（B）A递归函数B.剪枝函数C。随机数函数名师资料总结-精品资料欢迎下载-名师精心整理-

33、第 24 页，共 30 页 -D.搜索函数21、以深度优先方式系统搜索问题解的算法称为(D)。A、分支界限算法 B、概率算法 C、贪心算法D、回溯算 法22、贪心算法与动态规划算法的主要区别是（B）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解23.采用最大效益优先搜索方式的算法是（A）。A、分支界限法B、动态规划法C、贪心法D、回溯法24.（D）是贪心算法与动态规划算法的共同点。A、重叠子问题 B、构造最优解 C、贪心选择性质D、最优子结构性质25.矩阵连乘问题的算法可由（B）设计实现。名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 30 页 -A、分支界限算法

34、 B、动态规划算法C、贪心算法 D、回溯算法26.0-1背包问题的回溯算法所需的计算时间为（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）27、背包问题的贪心算法所需的计算时间为（B）A、O（n2）B、O（nlogn）C、O（2）D、O（n）29、使用分治法求解不需要满足的条件是（A）。A 子问题必须是一样的 B 子问题不能够重复C 子问题的解可以合并 D 原问题和子问题使用相同的方法解30、下面问题（B）不能使用贪心法解决。n n A 单源最短路径问题B N 皇后问题 C 最小花费生成树问题 D 背包问题31、下列算法中不能解决0/1 背包问题的是（A）A 贪心法 B 动

35、态规划 C 回溯法 D 分支限界法32、回溯法搜索状态空间树是按照（C）的顺序。名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 30 页 -A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历33、采用广度优先策略搜索的算法是（A）。A、分支界限法B、动态规划法C、贪心法D、回溯法34实现合并排序利用的算法是（A）。A、分治策略B、动态规划法C、贪心法D、回溯法35下列是动态规划算法基本要素的是（D）。A、定义最优解B、构造最优解 C、算出最优解 D、子问题重叠性质36下列算法中通常以自底向下的方式求解最优解的是（B）。A、分治法 B、动态规划法C、贪心法D、回溯

36、法名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 30 页 -二、填空题1.算法的复杂性有时间 复杂性 和 空间 复杂性之分。2、程序是算法用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令 是清晰的，无歧义的。4.矩阵连乘问题的算法可由动态规划设计实现。5、算法是指解决问题的一种方法或 一个过程。6、快速排序算法的性能取决于划分的对称性。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为回溯法。10、任何可用计算机求解的

37、问题所需的时间都与其规模 有关。11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。12、回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和 限界函数14、解决 0/1 背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 30 页 -15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和 0/1 背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1 背包问题，只使用约束条件进行裁剪的是

38、 N 皇后问题。17、回溯法是一种既带有系统性 又带有 跳跃性 的搜索算法。18.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质19.贪心算法的基本要素是贪心选择质和 最优子结构性质。21.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题 的解得到原问题的解。算法是由若干条指令组成的有穷序列，且要满足输入，输出、确定性和有限性 四条性质。23、快速排序算法是基于分治策略的一种排序算法。24、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。三、算法设计题1.背包问题的贪心算法，分支限界算法 2.最大子段和:动态规划算法 3.贪心算法求活动安排问题 5.快速排序6.多机调度问题-贪心算法四、简答题1 分治法的基本思想名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 30 页 -2.分治法与动态规划法的相同点 3.分治法与动态规划法的不同点 4.分支限界法与回溯法的相同点5分治法所能解决的问题一般具有的几个特征是：6.用分支限界法设计算法的步骤7.回溯法中常见的两类典型的解空间树是子集8.请简述符号 t(n)(g(n),t(n)(g(n),t(n)(g(n)的含义。9.分支限界法的搜索策略是：名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 30 页 -