中科院陈玉福计算机算法设计与分析期末简答题答案

《计算机算法设计与分析》试卷 考试时间120分钟2002年-2003年第二学期学号 姓名 成绩一、阐述题1． 请说明算法的五个基本特性，并进行简要的分析(5分) 答：算法的五个基本特性如下：① 确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。

② 能行性 一个算法是能行的是指算法中有待实现的运算都是基本的运算，每种运算至少在原理上能由人用纸和笔在有限时间内完成。

③ 输入 一个算法有0个或多个输人，这些输人是在算法开始之前给出的量，它取自特定的对象集合。

④ 输出 一个算法产生一个或多个输出，这些输出是同输人有某种特定关系的量。

⑤ 有穷性 一个算法总是在执行了有穷步的运算之后能够终止，且每一步都可在有穷时间内完成。

这里的有穷的概念不是纯数学的，而是在实际上是合理的，可以接受的。

凡是算法，都必须满足以上五条特性。

只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。

2． 若森林非空，请按照森林和树相互递归的定义，阐述森林的两种遍历的方法。

(10分) 答：森林是由m(m ≥0)棵互不相交的树构成的集合。

对树中的每一个结点而言，其子树的集合即为森林。

所以，森林和树是可以相互递归定义的。

对于一个非空的森林F=(T 1，T 2，…，T m )，因为至少存在一棵树，不妨假设为T 1，则森林F 可以分解成T 1和由T 2，…，T m 构成的森林。

于是，可得到森林的两种遍历算法。

① 先序遍历森林若森林非空，则可按下述规则遍历这个森林： （1） 访问树中第一棵树的根结点；（2） 先序遍历第一棵中根结点的所有子树构成的森林； （3） 先序遍历除去第一棵树外剩下的树构成的森林。

② 中序遍历森林若森林非空，则可按下述规则遍历这个森林：（1） 中序遍历第一棵中根结点的所有子树构成的森林； （2） 访问树中第一棵树的根结点；（3） 中序遍历除去第一棵树外剩下的树构成的森林。

中国科学院研究生院课程编号：711008Z－1试题专用纸课程名称：计算机算法设计与分析任课教师：陈玉福———————————————————————————————————————————————姓名学号成绩1.回答下列问题：(每小题5分)1.陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方法各自有什么实际意义最坏情况下的时间复杂度称最坏时间复杂度。

一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

2.阐述动态规划算法与贪心算法的区别，它们都有那些优势和劣势动态规划算法与贪心算法都要求问题具有最优子结构性质，这是二者的一个共同点。

但是对于具有最优子结构的问题应该选择前者还后者来解决下面通过两个经典的组合优化问题谈谈动态规划算法与贪心算法的主要差异3.动态规划法与分治法和贪心法类似，它也是将原问题分解为若干个更小的、相似的子问题，并通过求解子问题产生一个全局最优解。

与分治法和贪心法不同之处在于：①使用贪心法时，当前的选择可能要依赖于已经作出的所有选择，但不依赖于有待于做出的选择和子问题。

因此贪心法是自顶向下(即从起点到终点)，一步一步地作出贪心选择。

当然，如果当前的选择可能要依赖于子问题的解时，则难以通过局部的贪心策略达到全局最优解。

②使用分治法时，由原问题分解出的各子问题通常是相互独立的，即不包含公共的子问题，因此一旦递归地求出各子问题的解后，便可自下而上地将各子问题的解合并成问题的解。

如果各子问题不是相互独立的，则分治法要做许多不必要的工作，重复地求解公共的子问题。

③动态规划允许由原问题分解出的子问题之间相互依赖。

每一个子问题只求解一次，并将结果保存起来，避免每次碰到此子问题时都要重复计算4.阐述回溯算法与分枝限界算法的共同点和不同点，提高算法效率的关键是什么5.6. 在对算法进行复杂性分析时，强调渐进复杂性的意义是什么7. 算法的复杂性算法的复杂性算法的复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。

1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的最优解，而上一部之前的最优解则不作保留。

动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。

不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

但它需要计算之前所有情况花费，更加耗费空间。

贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编码和执行过程中都有一定的速度优势。

贪心算法是只是找局部最优解，不一定是全局最优解。

2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。

分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。

可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。

3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什么问题的什么特性提高效率的？一个最优化策略的子策略总是最优的。

一个问题满足最优化原理又称其具有最优子结构性质。

《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。

3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。

4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。

时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。

5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。

最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。

6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。

上述过程被反复递归调用。

7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。

目标函数：获得最大利润。

最优量度：最大利润/重量比。

8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。

科技学院二○ 年 学期期末考试信息与计算科学专业年级《算法设计与分析》 试题考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 一、填空题（每小题3 分，共计30 分）1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

()()log log f n n n g n n ==2. 算法的时间复杂性为1,1()8(3/7),2n f n f n n n =⎧=⎨+≥⎩，则算法的时间复杂性的阶为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。

8. ____________________________是问题能用动态规划算法求解的前提。

9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。

10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）1. 试述回溯法的基本思想及用回溯法解题的步骤。

题 号 一二三四五总分 统分人得 分 阅卷人复查人2. 有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。

1.一个算法就是一个有穷规矩的聚集,个中之规矩划定懂得决某一特别类型问题的一系列运算,此外,算法还应具有以下五个重要特点:_________,________,________,____ ______,__________.,权衡一个算法利害的尺度是______________________.3.某一问题可用动态计划算法求解的明显特点是____________________________________.4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列_____________________________.5.用回溯法解问题时,应明白界说问题的解空间,问题的解空间至少应包含___________.6.动态计划算法的根本思惟是将待求解问题分化成若干____________,先求解___________,然后从这些____________的解得到原问题的解.7.以深度优先方法体系搜刮问题解的算法称为_____________.8.0-1背包问题的回溯算法所需的盘算时光为_____________,用动态计划算法所需的盘算时光为____________.9.动态计划算法的两个根本要素是___________和___________.10.二分搜刮算法是应用_______________实现的算法.二.分解题（50分）1.写出设计动态计划算法的重要步调.2.流水功课调剂问题的johnson算法的思惟.3.若n=4,在机械M1和M2上加工功课i所需的时光分离为a i和b i,且(a1,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)求4个功课的最优调剂计划,并盘算最优值.4.应用回溯法解0/1背包问题：n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量构成,请求用一棵完整二叉树暗示其解空间（从根动身,左1右0）,并画出其解空间树,盘算其最优值及最优解.5.设S=｛X1,X2,···,X n｝是严厉递增的有序集,应用二叉树的结点来存储S中的元素,在暗示S的二叉搜刮树中搜刮一个元素X,返回的成果有两种情况,（1）在二叉搜刮树的内结点中找到X=X i,其概率为b i.（2）在二叉搜刮树的叶结点中肯定X∈（X i,X i+1）,其概率为a i.在暗示S的二叉搜刮树T中,设存储元素X i的结点深度为C i;叶结点（X i,X i+1）的结点深度为d i,则二叉搜刮树T的平均路长p为若干？假设二叉搜刮树T[i][j]=｛X i,X i+1,···,X j｝最优值为m[i][j],W[i][j]=a i-1+b i+···+b j+a j,则m[i][j](1<=i<=j<=n)递归关系表达式为什么？6.描写0-1背包问题.三.简答题（30分）1.流水功课调剂中,已知有n个功课,机械M1和M2上加工功课i 所需的时光分离为a i和b i,请写出流水功课调剂问题的johnson轨则中对a i和b i的排序算法.（函数名可写为sort(s,n)）2.最优二叉搜刮树问题的动态计划算法（设函数名binarysearchtree)）答案：一.填空1．肯定性有穷性可行性0个或多个输入一个或多个输出2.时光庞杂性空间庞杂性时光庞杂度高下具有最优子构造性质4.{BABCD}或{CABCD}或{CADCD｝5.一个（最优）解6.子问题子问题子问题7.回溯法8. o(n*2n) o(min{nc,2n})9.最优子构造重叠子问题10.动态计划法二.分解题1.①问题具有最优子构造性质;②构造最优值的递归关系表达式;③最优值的算法描写;④构造最优解;2.①令N1={i|a i<b i},N2={i|a i>=b i};②将N1中功课按a i的非减序排序得到N1’,将N2中功课按b i的非增序排序得到N2’;③N1’中功课接N2’中功课就构成了知足Johnson轨则的最优调剂.3.步调为：N1={1,3},N2={2,4};N 1’={1,3},N 2’={4,2}; 最优值为：384.解空间为{(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） 5.二叉树T 的平均路长P=∑=+n i 1Ci)(1*bi +∑=nj 0dj *aj{m[i][j]=0(i>j)6.已知一个背包的容量为C,有n 件物品,物品i 的重量为W i ,价值为V i ,求应若何选择装入背包中的物品,使得装入背包中物品的总价值最大. 三.简答题m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0)1.void sort(flowjope s[],int n){int i,k,j,l;for(i=1;i<=n-1;i++)//-----选择排序{k=i;while(k<=n&&s[k].tag!=0) k++;if(k>n) break;//-----没有a i,跳出else{for(j=k+1;j<=n;j++)if(s[j].tag==0)if(s[k].a>s[j].a) k=j;swap(s[i].index,s[k].index);swap(s[i].tag,s[k].tag); } }l=i;//-----记下当前第一个b i的下标for(i=l;i<=n-1;i++){k=i;for(j=k+1;j<=n;j++)if(s[k].b<s[j].b) k=j;swap(s[i].index,s[k].index); //-----只移动index和tag swap(s[i].tag,s[k].tag); }}2.void binarysearchtree(int a[],int b[],int n,int **m,int**s,int **w){int i,j,k,t,l;for(i=1;i<=n+1;i++){ w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)//----l是下标j-i的差for(i=1;i<=n-l;i++){j=i+l;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i;for(k=i+1;k<=j;k++){ t=m[i][k-1]+m[k+1][j]+w[i][j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}一、填空题（本题15分,每小题1分）1、算法就是一组有穷的,它们划定懂得决某一特定类型问题的 .2、在进行问题的盘算庞杂性剖析之前,起首必须树立求解问题所用的盘算模子.3个根本盘算模子是...3、算法的庞杂性是的器量,是评价算法好坏的重要根据.4、盘算机的资本最重要的是和资本.因而,算法的庞杂性有和之分.5、f(n)= 6×2n+n2,f(n)的渐进性态f(n)= O( )6、贪婪算法老是做出在当前看来的选择.也就是说贪婪算法其实不从整体最优斟酌,它所做出的选择只是在某种意义上的. 7、很多可以用贪婪算法求解的问题一般具有2个重要的性质：性质和性质.二.简答题（本题25分,每小题5分）1、简略描写分治法的根本思惟.2、简述动态计划办法所应用的最优化道理.3、何谓最优子构造性质？4、简略描写回溯法根本思惟.5、何谓P.NP.NPC问题三.算法填空（本题20分,每小题5分）1.n后问题回溯算法(1)用二维数组A[N][N]存储皇后地位,若第i行第j列放有皇后,则A[i][j]为非0值,不然值为0.(2)分离用一维数组M[N].L[2*N-1].R[2*N-1]暗示竖列.左斜线.右斜线是否放有棋子,有则值为1,不然值为0.for(j=0;j<N;j++)if( 1 ) /*安然检讨*/{ A[i][j]=i+1; /*放皇后*/2 ;if(i==N-1)输出成果;else 3 ;; /*试探下一行*/4 ; /*去皇后*/5 ;;}2.数塔问题.有形如下图所示的数塔,从顶部动身,在每一结点可以选择向左走或是向右走,一路走到底层,请求找出一条路径,使路径上的值最大.for(r=n-2;r>=0;r--) //自底向上递归盘算for(c=0; 1 ;c++)if( t[r+1][c]>t[r+1][c+1]) 2 ;else 3 ;3.Hanoi算法Hanoi(n,a,b,c)if （n==1） 1 ;else{ 2 ;3 ;Hanoi(n-1,b, a, c);}4.Dijkstra算法求单源最短路径d[u]:s到u的距离 p[u]:记载前一节点信息Init-single-source(G,s)for each vertex v∈V[G]do { d[v]=∞; 1 }d[s]=0Relax(u,v,w)if d[v]>d[u]+w(u,v)then { d[v]=d[u]+w[u,v];2}dijkstra(G,w,s)1. Init-single-source(G,s)2. S=Φ3.Q=V[G]4.while Q<> Φdo u=min(Q)S=S∪{u}for each vertex 3do4四.算法懂得题（本题10分）根据优先队列式分支限界法,求下图中从v1点到v9点的单源最短路径,请画出求得最优解的解空间树.请求中央被舍弃的结点用×标识表记标帜,获得中央解的结点用单圆圈○框起,最优解用双圆圈◎框起.五.算法懂得题（本题5分）设有n=2k个运发动要进行轮回赛,现设计一个知足以下请求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次;②每个选手一天至多只能赛一次;③轮回赛要在最短时光内完成.（1）假如n=2k,轮回赛起码须要进行几天;（2）当n=23=8时,请画出轮回赛日程表.六.算法设计题（本题15分）分离用贪婪算法.动态计划法.回溯法设计0-1背包问题.请求：解释所应用的算法计谋;写出算法实现的重要步调;剖析算法的时光.七.算法设计题（本题10分）经由过程键盘输入一个高精度的正整数n(n的有用位数≤240),去失落个中随意率性s个数字后,剩下的数字按原阁下次序将构成一个新的正整数.编程对给定的n 和s,查找一种计划,使得剩下的数字构成的新数最小.【样例输入】178543S=4【样例输出】13答案：一.填空题（本题15分,每小题1分）1．规矩一系列运算2. 随机存取机RAM(Random Access Machine);随机存取存储程序机RASP(Random Access Stored Program Machine);图灵机(Turing Machine)3. 算法效力4. 时光.空间.时光庞杂度. 空间庞杂度5．2n6．最好局部最优选择7. 贪婪选择最优子构造二.简答题（本题25分,每小题5分）6、分治法的根本思惟是将一个范围为n的问题分化为k个范围较小的子问题,这些子问题互相自力且与原问题雷同;对这k 个子问题分离求解.假如子问题的范围仍然不敷小,则再划分为k个子问题,如斯递归的进行下去,直到问题范围足够小,很轻易求出其解为止;将求出的小范围的问题的解归并为一个更大范围的问题的解,自底向上慢慢求出本来问题的解.7、“最优化道理”用数学化的说话来描写：假设为懂得决某一优化问题,须要依次作出n个决议计划D1,D2,…,Dn,如若这个决议计划序列是最优的,对于任何一个整数k,1 < k < n,不管前面k个决议计划是如何的,今后的最优决议计划只取决于由前面决议计划所肯定的当前状况,即今后的决议计划Dk+1,Dk+2,…,Dn也是最优的.8、某个问题的最优解包含着其子问题的最优解.这种性质称为最优子构造性质.9、回溯法的根本思惟是在一棵含有问题全体可能解的状况空间树长进行深度优先搜刮,解为叶子结点.搜刮进程中,每到达一个结点时,则断定该结点为根的子树是否含有问题的解,假如可以肯定该子树中不含有问题的解,则废弃对该子树的搜刮,退回到上层父结点,持续下一步深度优先搜刮进程.在回溯法中,其实不是先构造出整棵状况空间树,再进行搜刮,而是在搜刮进程,慢慢构造出状况空间树,即边搜刮,边构造.10、P(Polynomial问题)：也等于多项式庞杂程度的问题.NP就是Non-deterministic Polynomial的问题,也等于多项式庞杂程度的非肯定性问题.NPC(NP Complete)问题,这种问题只有把解域里面的所有可能都穷举了之后才干得出答案,如许的问题是NP里面最难的问题,这种问题就是NPC问题.三.算法填空（本题20分,每小题5分）1.n后问题回溯算法(1) !M[j]&&!L[i+j]&&!R[i-j+N](2) M[j]=L[i+j]=R[i-j+N]=1;(3) try(i+1,M,L,R,A)(4) A[i][j]=0(5) M[j]=L[i+j]=R[i-j+N]=02.数塔问题.（1）c<=r(2)t[r][c]+=t[r+1][c]（3）t[r][c]+=t[r+1][c+1]3.Hanoi算法（1）move(a,c)（2）Hanoi(n-1, a, c , b)（3）Move(a,c)4.（1）p[v]=NIL（2）p[v]=u(3) v∈adj[u]（4）Relax(u,v,w)四.算法懂得题（本题10分）五.（1）8天（2分）;（2）当n=23=8时,轮回赛日程表（3分）.六.算法设计题（本题15分）1 2 3 4 5 6 7 82 1 43 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 87 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1（1）贪婪算法 O（nlog（n））➢起首盘算每种物品单位重量的价值Vi/Wi,然后,依贪婪选择计谋,将尽可能多的单位重量价值最高的物品装入背包.若将这种物品全体装入背包后,背包内的物品总重量未超出C,则选择单位重量价值次高的物品并尽可能多地装入背包.依此计谋一向地进行下去,直到背包装满为止.➢具体算法可描写如下：void Knapsack(int n,float M,float v[],float w[],float x[]){Sort(n,v,w);int i;for (i=1;i<=n;i++) x[i]=0;float c=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)的递归式如下.void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c);for (j=0;j<=jMax;j++)/*m(n,j)=0 0=<j<w[n]*/m[n][j]=0;for (j=w[n];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/m[n][j]=v[n];for (i=n-1;i>1;i--){ int jMax=min(w[i]-1,c);for (j=0;j<=jMax;j++)/*m(i,j)=m(i+1,j) 0=<j<w[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：当前最优值void backtrack(int i)//回溯法i初值1{ if(i > n) //到达叶结点{ 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);}七.算法设计题（本题10分）为了尽可能地逼近目的,我们拔取的贪婪计谋为：每一步老是选择一个使剩下的数最小的数字删去,即按高位到低位的次序搜刮,若列位数字递增,则删除最后一个数字,不然删除第一个递减区间的首字符.然后回到串首,按上述规矩再删除下一个数字.反复以长进程s次,剩下的数字串等于问题的解了.具体算法如下：输入s, n;while（ s > 0 ）{ i=1; //从串首开端找while (i < length(n)) && (n[i]<n[i+1]){i++;}delete(n,i,1); //删除字符串n的第i个字符s--;}while (length(n)>1)&& (n[1]=‘0’)delete(n,1,1); //删去串首可能产生的无用零输出n;。

湖南科技学院二○ 年 学期期末考试信息与计算科学专业 年级《算法设计与分析》 试题考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 一、填空题（每小题3 分，共计30 分）1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

()()log log f n n n g n n ==2. 算法的时间复杂性为1,1()8(3/7),2n f n f n n n =⎧=⎨+≥⎩，则算法的时间复杂性的阶为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。

8. ____________________________是问题能用动态规划算法求解的前提。

9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。

10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）1. 试述回溯法的基本思想及用回溯法解题的步骤。

2. 有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。

湖南科技学院二○ 年 学期期末考试信息与计算科学专业 年级《算法设计与分析》 试题考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟一、填空题（每小题3 分，共计30 分）1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

2. 算法的时间复杂性为1,1()8(3/7),2n f n f n n n =⎧=⎨+≥⎩，则算法的时间复杂性的阶为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。

8. ____________________________是问题能用动态规划算法求解的前提。

9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。

10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）1. 试述回溯法的基本思想及用回溯法解题的步骤。

2. 有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。

不存在二义性。

只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

湖南科技学院二○年学期期末考试信息与计算科学专业年级《算法设计与分析》试题考试类型：开卷试卷类型：C卷考试时量：120分钟。

9.贪心选择性质是指____________________________________________________________________________________________________________________。

10.回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）1.试述回溯法的基本思想及用回溯法解题的步骤。

2.有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2后一个作业在机器M2上加工完成所需的时间最少，并计算所需的最少时间。

}template<typenameType>voidPerm(TypeR[],intk,intn,int&sum){//n为元素个数，sum记录不同排列的总数if(k==n){______________________;//3for(inti=1;i<=n;i++)cout<<___________________;//4cout<<endl;}else{for(inti=k;i<=n;i++)if(ok(R,k,i)){Swap(R[k],R[i]);Perm(_________________________);//5Swap(R[k],R[i]);}}}《算法设计与分析》试题C答案一、填空题（每小题3分，共计30分）1.f(n)=Ω(g(n))2.73log8n 3.划分的对称性4.由若干条指令组成组成的有穷序列（解决问题的一种方法或一个过程）5.分枝限界法6.最坏7.高8.最优子结构9.所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

《算法设计与分析》试卷及答案算法设计与分析考试复习试卷《算法设计与分析》试卷1一、多项选择题（每空2分，共20分）：1、以下关于算法设计问题的叙述中正确的是__________。

A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关B、利用计算机无法解决非数值问题C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题2、算法的特征包括_________。

A、有穷性B、确定性C、输入和输出D、能行性或可行性3、以下描述是有关算法设计的基本步骤：①问题的陈述②算法分析③模型的拟制④算法的实现⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起其中正确的顺序是__________。

A、①②③④⑤⑥B、①③⑤②④⑥C、②④①③⑤⑥D、⑥①③⑤②④4、以下说法正确的是__________。

A、数学归纳法可以证明算法终止性B、良序原则是证明算法的正确性的有力工具C、x = 小于或等于x的最大整数（x的低限）D、x = 小于或等于x的最大整数（x的高限）5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C 上所用的次数，则递归方程为__________，其初始条件为__________，将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数，则有递归方程为__________，其中F1=F2=__________。

A、Fn=Fn-1+Fn-2B、h（n）= 2h（n-1）+1C、1D、h（1）= 1E、h（n）=2n-1F、06、在一个有向连通图中（如下图所示），找出点A到点B的一条最短路为____ ______。

A、最短路：1→3→5→8→10，耗费：20B、最短路：1→4→6→9→10，耗费：16。

算法大题期末考试题及答案一、简答题（每题5分，共20分）1. 简述什么是递归算法，并给出一个递归算法的实例。

答案：递归算法是一种在算法中使用函数调用自身的方法来解决问题的算法。

例如，计算阶乘的递归算法定义为：n! = n * (n-1)!，其中n是一个正整数，递归的基本情况是1! = 1。

2. 描述二分查找算法的基本思想，并说明其时间复杂度。

答案：二分查找算法是一种在有序数组中查找特定元素的算法。

其基本思想是将数组分为两半，比较中间元素与目标值，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

这个过程重复进行，直到找到目标值或查找范围为空。

二分查找的时间复杂度为O(log n)。

3. 什么是动态规划？动态规划与贪心算法的区别是什么？答案：动态规划是一种通过将复杂问题分解为更小的子问题来解决的方法，并且通过存储这些子问题的解来避免重复计算。

动态规划与贪心算法的区别在于，贪心算法在每一步选择局部最优解，而动态规划则考虑所有可能的子问题解，并选择全局最优解。

4. 解释什么是哈希表，并简述其工作原理。

答案：哈希表是一种数据结构，它提供了快速的数据插入和查找功能。

哈希表通过哈希函数将键映射到表中的一个位置来访问记录，这个通过键到位置的映射过程称为哈希。

如果两个键具有相同的哈希值，这种情况称为冲突，通常通过链地址法或开放地址法来解决。

二、计算题（每题10分，共20分）1. 给定一个数组A=[3, 5, 7, 9, 11]，请使用二分查找算法找出11的位置。

答案：首先，确定数组的中间位置，即(0+4)/2=2，比较A[2]与11，发现A[2]=7小于11，因此11在A[2]的右侧。

更新查找范围为A[3]到A[4]，即索引3和4。

继续比较A[3]与11，发现A[3]=9小于11，因此11在A[3]的右侧。

最后，比较A[4]与11，发现A[4]=11等于目标值，所以11的位置是4。

《计算机算法设计与分析》习题及答案一．选择题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。

《算法设计与分析》考试题⽬及答案解析《算法分析与设计》期末复习题⼀、选择题1.应⽤Johnson法则的流⽔作业调度采⽤的算法是（D）A. 贪⼼算法B. 分⽀限界法C.分治法D. 动态规划算法2.Hanoi塔问题如下图所⽰。

现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。

移动圆盘时遵守Hanoi塔问题的移动规则。

由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔3. 动态规划算法的基本要素为（C）A. 最优⼦结构性质与贪⼼选择性质B．重叠⼦问题性质与贪⼼选择性质C．最优⼦结构性质与重叠⼦问题性质D. 预排序与递归调⽤4. 算法分析中，记号O表⽰（B），记号Ω表⽰（A），记号Θ表⽰（D）。

A.渐进下界B.渐进上界C.⾮紧上界D.紧渐进界E.⾮紧下界5. 以下关于渐进记号的性质是正确的有：（A）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ?=ΘB. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==?=C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})D. f(n)O(g(n))g(n)O(f(n))=?=6.能采⽤贪⼼算法求最优解的问题，⼀般具有的重要性质为：（A）A. 最优⼦结构性质与贪⼼选择性质B．重叠⼦问题性质与贪⼼选择性质C．最优⼦结构性质与重叠⼦问题性质D. 预排序与递归调⽤7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。

A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分⽀限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。

A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。

A.B.C.D.10. 回溯法的效率不依赖于以下哪⼀个因素？（C ）A.产⽣x[k]的时间；B.满⾜显约束的x[k]值的个数；C.问题的解空间的形式；D.计算上界函数bound的时间；E.满⾜约束函数和上界函数约束的所有x[k]的个数。