《算法分析与设计》期末试题及参考答案

1、文档来源为 :从网络收集整理.word 版本可编辑.欢迎下载支持.2算法分析与设计期末试题及参考答案、简要回答下列问题1.1.2.算法重要特性是什么？确定性、可行性、输入、输出、有穷性2. 算法分析的目的是什么？2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。3.3. 算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小 n 的函数。4. 算法的渐进时间复杂性的含义？4当问题的规模n 趋向无穷大时，影响算法效率的重要因素是T(n) 的数量级，而其他因素仅是使时间复杂度相差常数倍， 因此可以用 T(n) 的数量级 ( 阶) 评价算

2、法。时间复杂度 T(n) 的数量级 (阶) 称为渐进时间复杂性。5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n 固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n , I) , I C Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) = EP(I)T(n , I) I C Dn6. 简述二分检索(折半查找)算法的基本过程。7. 设输入是一个按非降次序排列的元素表Ai ： j 和 x ，选取 A(i+j)/2 与 x 比较，如果 A(i+j

3、)/2=x ，则返回 (i+j)/2 ，如果 A(i+j)/2<x ，则 Ai ： (i+j)/2-1 找 x， 否则在 A (i+j)/2+1： j 找 x 。上述过程被反复递归调用。8. 背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。目标函数：获得最大利润。最优量度：最大利润 / 重量比。8. 采用回溯法求解的问题，其解如何表示？有什么规定？8.问题的解可以表示为n元组：(xi,X2,Xn),XiCS, S i为有穷集合，Xi C S,(xi,X2,xn)具备完备性，即(xi,X2,xn)是合理的，则(xi,X2,Xi) (i<n) 一定合理。9. 回溯法的搜索特

4、点是什么？9. 在解空间树上跳跃式地深度优先搜索，即用判定函数考察xk 的取值，如果xk是合理的就搜索xk 为根节点的子树，如果xk 取完了所有的值，便回溯到 xk-1 。10. n 皇后问题回溯算法的判别函数place 的基本流程是什么？10. 将第 K 行的皇后分别与前k-1 行的皇后比较， 看是否与它们相容， 如果不相容就返回 false ，测试完毕则返回 true 。11. 为什么用分治法设计的算法一般有递归调用？11 . 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。12. 为什么要分析最坏情况下的算法时间复杂性？ 、12 最坏情况下的时间复杂性决定算法的优劣，

5、 并且最坏情况下的时间复杂性较平均时 间复杂性游可操作性。13. 简述渐进时间复杂性上界的定义。13 .T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C, nNo,有 T(n)<f(n) ，这种关系记作T(n)=O(f(n)。14. 二分检索算法最多的比较次数？14 . 二分检索算法的最多的比较次数为 log n 。15. 快速排序算法最坏情况下需要多少次比较运算？15.1. 坏情况下快速排序退化成冒泡排序，需要比较n2次。16. 贪心算法的基本思想？16 . 是一种依据最优化量度依次选择输入的分级处理方法。 基本思路是： 首先根据题意，选取一种 量度标准； 然

6、后 按这种量度标准对这 n 个输入排序， 依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。17 .回溯法的解(Xl,X 2,xn)的隐约束一般指什么？17.回溯法的解(xi,x 2,Xn)的隐约束一般指个元素之间应满足的某种关系。18. 阐述归并排序的分治思路。18. 讲数组一分为二， 分别对每个集合单独排序， 然后将已排序的两个序列归并成一个 含 n 个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。19. 快速排序的基本思想是什么。19. 快速排序的基本思想是在待排序的 N 个记录中任意取一个记录，把该记录放在最终 位

7、置后， 数据序列被此记录分成两部分。 所有关键字比该记录关键字小的放在前一部分， 所 有比它大的放置在后一部分， 并把该记录排在这两部分的中间， 这个过程称作一次快速排序。 之后重复上述过程，直到每一部分内只有一个记录为止。20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？20. 在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q, Q又调用P,这个称为间接递归。消除递归一般要用到栈这种数据结构。21. 什么是哈密顿环问题？文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持21 .哈密顿

8、环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。22 .用回溯法求解哈密顿环，如何定义判定函数？22 .当前选择的节点Xk是从未到过的节点，即Xk wXi(i=1,2,k-1)，且C(Xk-1, Xk) woo,如果 k=i ,则 c(xk, X1) woo。23 .请写出prim算法的基本思想。23.思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T,根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。二、复杂性分析1、MERGE

9、SORT(lowhigh) if low<high ;then mid (low , high)/2 ;MERGESORT(low , mid);MERGESORT(mid+1 , high); MERGE(low , mid, high); endifend MERGESORTT(n) = 2( 2T (x / 4)+ch / 2)+cn= 4r(n/4) + 2cM=2C 7(1) +Acm=口曰+心口 leg n二、复杂性分析 K递归方程.、 1口冏=12T(tt/2)+Ctt ft AI 设nW上 解递归方程：2、procedure S1(P , VV M X, n) i 1;

10、a -0 while i < n doif W(i)>M then return endifa a+ii -i+1 ;repeat end1 + 1时间为: 0(1)while £ n do 循环 n 次 循环体内所用时间为0(1)所以总时间为：T(n)=0(l)+ 破= 0(n)3.procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)vA(m);i mlooploop i i+1 until A(i)> v repeatloop p p-1 until A(p)< v repeatif i<pthe

11、n call INTERCHANGE(A(i),A(p) else exitendifrepeatA(m) -A(p);A(p)- vEnd PARTITION3解：、最多的查找次数是p-m+1次4 .procedure F1(n) if n<2 then return(1)else return(F2(2,n,1,1) endif end F1procedure F2(i,n,x,y) if i < nthen call F2(i+1,n,y,x+y) endifreturn(y) end F24、解：F2 (2, n,1,1 )的时间复杂度为：T(n)=O(n-2); 因为i

12、Wn时要递归调用F2, 一共是n-2次当n=1时F1(n)的时间为 O(1)当n>1时F1(n)的时间复杂度与 F2(2,n,1,1)的时间复杂度相同即为为O(n)5 .procedure MAX(A,n,j)xmaxfor iA(1);j -1-2 to n doif A(i)>xmax then xmaxA(i); j i;endifrepeat end MAX答案5 、xmaxA(1);j 1 时间为：O(1)for i 2 to n do循环最多n-1次所以总时间为：T(n)=O(1)+(n-1)O(1)= O(n)6 .procedure BINSRCH(A,n,x,j)

13、 integer low,high,mid,j,n; low -1;high n while low< high domid |_(low+high)/2_|case:x<A(mid):highmid-1:x>A(mid):low -mid+1:else:jmid; returnendcaserepeatj 0end BINSRCH答案6 、log 2n+1三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。C(1,2)=3,C(1,3)=5,C(1,4)=2，C(3,6)=4 , C(4,5)=2 , C(4,6)=1C(2,6)=8,C(2,7

14、)=4,C(3,5)=5C(5,8)=4,C(6,8)=5,C(7,8)=6答案：1、Cost(4,8)=0Cost(3,7)= C(7,8)+0=6, D5=8Cost(3,6)= C(6, 8)+0=5, D6=8Cost(3,5)= C(5, 8)+0=4 D7=8Cost(2,4)=minC(4, 6)+ Cost(3,6), C(4, 5)+ Cost(3,5)=min1+5,2+4=6 D4=6Cost(2,3)=minC(3, 6)+ Cost(3,6) =min4+5=9 D3=5Cost(2,2)=minC(2, 6)+ Cost(3,6), C(2, 7)+ Cost(3,

15、7)=min8+5,4+6=10 D2=7Cost(1,1)=minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) =min3+10,5+9,2+6= 8D1=41 一 4一 6一 82、写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=(48,12,61,3,5,19,32,7)答案2、 写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=()1、 48,12,61,3,5,19,32,72、48,12 61,3 5,1932,73、48 61, 12 3 19 32, 574、61 32 3 55、

16、61 33、给出5个数(3,6,9,1,7),M=13,用递归树描述 sumofsub算法求和数=M的一个子集的过程。给出5个酊(3, 6, 9,1, 7),附二12,用递归轨描述tfiUMOfsub算法求和数5的一个于集 的过程。4、 快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)4、第一个分割元素为65(1)(2)(3)(4)C5)(6)(7)(工65707580855550265Z.758085555 bQ70652QQ0T855575?06525055858Q75705570758085&55Q2-

17、1 2 3 4 4115、 归并排序算法对下列实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)6、48,12,61,35,19,32,748,12 61,35,1932,712,48 3,615,197,323, 12, 48, 615, 7, 19, 323,5, 7,12 , 19, 32, 48,616、写出图着色问题的回溯算法的判断Xk是否合理的过程。7、 i 0while i<k doif Gk,i=1 and Xk= Xi then return falsei -i+1repeatif i= k then return true7、8、K 1X1

18、-1 ,返回 trueX2 -1,返回 false; X2-X2+1=2,返回 trueX3 -1 ,返回 false; X3-X3+1=2,返回 false;X3 -X3+1=3, 返回 trueX4 -1,返回 false; X4-X4+1=2,返回 false;X4 -X4+1=3, 返回 true找到一个解 (1, 2, 3, 3)8、写出第7题的状态空间树。分成两个子问题分成四个子问题分成八个子问题返回上一层返回上一层排序结束，返回主函数9、写出归并排序算法对下列实例排序的过程。(6,2,9,3,5,1,8,7)9、调用第一层次 6,2,9,35,1,8,7调用第二层次6,2 9,3

19、5,1 8,7调用第三层次6 2 9 35 1 8 7调用第四层次只有一个元素返回上一层第三层归并2 ,6 3, 9 1,5 7,8第二层归并2 ,3,6, 91,5,7,8第一层归并1,2 ,3, 5 ,6, 7, 8,910、写出用背包问题贪心算法解决下列实例的过程。P=(18,12,4,1)W=(12,10,8,3)M=2510、实例符合 P(i)/W(i)>P(i+1)/W(i+1) 的顺序。CU 25,X 0W1< CU: x1-1; CUCU-W1=13;W2< CU: x2- 1; CU CU-W2=3;W3>CU: x3 CU/ W3=3/8;实例的解为

20、：(1, 1, 3/8, 0)11、有一个有序表为1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100,当使用 二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。解一共要要执行四次才能找到值为82的数。12、使用prim算法构造出如下图 G的一棵最小生成树。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=613、有如下函数说明int f(int x,in

21、t y)f=x Mod y +1;已知a=10,b=4,c=5则执行k=f(f(a+c,b),f(b,c) 后，k的值是多少并写出详细过程。K的值是514、McCathy函数定义如下：当 x>100 时 m(x)=x-10;当 x<=100 时 m(x)=m(m(x+11);编写一个递归函数计算给定x的m(x)值。int m(int x)int y；if(x>100) return(x-100);elsey=m(x+11);return (m(y);15、设计一个算法在一个向量A中找出最大数和最小数的元素。解Void maxmin(A,n)Vector A;int n;int

22、 max,min,i;max=A0;min=A0;for(i=0;i<=n;i+)if(Ai>max)max=Ai;else if(Ai<min)min=Ai;printf("max=%d,min=%dn' ，max,min);参考答案三、算法理解12.使用普里姆算法构造出如下图G的一棵最小生成树。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6四、设计算法1.1. 设有

23、n项独立的作业1,2,，n,由m台相同的机器加工处理。作业 i所需要的 处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理； 任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。解：对于处理机j ,用Sj表示处理机j已有的作业数，用 Pj,k表示处理机j的第 k个作业的序号。1)将作业按照t1*2 >> tn排序2) S1:m清零j -0/从第一个处理机开始安排3) for i - 1 to n do / 安排 n 个作业j j mod m +1/选下一个处

24、理机Sj -Sj+1;Pj,Sj1；Repeat2.2.设有n种面值为：d1>d2>> dn的钱币，需要找零钱M,如何选择钱币dk,的数目X,满足d1XX +dnX X M ,使得X +X最小请选择贪心策略，并设计贪心算法。贪心原则：每次选择最大面值硬币。为解向量为第i中硬币数CUH M;i1;X0/ XWhile CU w 0 doXi - CU div di / XiCl> CU-di*Xi文档来源为 :从网络收集整理.word 版本可编辑.欢迎下载支持i -i+1;repeat3、 3. 有 n 个物品， 已知 n=7, 利润为 P=(10,5,15,7,6,18

25、,3)， 重量 W=(2,3,5,7,1,4,1)，背包容积M=15，物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获 最优解。定义结构体数组 G,将物品编号、利润、重量彳为一个结构体：例如 Gk=1,10,2求最优解，按利润 / 重量的递减序，有5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3 ,5/3 4,7,7,1算法procedure KNAPSACK(P ， W， M， X， n)/P(1： n) 和 W(1； n) 分别含有按P(i)/W(i)> P(i+1)/W(i+1) 排序 的n件物品的效益值和重量。M是背包的容量大小，而 x(1 ： n)是解向量real P(1： n) ， W(1： n) ， X(1 ： n) ， M， cu；integer i ， n ；X 0 /将解向量初始化为零/cu M /cu 是背包