算法分析与设计期末模拟试题

《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？2.算法分析的目的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述二分检索（折半查找）算法的基本过程。

7.背包问题的目标函数和贪心算法最优化量度相同吗？8.采用回溯法求解的问题，其解如何表示？有什么规定？9.回溯法的搜索特点是什么？10.n皇后问题回溯算法的判别函数place的基本流程是什么？11.为什么用分治法设计的算法一般有递归调用？12.为什么要分析最坏情况下的算法时间复杂性？13.简述渐进时间复杂性上界的定义。

14.二分检索算法最多的比较次数？15.快速排序算法最坏情况下需要多少次比较运算？16.贪心算法的基本思想？17.回溯法的解（x1,x2,……x n）的隐约束一般指什么？18.阐述归并排序的分治思路。

19.快速排序的基本思想是什么。

20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21.什么是哈密顿环问题？22.用回溯法求解哈密顿环，如何定义判定函数？23.请写出prim算法的基本思想。

二、复杂性分析1、MERGESORT(low，high)if low<high；then mid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifend MERGESORT2、procedure S1(P，W，M，X，n)i←1; a←0while i≤ n doif W(i)>M then return endifa←a+ii←i+1 ;repeatend3.procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)v←A(m);i←mlooploop i←i+1 until A(i) ≥v repeatloop p←p-1 until A(p) ≤v repeatif i<pthen call INTERCHANGE(A(i),A(p))else exitendifrepeatA(m) ←A(p);A(p) ←vEnd PARTITION4.procedure F1(n)if n<2 then return(1)else return(F2(2,n,1,1))endifend F1procedure F2(i,n,x,y)if i≤nthen call F2(i+1,n,y,x+y)endifreturn(y)end F25.procedure MAX(A,n,j)xmax←A(1);j←1for i←2 to n doif A(i)>xmax then xmax←A(i); j←i;endif repeatend MAX6.procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low←1;high←nwhile low≤high domid←|_(low+high)/2_|case:x<A(mid):high←mid-1:x>A(mid):low←mid+1:else:j ←mid; returnendcase repeat j ←0 end BINSRCH三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。

一、填空题(选做5道，10分)1． 用矩阵幂的方法求斐波那契数，其运行时间为（）.2． 对于一个可以用动态规划法求解的问题，要求问题既要满足（）的特性，又要具有大量的（ ）.3． 对于一个可以用贪心法求解的问题，不仅要求问题满足（）的特性，还应证明其贪心策略的（ ）.4． 设有n 个栈操作（PUSH 、POP 、MULTIPOP ）的序列，作用于初始为空的栈S .不区分三种操作，则每个操作的最坏运行时间为（），平摊运行时间为（）. 5． 三种平摊分析的方法分别为（）、（）、（）.6． 四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（）树；巡回售货员问题的搜索空间为（）树.7． （）法的求解目标是找出解空间树中满足约束条件的所有解，而（）法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解. 8． 回溯法一般以（）优先的方式搜索解空间树，而分支限界法则一般以（）优先或以最小耗费优先的方式搜索解空间树. 二、单项选择题 (10分)1． 下列关于排序算法的叙述，不正确的是？（）A) 堆排序的最差情形运行时间为Θ(n lg n )B) 快速排序平均情形运行时间为Θ(n lg n ) C) 任何排序算法的最差情形运行时间都不可能比Ω(n lg n )更小D) 插入排序在最好情形下的运行时间为Θ(n )2． 对于课堂讲解的线性时间内找第i 小的元素的算法，（）下列叙述中不正确的是？A) 算法第一步中可以按每五个元素一组找中位数；B) 算法第一步中可以按每七个元素一组找中位数；B) 算法第一步中不能按每三个元素一组找中位数；D) 如果要求的n 个元素的中位数，则中位数一定是第一步中找到的中位数中的某一个.3． 主方法可以求解满足形如下式的递推方程，（）则下列关于方程中的约束中不准确的是？A) 对于系数a ，装订线内不要必须满足a≥ 1B) 对于系数b，必须满足b > 1C) 若对于常数ε>0，f(n)=O(n log b a-ε)，则T(n)=Θ(n log b a)D) 若f(n)=O(n log b a)，则T(n)=Θ(n log b a log n)4．下列哪些问题不能用贪心法求解？（）A) 霍夫曼编码问题B) 单源最短路径问题C) 0-1背包问题D) 最小生成树问题可合并堆上可以不包含下列哪个操作？（）A) DECREASE-KEY(H, x, k) B) UNION(H1, H2)C) INSERT(H, x) D) EXTRACT-MIN(H)5．不同堆上插入操作最差情形下的开销或平摊开销，（）对二叉堆、二项堆和斐波那契堆，下列选项中描述错误的是？A) 二叉堆为Θ(lg n) B) 二项堆为O(lg n)C) 斐波那契堆为Θ(1)D) 三种堆的开销都是Θ(lg n)6．关于网络流的割，下列选项中错误的是？（）割(S,T)是流网络G=(V,E)的一个划分，其中s∈S, t∈T.如果f 是G上的流，那么流经割的净流量为f(S,T)，割(S,T)上的容量定义为c(S,T) .A) | f| ≤ c(S, T) B) f(S, T) = |f|C) f(s, V-s) = | f | D) f(S-s, V) = | f |7．下列随机算法一定有解但解不一定正确的是？（）A) SherwoodB) LasVegas C) MonteCarloD) 三者都不是8．在快速排序算法中引入随机过程的主要目的是什么？（）A) 改善确定性算法的平均运行时间B) 保证算法总能在O(n lg n)时间内结束C) 避免了算法最坏情况下的发生D) 改善了确定性算法最坏情形下的平均运行时间9．用Monte Carlo方法估计四后问题回溯算法的效率.（）五次实验结果分别为<1,4,2>、<2,4,1,3>、<4,2>、<3,1,4,2>、<1,3>，则解空间中的结点数估计为？A) 16 B) 16.2 C) 17 D) 16.5三、社会名流(20分) Array在n个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流.现在的问题是如果存在，试找出该社会名流.你可以使用的唯一方式是询问：“请问你知道那个人吗？”请给出提问次数为O(n)的算法，写出伪代码，分析算法的正确性，并给出算法运行时间的精确分析（即O(n)中隐藏的系数）.（提示：当你问A是否认识B时，如果A认识B，则A不是社会名流；如果A不认识B，则B不是社会名流）四、地板覆盖（20分）用2*1的地板块覆盖3*n 的地面有多少种方案？如下图是一个覆盖的例子，函数fn 可用于求解这个问题，请说明fn 算法的正确性，并说明算法运行时间的上界和下界.int fn(int n) { if (n % 2 == 1) return 0。

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

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

不存在二义性。

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

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

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

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

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

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

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

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

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

二、建立迭代关系式。

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

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

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

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

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

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

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. 回溯法解旅行售货员问题时的解空间树是（ 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、下列随机算法中运行时有时候成功有时候失败的是（C )A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）.A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。

（ B )A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B )。

A、O（n2n)B、O（nlogn)C、O(2n）D、O(n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）.A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）.A、分治法B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是（ C ）。

大学期末考试试卷B 卷（算法设计与分析）一、选择题（30分，每题2分）1、下面的算法段针对不同的自然数n 作不同的处理，其中函数odd (n) 当n 是奇数时返回true ，否则返回false ，while ( n > 1) if ( odd (n) ) n = 3 * n + 1;else n = n / 2;请问该算法所需计算时间的下界是 。

A ．Ω（2n ） B ．Ω（nlog n ） C ．Ω（n ！） D ．Ω（logn ）2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足 位客户的需求。

P104 A ．3 B ．4 C ．5 D ．63、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用 来消除或减少问题的好坏实例间的这种差别。

A ．数值概率算法 B ．舍伍德算法 C ．拉斯维加斯算法 D ．蒙特卡罗算法4、将一个正整数n 表示成一系列正整数之和， n = n 1 + n 2 + … +n k （其中，n 1≥n 2≥ … ≥n k ≥1，k ≥1）正整数n 的一个这种表示称为正整数n 的一个划分。

正整数n 的不同的划分个数总和称为正整数n 的划分数，记作p （n ）；另外，在正整数n 的所有不同划分中，将最大加数n1不大于m 的划分个数记作q （n ，m ）。

则当n=10时，p （n ）= 。

A ．q （8，8） B ．1 + q （9，9） P12 C ．2 + q （10，8） D ．A ，B ，C 都正确5、对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。

A ．n!B ．2nC ．2n+1-1D ．∑=ni i n 1!/! P1406、在棋盘覆盖问题中，对于2k ×2k 的特殊棋盘（有一个特殊方块），所需的L 型骨牌的个数是 A 。

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．重叠子问题性质与贪心选择性质
3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最 优的选择，即贪心选择来达到）。
4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。 5. 回溯法是指（具有限界函数的深度优先生成法）。 6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任 何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中 从根结点到叶结点的最长路径的长度为 h(n)，则回溯法所需的计算空间通 常为（O(h(n))）。 7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与
12. 用回溯法解图} 的 m 着色问题时，使用下面的函数 OK 检查当前扩展结点的
每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn））。
Bool Color::OK(int k) {//
for(int j=1;j<=n;j++) if((a[k][j]= =1)&&(x[j]= =x[k])) return false;
f(n)个单位时间。用 T(n)表示该分治法解规模为|P|=n 的问题所需的计算时
间，则有：T (n)

kT (n
O(1) / m)
f
(n)
n 1 n 1

A卷一、选择题1.二分搜索算法是利用（A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2. 回溯法解旅行售货员问题时的解空间树是（ A ）。

A、子集树B、排列树C、深度优先生成树D、广度优先生成树3.下列算法中通常以自底向上的方式求解最优解的是（B ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法4．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）6．分支限界法解最大团问题时，活结点表的组织形式是（ B）。

A、最小堆B、最大堆C、栈D、数组7、下面问题（B ）不能使用贪心法解决。

A 单源最短路径问题B N皇后问题C 最小花费生成树问题D 背包问题8.下列算法中不能解决0/1背包问题的是（A ）A 贪心法B 动态规划C 回溯法D 分支限界法9.背包问题的贪心算法所需的计算时间为（ B ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）10.背包问题的贪心算法所需的计算时间为（B ）。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）二、填空题1.算法的复杂性有复杂性和复杂性之分。

2.算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。

其中算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。

3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。

4.动态规划算法的两个基本要素是. 性质和性质。

5.回溯法是一种既带有又带有的搜索算法；分支限界法是一种既带有又带有的搜索算法。

6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。

在任何时刻，算法只保存从根结点到当前扩展结点的路径。

算法设计与分析期末复习题【试题.知识点】算法设计与分析期末考试复习题1．算法有哪些特点？为什么说⼀个具备了所有特征的算法，不⼀定就是使⽤的算法?2．证明下⾯的关系成⽴：(参考例题1.5--1.6)（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)(3)n!=Θ(n n) (4)5n2-6n=Θ(n2)13.考虑下⾯的算法：输⼊：n个元素的数组A输出：按递增顺序排序的数组A1. void sort(int A[],int n)2. {3. int i,j,temp;4. for(i=0;i5. for(j=i+1;j6. if(A[j]7. temp=A[i];8. A[i]=A[j];9. A[j]=temp;10. }11. }（1）什么时候算法所执⾏的元素赋值的次数最少？最少多少次？（2）什么时候算法所执⾏的元素赋值的次数最多？最多多少次？4.考虑下⾯的算法：输⼊：n个元素的数组A输出：按递增顺序排序的数组A1. void bubblesort(int A[],int n)2. {3. int j,i,sorted;4. i=sorted=0;5. while(i6. sorted=1;7. for(j=n-1;j>i;j--) {8. if(A[j]9. temp=A[j];210. A[j]=A[j-1];11. A[j-1]=temp;12. sorted=0;13. }14. }15. i=i+1;16. }17. }（1）算法所执⾏的元素⽐较次数最少是多少次？什么时候达到最少？（2）算法所执⾏的元素⽐较次数最多是多少次？什么时候达到最多？（3）算法所执⾏的元素赋值次数最少是多少次？什么时候达到最少？（4）算法所执⾏的元素赋值次数最多是多少次？什么时候达到最多？（5）⽤О、和Ω记号表⽰算法的运⾏时间。

（6）可以⽤Θ记号来表⽰算法的运⾏时间吗？请说明。

35.解下⾯的递归⽅程：（1）f(n)=5f(n-1)-6f(n-2) f(0)=1 f(1)=0（2）f(n)=4f(n-1)-4f(n-2) f(0)=6 f(1)=86.初始链表的内容为：3562，6381，0356，2850，9136，3715，8329，7481，写出⽤基数排序算法对它们进⾏排序的过程。

算法设计与分析期末考试复习题1．算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?2．证明下面的关系成立：(参考例题1.5--1.6)（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)(3)n!=Θ(n n) (4)5n2-6n=Θ(n2)3.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1. void sort(int A[],int n)2. {3. int i,j,temp;4. for(i=0;i<n-1;i++)5. for(j=i+1;j<n;j++)6. if(A[j]<A[i]) {7. temp=A[i];8. A[i]=A[j];9. A[j]=temp;10. }11. }（1）什么时候算法所执行的元素赋值的次数最少？最少多少次？（2）什么时候算法所执行的元素赋值的次数最多？最多多少次？4.考虑下面的算法：输入：n个元素的数组A输出：按递增顺序排序的数组A1. void bubblesort(int A[],int n)2. {3. int j,i,sorted;4. i=sorted=0;5. while(i<n-1 && !sorted) {6. sorted=1;7. for(j=n-1;j>i;j--) {8. if(A[j]<A[j-1]) {9. temp=A[j];10. A[j]=A[j-1];11. A[j-1]=temp;12. sorted=0;13. }14. }15. i=i+1;16. }17. }（1）算法所执行的元素比较次数最少是多少次？什么时候达到最少？（2）算法所执行的元素比较次数最多是多少次？什么时候达到最多？（3）算法所执行的元素赋值次数最少是多少次？什么时候达到最少？（4）算法所执行的元素赋值次数最多是多少次？什么时候达到最多？（5）用О、和Ω记号表示算法的运行时间。

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

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

不存在二义性。

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

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

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

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

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

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

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

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

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

二、建立迭代关系式。

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

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

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

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

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

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

算法分析与设计期末考试模拟试题一课程名称：__ 算法分析与设计 考试形式： 闭 卷学习中心：_________ 考试时间： 90分钟姓 名：_____________ 学 号：一、填空题（每小题4分，共计40分）1. 通常只考虑三种情况下的时间复杂度，即 情况、情况和 情况下的时间复杂度，分别记为T max (N)、T min(N) 和T avg (N)，实践表明可操作性最好且最有实际价值的是 情况下的时间复杂度。

2. n n 1032 的渐近表达式是 ，)log(3n 的渐近表达式是 。

3. 根据符号O 的定义易知O(1)=O(2)，用O(1)和O(2)表示同一个方法时，差别仅在于其中的 。

4. 递归算法是指 的算法，递归函数是指 的函数。

5. 贪心算法总是做出在当前看来_____________的选择，也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的________________。

6. 如果某问题具有________________________和___________________________两个重要性质，该问题可以用贪心算法求解。

7. 单源最短路径问题适合用_______________算法来求解、0-1背包问题适合用_____________算法来求解。

8. 分治法是将一个规模为n的问题分解为k个规模________的子问题，这些子问题___________且与原问题__________。

递归地求解这些子问题，然后将各个子问题的解_________得到原问题的解。

9. 动态规划算法的两个基本要素是____________________和____________________。

10.___ 算法可以有效地解凸多边形最优三角剖分问题，而____________算法是求解最优装载问题的有效方法。

二、简答题（每小题10分，共计40分）1. 如果只需要求解问题的最优值，动态规划算法步骤是什么？如果需要构造最优解，则还需要加上什么步骤？2. 请简述什么是贪心选择性质3. 请简述什么是最小生成树。

《算法分析与设计》期末复习题一、选择题1。

应用Johnson 法则的流水作业调度采用的算法是（D )A. 贪心算法 B 。

分支限界法 C.分治法 D 。

动态规划算法2。

Hanoi 塔问题如下图所示。

现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置.移动圆盘时遵守Hanoi 塔问题的移动规则。

由此设计出解Hanoi 塔问题的递归算法正确的为：（B ）Hanoi 塔A. void hanoi(int n, int A, int C, int B) { if (n > 0) {hanoi(n-1,A,C, B); move(n,a,b);hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) {if (n > 0) {hanoi(n-1, A, C, B); move(n,a,b);hanoi(n-1, C, B, A); }C. void hanoi(int n, int C, int B, int A) {if (n > 0) {hanoi(n-1, A, C, B); move(n,a,b);hanoi(n-1, C, B, A); }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。

1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：确定性：可行性：输入：输出：算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

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

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

复杂性的渐近性态设T(N)是算法A的复杂性函数，使得当N→∞时有：(T(N)-T’(N))/T(N) → 0那么，我们就说T’(N)是T(N)当N→∞时的渐近性态，或叫T’(N)为算法A当N→∞的渐近复杂性而与T(N)相区别。

P = NP经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法分而治之法1、基本思想将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

3、分治法的基本步骤（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。

递归：直接或间接的调用自身的算法，叫做递归算法。

考生 信 息 栏 ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿ 装 订 线考 生信 息 栏 ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿ 装 订 线 pro2(n) ex1(n/2) end if return end ex1 3．用Floyd 算法求下图每一对顶点之间的最短路径长度，计算矩阵D 0，D 1，D 2和D 3，其中D k [i, j]表示从顶点i 到顶点j 的不经过编号大于k 的顶点的最短路径长度。

三．算法填空题（共34分） 1．（10分）设n 个不同的整数按升序存于数组A[1..n]中，求使得A[i]=i 的下标i 。

下面是求解该问题的分治算法。

算法 SEARCH 输入：正整数n ，存储n 个按升序排列的不同整数的数组A[1..n]。

输出：A[1..n]中使得A[i]=i 的一个下标i ，若不存在，则输出 no solution 。

i=find ( (1) ) if i>0 then output i else output “no solution” end SEARCH 过程 find (low, high) // 求A[low..high] 中使得A[i]=i 的一个下标并返回，若不存在，考生 信息 栏 ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿ 装订线《算法设计与分析》期考试卷(A)标准答案 一. 填空题：1. 元运算 考生 信 息 栏 ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级姓名＿＿＿＿＿＿ 学号＿＿＿＿＿ 装订线2. O3.∑∈n D I I t I p )()(4. 将规模为n 的问题分解为子问题以及组合相应的子问题的解所需的时间5. 分解，递归，组合6. 在问题的状态空间树上作带剪枝的DFS 搜索（或：DFS+剪枝）7. 前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的8. 局部9. 高10. 归并排序算法11. 不同12. v=random (low, high); 交换A[low]和A[v]的值随机选主元13. 比较n二. 计算题和简答题：1. 阶的关系：(1) f(n)= O(g(n))(2) f(n)=Ω(g(n))(3) f(n)=Ω(g(n))(4) f(n)= O(g(n))(5) f(n)=Θ(g(n))阶最低的函数是：100阶最高的函数是：n 32. 该递归算法的时间复杂性T(n)满足下列递归方程：⎩⎨⎧>+===1n ,n log T(n/2)T(n)1n , 1T(n)2 将n=k2, a=1, c=2, g(n)=n log 2, d=1代入该类递归方程解的一般形式得： T(n)=1+∑-=1k 0i i 22n log =1+k n log 2-∑-=1k 0i i =1+ k n log 2-2)1k (k -=n log 2122+n log 212+1 所以，T(n)= n log 2122+n log 212+1=)(log 2n Θ。

《算法分析与设计》期末复习题一、选择题1.应用Johnson 法则的流水作业调度采用的算法是（D ）A. 贪心算法B. 分支限界法C.分治法D. 动态规划算法2.Hanoi 塔问题如下图所示。

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

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

由此设计出解Hanoi 塔问题的递归算法正确的为：（B ）Hanoi 塔A. void hanoi(int n, int A, int C, int B) { if (n > 0) {hanoi(n-1,A,C, B); move(n,a,b);hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) {if (n > 0) {hanoi(n-1, A, C, B); move(n,a,b);hanoi(n-1, C, B, A); }C. void hanoi(int n, int C, int B, int A) {if (n > 0) {hanoi(n-1, A, C, B); move(n,a,b);hanoi(n-1, C, B, A); }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）策略，从根结点出发搜索解空间树。

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∈Dn
二、复杂性分析 1、 MERGESORT(low，high) if low<high； then mid←(low，high)/2； MERGESORT(low，mid)； MERGESORT(mid+1，high)； MERGE(low，mid，high)； endif end MERGESORT
17. 回溯法的解（x1,x2,……xn）的隐约束一般指什么？ 17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。
18. 阐述归并排序的分治思路。 18. 讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一
个含 n 个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。
《算法分析与设计》期末试题及参考答案
一、简要回答下列问题 ： 1. 算法重要特性是什么？ 1. 确定性、可行性、输入、输出、有穷性 2. 2. 算法分析的目的是什么？ 2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3. 算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小 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）。

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）。

A、O（n2）nB、O（nlogn）C、O（2）nD、O（n）16．实现最大子段和利用的算法是（B）。

A、分治策略B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（A）。

A、分治法B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是（C）。