算法设计与分析期末总复习

1、复习一、简答题（每小题5分，选答2题，共10分）1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。2. 简述非递归算法时间效率分析的通用方案。3. 简述递归算法时间效率的通用方案。4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。二、分析题（每小题10分，共20分）1. 考虑下面的算法。P52算法 Mystery(n) /输入：非负整数nS=0for i ß 1 to n doS ß S + i*iReturn Sa. 该算法求的是什么？b. 它的基本操作是什么？c. 该基本操作执行了多

2、少次？d. 该算法的效率类型是什么？2. 考虑下面的递归算法。P52算法 Secret(A0.n-1) /输入：包含n个实数的数组A0.n-1minval ß A0; maxval ß A0for i ß1 to n-1 doif Ai < minvalminval ß AiifAi > maxvalmaxval ß Aireturn maxval minvala. 该算法求的是什么？b. 它的基本操作是什么？c. 该基本操作执行了多少次？d. 该算法的效率类型是什么？3. 考虑下面的递归算法P59算法 Q(n) /输入：正整数if

3、 n=1 return 1else return Q(n-1) + 2*n -1a. 建立该函数值的递推关系并求解，以确定该算法计算的是什么；b. 建立该算法所做的乘法运算次数的递推关系并求解；c. 建立该算法所做的加减运算次数的递推关系并求解。三、算法设计题（每小题10分，共20分）1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调用树。(4章分治法)P1022. 对于下面的有向图，应用基于DFS的算法来解拓扑排序问题。(5章减治法)P133.3. 用自底向上算法为列表1, 8, 6, 5, 3, 7, 4进行堆排序。(6章变治法)P1754. 应用Hor

4、spool算法在下面的文本中查找模式BARBER：BSS_KNER_BARBER (7章时空权衡)P201四、计算题（每小题10分，共20分）1. 对于输入30, 20, 56, 75, 31, 19和散列函数h(K)=K mod 11(7章时空权衡)P207a. 构造它们的开散列表；b. 求在本表中成功查找的最大键值比较次数；c. 求在本表中成功查找的平均键值比较次数。2. 对由下面邻居矩阵定义的有向图，应用Warshall算法求它的传递闭包。(8章动态规划)P2223. 对于下面具有权重矩阵的有向图，求解完全最短路径问题。(8章动态规划)P2234. 应用Prim算法或Kruskal算法求下列图的最小生成树。(9章贪婪技术)P245五、综合题（每小题15分，共30分）1. 假设文本中字符及其出现概率如下表所示(9章贪婪技术)P253字符ABCD-出现概率0.40.10.20.150.15a. 利用上表的数据构造一套哈夫曼编码；b. 用a中的编码对文本ABACABAD进行编码；c.2. 用单纯形法解下列线性规划问题(10章迭代改进)P249最大化： 3x+5y约束： x