北航六系大二算法设计与分析2007期末试题

2006-2007学年度第一学期计算机科学系《算法设计与分析》期末试卷（A）一对于下列各组函数，确定f(n)=O(g(n))是否成立。

(每题5分,共20分)1f(n)=3n,g(n)=nf(n)=O(g(n))成立，因为存在正的常数C和自然数n，使得N>=n时，有F（n）<=Cg(n)2f(n)=nlogn+n,g(n)=logn不成立！N>=n时，有f(n)>=og(n);属于f(n)=πg(n)这种情况3f(n)=log2n,g(n)=logn不成立！当logN>=1时，总有f(n)>=log n,属于f(n)=πg(n)这种情况！4f(n)=5,g(n)=log5成立！总存在一个正的常数C，使得f(n)<=Cg(n)1二分搜索法 int bin_seach ( int k[ ] , int n , int key ) { int low = 0 , high = n=1 , mid ; while ( low <= high ) { mid = ( low + high ) / 2 ; if ( key == k[ mid ] ) return mid ; if ( key > k[ mid ] ) low = mid + 1 ; else high = mid - 1 ; } return -1 ;} T(n)=n 2利用一维一级指针数组及二级指针输出二维数组元素。

#include "stdio.h" void main() { int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}}; int *arr[3]={a[0],a[1],a[2]}; int i,j,**p; p=arr; for(i=0;i<3;i++){for(j=0;j<4;j++)printf("%3d",a[i][j]));printf("%3d",*(&p[0][0]+i*4+j));printf("%3d",*(p[i]+j));printf("%3d",(*(p+i))[j]);printf("%3d",*(*(p+i)+j));printf("\n");}printf("\n");三 写出下列算法的时间复杂度函数.(每题5分,共10分)————————————装————————————————订}T(n)=12四根据给定的算法求出下列问题的解。

2006-2007学年第二学期期末考试试题数学分析一、 填空题 （每小题6分，共30分）1． 设向量场),,(222222y x x z z y F +++=，则_,____________________=F div ._______________________________=F rot ２．在曲面0:2=−Σ−z x e y 上点)2,1,1(处的法线方程是.________________________３．设}0,1|),{(22≥=+=y y x y x L ，则.___________2=∫L ds x４．锥面22y x z +=被圆柱面x y x 222=+截下的曲面的面积为._______________ ５．求极限._____________)1(lim 2200222=+∫∫→xx t x t x dt e x dt e二、 （本题满分１０分）计算定积分∫−=10ln 1dx x x I ．三、 （本题满分１０分）计算∫∫∫V z dxdydz e ||，其中1:222≤++z y x V ． 四、 （本题满分１０分）设函数)(x f 在),(+∞−∞内具有一阶连续导数，L 是上半平面)0(>y 内的有向分段光滑曲线，其起点为),(b a ，终点为),(d c ．记∫−++=L dy xy f y y x dx xy f y y I ]1)([)](1[1222，（１） 证明曲线积分I 与路径L 无关；（２） 当cd ab =时，求I 的值．（３）五、 （本题满分１０分）求解微分方程0)sin ()(22=+−−dy y x dx y x ．六、 （本题满分１０分）计算∫∫Σ−+−xzdxdyxydzdx dydz x 48)1(22，其中Σ是由曲线)0(a y e x y ≤≤=绕x 轴旋转而成的旋转曲面，其法向量与x 轴正向的夹角恒大于2π．七、 （本题满分１０分）计算∫−+−+−=L dzy x dy x z dx z y I )()()(222222，其中L 为平面1=++z y x 被三个坐标平面所截三角形Σ的边界，若从x 轴的正向看去，定向为顺时针方向．八、 （本题满分１０分） 证明∫∞+−+18sin dx y x x e xy 在),0[+∞上一致收敛．九、 加选题（本题满分１０分）设L 是不经过点)0,2(及点)0,2(−的分段光滑的简单闭曲线，试就L 的不同情形计算曲线积分∫ +++−+−−+ ++++−=L dy y x x y x x dx y x y y x y I .)2(2)2(2)2()2(22222222 其中L 取正向．1.解：0)()()(222222=+∂∂++∂∂++∂∂=y x zx z y z y x F div ,222222y x x z z y z y xk j i F rot +++∂∂∂∂∂∂= , ),,(2y x x z z y F rot −−−= , 或k y x j x z i z y F rot )(2)(2)(2−+−+−=.2.解：z x e y F −−=2, ),1,2(),,(22z x z x z y x e e F F F −−−=,)1,1,2(|),,()2,1,1(−==z y x F F F n , 于是所求法线方程为121121−=−=−−z y x 3.解：。

一、填空题(选做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。

大学期末考试试卷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 。

《算法分析与设计》期末试题及参考答案一、简要回答下列问题：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)一定合理。

一。

选择题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. 回溯法解旅行售货员问题时的解空间树是（ B ）。

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

《算法设计与分析》期末必考复习及答案题整理1、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。

递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，3、 Prim算法：设G=(V,E)是连通带权图，V={1,2,…,n}。

构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且c[j]最小的边，将顶点j添加到S 中。

这个过程一直进行到S=V时为止。

4、什么是剪枝函数：回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。

其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。

这两类函数统称为剪枝函数。

6、分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。

5、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。

6、最优子结构性质：该问题的最优解包含着其子问题的最优解。

7、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。

这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

《算法分析与设计》期末复习题一、选择题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。

2006-2007学年第⼆学期《算法设计与分析》A卷⼆、对于下列各组函数，确定f(n) = O(g(n))，或者f(n) =Ω(g(n))，或f(n)＝(g(n))。

（15分）1. f(n)=logn2, g(n)=logn+52. f(n)=logn2, g(n) = n3. f(n) = n, g(n)=log2n4. f(n)=nlogn+n, g(n)=logn三、给定如下矩阵连乘问题，⽤动态规划算法计算最优计算次序及最优值（15分）。

A1 A2 A3 A4 A5 A620×10 10×35 35×15 15×40 40×25 25×30四、对于数组a[0 : n-1]，给定n段合并排序算法如下，建⽴其计算复杂性递归表达式并求解（15分）。

Public static void mergesort(int [] a, int left, int right){if(left < right){int j = (int)Math.sqrt(right – left + 1);if(j > 1){for(int i = 0; i < j; i++)mergesort(a, left + i*j, left + (i + 1) *j – 1);mergesort(a, left+j*j, right);}mergeall(a, left, right);}}其中，算法mergeall合并n个排好序的数组段。

五、给定图如下，求出最⼩⽣成树以及以顶点1为源的单源最短路径。

（15分）六、证明求最⼤公约数的欧⼏⾥得算法的正确性，并分析其算法复杂性。

（15分）int gcd(int a, int b){if(b = = 0)return a;return gcd(b, a % b);}其中%为求模运算。

七、给定分别有n个元素的两个集合S和T，试设计⼀个判定S和T是否相等的蒙特卡罗算法，并分别就相等和不相等（有⼀个元素不同）两种情形分析算法正确的概率。

2007-2008学年第一学期期末试卷一、（6分，A 班不做）设x 1，x 2，…，x n 是来自正态总体2(,)N μσ的样本，令)x x T -=，试证明T 服从t -分布t （2）二、（6分，B 班不做）统计量F-F(n,m)分布，证明111(,)F F n m αααα-的（0<<1）的分位点x 是。

三、（8分）设总体X 的密度函数为(1),01(;) 0 , x x p x ααα⎧+<<=⎨⎩其他其中1α>-，是位置参数。

x 1，x 2，…，x n 是来自总体X 的简单样本，试求参数α的矩估计和极大似然估计。

四、（12分）设总体X 的密度函数为1x exp x (;) 0 , p x μμσσσ⎧⎧-⎫-≥⎨⎬⎪=⎭⎨⎩⎪⎩，其它，其中,0,μμσσ-∞<<+∞>已知，是未知参数。

x 1，x 2，…，x n 是来自总体X 的简单样本。

（1）试求参数σ的一致最小方差无偏估计σ∧； （2）σ∧是否为σ的有效估计？证明你的结论。

五、（6分，A 班不做）设x 1，x 2，…，x n 是来自正态总体211(,)N μσ的简单样本，y 1，y 2，…，y n 是来自正态总体222(,)N μσ的简单样本，且两样本相互独立，其中221122,,,μσμσ是未知参数，2212σσ≠。

为检验假设012112:, :,H H μμμμ=≠可令12, 1,2,..., , ,i i i z x y i n μμμ=-==-则上述假设检验问题等价于0111:0, :0,H H μμ=≠这样双样本检验问题就变为单检验问题。

基于变换后样本z 1，z 2，…，z n ，在显著性水平α下，试构造检验上述问题的t-检验统计量及相应的拒绝域。

六、（6分，B 班不做）设x 1，x 2，…，x n 是来自正态总体20(,)N μσ的简单样本，0μ已知，2σ未知，试求假设检验问题22220010:, :H H σσσσ≥<的水平为α的UMPT 。

算法设计与分析期末考试卷及答案a-CAL-FENGHAI.-(YICAI)-Company One1考生 信 息 栏 ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿装订线考生 信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿装订线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. ∑∈nD 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=k 2, 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 Θ。

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. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。

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

华南农业大学期末考试试卷（A卷）2007学年第一学期考试科目: 算法分析与设计考试类型: （开卷）考试时间: 120分钟学号姓名年级专业一、选择题（20分, 每题2分）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)。

}}上述算法的时间复杂度为A.A. O（2n）B. O（nlog n）C. Θ（n！）D. Θ（nn）2.当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时, 可以使用B来消除或减少问题的好坏实例间的这种差别.（A）数值概率算法（B）舍伍德算法（C）拉斯维加斯算法（D）蒙特卡罗算法3.对于下列二分搜索算法, 正确的是D.（A）public static int binarySearch(int[] a, int x, int n){int left = 0, right = n-1。

while(left <= right){int middle = (left + right) / 2。

if(x == a[middle]) return middle。

if(x > a[middle]) left = middle。

else right = middle。

}//whilereturn –1。

}（B）public static int binarySearch(int[] a, int x, int n) {int left = 0, right = n-1。

while(left+1 != right){int middle = (left + right) / 2。

if(x >= a[middle]) left = middle。

else right = middle。

}//whileif(x == a[left]) return left。

2006-2007学年第二学期《计算机算法设计与分析》试题院系：软件学院专业：软件工程年级：2004级一.简答题（共10分）略二.计算题(35分)1. (6 分)对下列各组函数f(n)和g(n),确定f(n)=O(g(n))或f(n)= Q(g(n))或f(n)=8 (g(n))。

(1)f(n)=3n, g(n)=2n2(2)f(n)=log n + 5, g(n)=log n(3)f(n)=log n, g(n尸J n咨：(1)f(n) = Q(g(n)) (2 分)(2)f(n) = 9(g(n)) (2 分)(3)f(n) = O(g(n)) (2 分)2. (8分)采用动态规划策略，计算a= {5,-37-4,-5,9,-2,10,-3,2}的最大子段和, 并给出这个最大子段和的起始下标和终止下标。

[设数组a中的元素下标从1开始。

]要求给出过程。

答：b[1]=5;b[2]=max{b[1]+a[2] , a[2]}=max{2,-3}=2b[3]=max{b[2]+a[3] , a[3]}=max{9,7}=9b[4]=max{b[3]+a[4] , a[4]}=max{5,-4}=5b[5]=max{b[4]+a[5] , a[5]}=max{0,-5}=0b[6]=max{b[5]+a[6] , a[6]}=max{9,9}=9b[7]=max{b[6]+a[7] , a[7]}=max{7,-2}=7b[8]=max{b[7]+a[8] , a[8]}=max{17,10}=17b[9]=max{b[8]+a[9] , a[9]}=max{14,-3}=14b[10]=max{b[9]+a[10] , a[10]}=max{16,2}=16(上述每两行1分，共5分)最大子段和为17 (1分)(若数组下标从1开始)起始下标：6 (1分)，终止下标：8 (1分)(若数组下标从0开始)起始下标：5 ( 0.5分)，终止下标：7 (0.5分)3 .（11分）设有3件工作分配给3个人，将工作i分配给第j个人所花的费用为C ij,现将为每一个人都分配1件不同的工作，并使总费用达到最小。

e i rb ei n一.填空题： 1. 元运算2. O 3.∑∈nD 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))3. (1) i>=1 (2)k[i]+1 (3) 1(4) i+1 (5) k[i]=0 (6) tag[x, y]=0(7) x=x-dx[k[i]]; y=y-dy[k[i]]四.算法设计题：1. 贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。

算法MINSTOPS输入：A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶的公里数m，存储各加油站离起点A的距离的数组d[1..n]。

输出：从A地到B地的最少加油次数k以及最优解x[1..k]（x[i]表示第i次加油的加油站序号），若问题无解，则输出no solution。

d[n+1]=s; //设置虚拟加油站第n+1站。

for i=1 to nif d[i+1]-d[i]>m thenoutput “no solution”; return //无解，返回end ifend fork=1; x[k]=1 //在第1站加满油。

s1=m //s1为用汽车的当前油量可行驶至的地点与A点的距离i=2while s1<sif d[i+1]>s1 then //以汽车的当前油量无法到达第i+1站。

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

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

不存在二义性。

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

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

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

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

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

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

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

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

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

二、建立迭代关系式。

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

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

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

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

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