算法设计与分析第一章习题解1.1,1.10,1.15
1.15练习
1.1（a）
1)A[1…60] =
A[(1+60)/2]=A[30]=40
由于33<40，舍弃A[30…60];
2)A[1…29] = A[(1+29)/2]=A[15]=25
由于33>25，舍弃A[1…15];
3) A[16…29]= A[(16+29)/2]=A[22]=32
由于33>32，舍弃A[16…22];
4) A[23…29] = A[(23+29)/2]=A[26]=36
由于33<36，舍弃A[26…29];
5) A[23…25] =
A[(23+25)/2]=A[24]=34; 由于33<34，舍弃A[24, 25];
6) A[23] = 11 12 13 … 68 69 70 11 12 13 … 37 38 39
26 27 28 … 37 38 39
33 34 35 36 37 38 39
33 34 35
33
由于33=33，搜索完毕。
综上，搜索33共执行了6次比较。
同理可得（b ）搜索7共执行了5次比较。
（c ）搜索70共执行了6次比较。
（d ）搜索77共执行了6次比较。
1.10 对11 12 1 5 15 3 4 10 7 2 16 9 8 14 13 6用bottomupsort 算法，按非降序排列。
解：用图示，如下进行。 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1
3 4 5 10 11 12 15
1 5 11 1
2 1.15用Θ表示函数。
(b)
2 6 7 8 9 1
3 1
4 16 3 4 10 1
5 2 7 9 1
6 6 8 13 14 11 12 1 5 15 3 4 10 2 7
9 16 8 14 6 13
（c）㏒2n+√n+㏒㏒n
(c)解：log2n+n+loglogn=?(log2n)
这是因为：考察lim
∞
→
n
(㏒2n+√n+㏒㏒n)/√n,用洛必达法则，分子分母同时求导，得
lim
∞
→
n
（2㏒n/n + n-1/2/2 + 1/n㏒n）/( n-1/2/2), 分子分母同时乘n,得lim
∞
→
n
（2㏒n + n1/2/2 + 1/㏒n）/( n1/2/2).再用洛必达法则，得
lim
∞
→
n
（2/n + n-1/2/4 - ㏒n-2/n）/( n-1/2/4),分子分母同时乘n,得lim
∞
→
n
（2 + n1/2/4 - ㏒n-2）/ n1/2/4.当n无限增大时㏒n-2/ n1/2/4=０,忽略不计,因此lim
∞
→
n
(2 + n1/2/4 - ㏒n-2)/ n1/2/4=1>0,
根据定义1.4可知, 原式=Θ(√n).
(d)
)
(
2/!n
n
n n
n
nΘ
=
+
《计算机算法设计与分析》习题及答案
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
中科院陈玉福计算机算法设计与分析期末简答题答案
1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。
算法设计与分析复习题目及答案19874
一。选择题 1、二分搜索算法就是利用( A )实现的算法。 Ａ、分治策略B、动态规划法C、贪心法 D、回溯法 2、下列不就是动态规划算法基本步骤的就是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 ３、最大效益优先就是( A )的一搜索方式。 Ａ、分支界限法Ｂ、动态规划法Ｃ、贪心法Ｄ、回溯法 4、在下列算法中有时找不到问题解的就是( B )。 Ａ、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5、回溯法解旅行售货员问题时的解空间树就是( B )。 A、子集树???Ｂ、排列树C、深度优先生成树?D、广度优先生成树 6.下列算法中通常以自底向上的方式求解最优解的就是( Ｂ)。 Ａ、备忘录法?B、动态规划法?C、贪心法????D、回溯法 7、衡量一个算法好坏的标准就是(C )。?A 运行速度快Ｂ占用空间少 C 时间复杂度低 D 代码短?８、以下不可以使用分治法求解的就是(D )。?Ａ棋盘覆盖问题Ｂ选择问题 C 归并排序 D 0/1背包问题?9、实现循环赛日程表利用的算法就是( A )。 A、分治策略?? B、动态规划法 C、贪心法??Ｄ、回溯法 10、下列随机算法中运行时有时候成功有时候失败的就是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11.下面不就是分支界限法搜索方式的就是( D )。 Ａ、广度优先?B、最小耗费优先C、最大效益优先D、深度优先 12、下列算法中通常以深度优先方式系统搜索问题解的就是( D )。 Ａ、备忘录法B、动态规划法??C、贪心法???D、回溯法
13、备忘录方法就是那种算法的变形。( B ) A、分治法? B、动态规划法? C、贪心法?? D、回溯法 1４、哈弗曼编码的贪心算法所需的计算时间为( B )。 A、Ｏ(n2n)?? B、O(nｌogｎ)? C、O(2ｎ) ??? D、Ｏ(n) 15.分支限界法解最大团问题时,活结点表的组织形式就是( B )。 A、最小堆???? B、最大堆?? C、栈???Ｄ、数组 １6.最长公共子序列算法利用的算法就是( B )。 A、分支界限法? B、动态规划法? C、贪心法 D、回溯法 17.实现棋盘覆盖算法利用的算法就是( A )。 Ａ、分治法??Ｂ、动态规划法C、贪心法??D、回溯法 18、下面就是贪心算法的基本要素的就是( C )。 A、重叠子问题?Ｂ、构造最优解??C、贪心选择性质??D、定义最优解 1９.回溯法的效率不依赖于下列哪些因素( D ) A、满足显约束的值的个数????Ｂ、计算约束函数的时间 C、计算限界函数的时间?? D、确定解空间的时间 ２０、下面哪种函数就是回溯法中为避免无效搜索采取的策略( B ) A.递归函数?B、剪枝函数? C。随机数函数???Ｄ、搜索函数 21、下面关于NＰ问题说法正确的就是(B )?A NＰ问题都就是不可能解决的问题?B P类问题包含在ＮＰ类问题中?C NP完全问题就是P类问题的子集 D ＮP类问题包含在P类问题中 22、蒙特卡罗算法就是( B )的一种。 Ａ、分支界限算法 B、概率算法C、贪心算法D、回溯算法 2３、下列哪一种算法不就是随机化算法( C ) A、蒙特卡罗算法 B、拉斯维加斯算法 C、动态规划算法 D、舍伍德算法 24、 ( D )就是贪心算法与动态规划算法的共同点。Ａ、重叠子问题B、构造最优解?C、贪心选择性质D、最优子结构性质２5、矩阵连乘问题的算法可由( B)设计实现。
算法设计与分析课后部分习题答案
算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中
for(i=0;i
算法设计与分析试卷(2010)
算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T
算法设计与分析考试题及答案
算法设计与分析考试题及 答案 It was last revised on January 2, 2021
一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算， 此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多 个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些 子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造 最优解； 2.流水作业调度问题的johnson算法的思想。 ①令N 1={i|a i =b i }；②将N 1 中作业按a i 的非减序排序得到N 1 ’，将N 2 中作业按b i 的非增序排序得到N 2’；③N 1 ’中作业接N 2 ’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i 和b i ，且 (a 1,a 2 ,a 3 ,a 4 )=(4,5,12,10)，(b 1 ,b 2 ,b 3 ,b 4 )=(8,2,15,9)求4个作业的最优调度方案，并计算最优 值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2 ’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0）
算法设计与分析习题
《算法设计与分析》习题 第一章算法引论 1、算法的定义 答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征 答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题
答：算法如下： （1） 递归法 汉诺塔问题 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); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n
计算机算法设计与分析期末考试复习题
1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。
OpenJudge算法设计与分析习题解答
1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。
源代码： #include
E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include
《算法设计与分析》复习题(汇编)
填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进
算法设计与分析课后习题
第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n ; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答：
计算机算法设计与分析习题及答案
计算机算法设计与分析习 题及答案 Prepared on 24 November 2020
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。
算法设计与分析期末试题答案解析
1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解；
健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一
《算法设计与分析实用教程》习题参考解答
《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include
算法设计与分析试卷及答案.doc
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。
算法设计与分析复习题目及答案doc
分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间）
分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法 ). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法 )之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树 ). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ）
算法设计与分析(期末总复习)
复习 一、简答题（每小题5分，选答2题，共10分） 1. 什么是算法试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。 4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。 二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52 算法 Mystery(n) 考虑下面的递归算法。P52 算法 Secret(A[0..n-1]) n-1] minval A[0]; maxval A[0] for i 1 to n-1 do if A[i] < minval minval A[i] if A[i] > maxval maxval A[i] return maxval – minval a.该算法求的是什么 b.它的基本操作是什么 c.该基本操作执行了多少次 d.该算法的效率类型是什么 3. 考虑下面的递归算法P59 算法 Q(n) 建立该函数值的递推关系并求解，以确定该算法计算的是什么； b. 建立该算法所做的乘法运算次数的递推关系并求解； c. 建立该算法所做的加减运算次数的递推关系并求解。
三、算法设计题（每小题10分，共20分） 1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调用树。(4章分治法)P102 2. 对于下面的有向图，应用基于DFS的算法来解拓扑排序问题。(5章减治法)P13 3.
3. 用自底向上算法为列表1, 8, 6, 5, 3, 7, 4进行堆排序。(6章变治法)P175 4. 应用Horspool算法在下面的文本中查找模式BARBER：BSS_KNER_BARBER (7章时空权衡)P201
算法设计与分析习题答案
算法设计与分析习题答案（第二版） 主编：吕国英 习题答案 习题答案 第三章： 1. #include
for(j=i;j>=0;j--) { buf[j]+=2; } } for(k=0;k<=n-2;k++) { if(buf[k]>=10) { buf[k+1]+=buf[k]/10; buf[k]%=10; } } for(i=n-1;i>=0;i--) printf("%d",buf[i]); printf("\n"); return 0; } 2. #include
int buf[6][6]; int i,j; printf("任意输入6个数字:"); for(i=0;i<6;i++) scanf("%d",&buf[0][i]); for(i=0;i<5;i++) { for(j=0;j<5;j++) { buf[i+1][j+1]=buf[i][j]; } buf[i+1][0]=buf[i][j]; } for(i=0;i<6;i++) { for(j=0;j<6;j++) printf("%d ",buf[i][j]); printf("\n"); } return 0; }
相关文档
- 算法设计与分析基础习题参考答案
- 计算机算法设计与分析习题及答案
- 算法设计与分析习题
- 算法设计与分析 习题2-5
- 算法设计与分析C++语言描述(陈慧南版)课后答案
- 计算机算法设计与分析期末考试复习题
- 算法设计与分析习题课
- 计算机算法设计与分析习题及答案
- 算法设计与分析课后习题
- 《算法设计与分析》复习题参考答案
- 算法设计与分析习题
- 算法设计与分析习题
- 算法设计与分析课后部分习题答案
- 计算机算法设计与分析》习题及答案
- 算法设计与分析习题答案
- 算法设计与分析-课后习题集答案
- 算法设计与分析+习题参考答案
- 计算机算法设计与分析习题和答案解析
- 计算机算法设计与分析习题及答案
- 算法设计与分析习题答案16章