算法设计与分析期末考试卷及答案a

1、一填空题（每空2分，共30分）1算法的时间复杂性指算法中 的执行次数。2在忽略常数因子的情况下，O、和三个符号中， 提供了算法运行时间的一个上界。3设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。4分治算法的时间复杂性常常满足如下形式的递归方程： 其中，g(n)表示 。5. 分治算法的基本步骤包括 。6回溯算法的基本思想是 。7动态规划和分治法在分解子问题方面的不同点是 。8贪心算法中每次做出的贪心选择都是 最优选择。9PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越 。10选择

2、排序、插入排序和归并排序算法中， 算法是分治算法。 11随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到 的结果。 12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤 ，就可得到一个随机化快速排序算法，该随机化步骤的功能是 。算法 QUICKSORT输入：n个元素的数组A1.n。输出：按非降序排列的数组A中的元素。考生信息栏学院系 专业 年级姓名 学号装 订 线1. quicksort(1, n)end QUICKSORT过程 quicksort(A, low, high)/ 对Alow.high中的元素按非降序排序。 2. if low<high then3.

3、 w=SPLIT(A, low, high) /算法SPLIT以Alow为主元将Alow.high划分成两部 /分，返回主元的新位置。4. quicksort (A, low, w-1)5. quicksort (A, w+1, high)6 end ifend quicksort13下面算法的基本运算是 运算，该算法的时间复杂性阶为( )。算法 SPLIT输入：正整数n，数组A1.n。输出：。 i=1 x=A1 for j=2 to n if Aj<=x then i=i+1 if ij then AiAj end if end for AiA1w =i return w, Aend

4、SPLIT二计算题和简答题（每小题7分，共21分）1用O、表示函数f与g之间阶的关系，并分别指出下列函数中阶最低和最高的函数：(1)f (n)=100 g(n)= (2) f(n)=6n+n g(n)=3n(3) f(n)= n/logn-1 g(n)=(4) f(n)= g(n)=(5) f(n)= g(n)= 2下面是一个递归算法，其中，过程pro1和pro2的运算时间分别是1和。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。 算法 EX1 输入：正整数n，n=2k。 输出： ex1(n) end EX1过程 ex1(n) if n=1 the

5、n pro1(n)else 考生信息栏学院系 专业 年级姓名 学号装 订 线pro2(n)ex1(n/2)end ifreturnend ex13用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dki, j表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。三算法填空题（共34分）1（10分）设n个不同的整数按升序存于数组A1.n中，求使得Ai=i的下标i 。下面是求解该问题的分治算法。 算法 SEARCH 输入：正整数n，存储n个按升序排列的不同整数的数组A1.n。 输出：A1.n中使得Ai=i的一个下标i，若不存在，则输出 no soluti

6、on。i=find ( (1) )if i>0 then output ielse output “no solution”end SEARCH过程 find (low, high) / 求Alow.high 中使得Ai=i的一个下标并返回，若不存在， /则返回0。 if (2) then return 0 else mid= if (3) then return mid else if Amid<mid then return find( (4) )elsereturn (5) end if end if end ifend find2(10分) 下面是求解矩阵链乘问题的动态规划

7、算法。矩阵链乘问题：给出n个矩阵M1, M2, , Mn , Mi 为riri+1阶矩阵，i=1, 2, , n，求计算M1M2Mn所需的最少数量乘法次数。记 Mi, j=MiMi+1Mj , i<=j。设Ci, j, 1<=i<=j<=n, 表示计算Mi, j的所需的最少数量乘法次数，则 算法 MATCHAIN输入：矩阵链长度n, n个矩阵的阶r1.n+1, 其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵链乘所需的数量乘法的最少次数。 考生信息栏学院系 专业 年级姓名 学号装 订 线for i=1 to n Ci, i= （1） for d=

8、1 to n-1 for i=1 to n-d j= (2) Ci, j= for k=i+1 to j x= (3) if x<Ci, j then (4) =x end if end for end for end for return (5) end MATCHAIN3(14分) 下面是用回溯法求解马的周游问题的算法。马的周游问题：给出一个nxn棋盘，已知一个中国象棋马在棋盘上的某个起点位置（x0, y0），求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线。（设马走日字。）算法 HORSETRAVEL 输入：正整数n，马的起点位置(x0, y0)，1<=x0, y0&l

9、t;=n 。输出：一条从起点始访问nxn棋盘每个格点恰好一次，最后回到起点的周游路线；若问题无解，则输出no solution。tag1.n, 1.n=0 dx1.8=2, 1, -1, -2, -2, -1, 1, 2dy1.8=1, 2, 2, 1, -1, -2, -2, -1 flag=false x=x0; y=y0 ; tagx, y=1 m=n*n i=1; ki=0 while (1) and not flag while ki<8 and not flag ki= (2) x1= x+dxki; y1= y+dyki if (x1,y1)无越界and tagx1, y1

10、=0) or (x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tagx, y= (3) if i=m then flag=true elsei= (4) (5) end if end if end whilei=i-1 (6) (7) end while if flag then outputroute(k) /输出路径 else output “no solution”end HORSETRAVEL考生信息栏学院系 专业 年级姓名 学号装 订 线四算法设计题（15分）1. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第

11、i个加油站离起点A的距离为公里，0=，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。算法设计与分析期考试卷(A)标准答案一. 填空题： 1. 元运算2. O3. 4. 将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间5. 分解，递归，组合6. 在问题的状态空间树上作带剪枝的DFS搜索（或：DFS+剪枝）7. 前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的8. 局部9. 高10. 归并排序算法11. 不

12、同12. v=random (low, high); 交换Alow和Av的值 随机选主元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阶最高的函数是：2. 该递归算法的时间复杂性T(n)满足下列递归方程： 将n=, a=1, c=2, g(n)=, d=1代入该类递归方程解的一般形式得：T(n)=1+=1+k-=1+ k-=+1所以，T(n)= +1=。3. 三. 算法填空题：1. (1) 1, n (2) l

13、ow>high (3) Amid=mid (4) mid+1, high (5) find(low, mid-1)2. (1) 0 (2) i+d (3) Ci, k-1+Ck, j+ri*rk*rj+1 (4) Ci, j (5) C1, n3. (1) i>=1 (2)ki+1 (3) 1 (4) i+1 (5) ki=0 (6) tagx, y=0 (7) x=x-dxki; y=y-dyki四. 算法设计题：1. 贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。算法 MINSTOPS输入：A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶的公里数m，存储各加油站离起点A的距离的数组d1.n。输出：从A地到B地的最少加油次数k以及最优解x1.k（xi表示第i次加油的加油站序号），若问题无解，则输出no solution。 dn+1=s; /设置虚拟加油站第n+1站。 for i=1 to n if di+1-di>m then output “no solution”; return /无解，返回en