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

《算法设计与分析(期末总复习)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、作是什么？c.该基本操作执行了多少次？d.该算法的效率类型是什么？2.考虑下面的递归算法。P52算法Secret(A[0..n-1])//输入：包含n个实数的数组A[0..n-1]minvalßA[0];maxvalßA[0]foriß1ton-1doifA[i]maxvalmaxvalßA[i]returnmaxval–minvala.该算法求的是什么？b.它的基本操作是什么？c.该基本操作执行了多少次？d.该算法的效率类型是什么？3.考虑下面的递归算

3、法P59算法Q(n)//输入：正整数ifn=1return1elsereturnQ(n-1)+2*n-1a.建立该函数值的递推关系并求解，以确定该算法计算的是什么；b.建立该算法所做的乘法运算次数的递推关系并求解；c.建立该算法所做的加减运算次数的递推关系并求解。三、算法设计题（每小题10分，共20分）1.应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调用树。(4章分治法)P102第9页　共9页2.对于下面的有向图，应用基于DFS的算法来解拓扑排序问题。(5章减治法)P1

4、33.第9页　共9页3.用自底向上算法为列表1,8,6,5,3,7,4进行堆排序。(6章变治法)P1754.应用Horspool算法在下面的文本中查找模式BARBER：BSS_KNER_BARBER(7章时空权衡)P201四、计算题（每小题10分，共20分）第9页　共9页1.对于输入30,20,56,75,31,19和散列函数h(K)=Kmod11(7章时空权衡)P207a.构造它们的开散列表；b.求在本表中成功查找的最大键值比较次数；c.求在本表中成功查找的平均键值比较次数。2.对由下面邻居矩阵定义的

5、有向图，应用Warshall算法求它的传递闭包。(8章动态规划)P222第9页　共9页3.对于下面具有权重矩阵的有向图，求解完全最短路径问题。(8章动态规划)P2234.应用Prim算法或Kruskal算法求下列图的最小生成树。(9章贪婪技术)P245第9页　共9页五、综合题（每小题15分，共30分）1.假设文本中字符及其出现概率如下表所示(9章贪婪技术)P253字符ABCD-出现概率0.40.10.20.150.15a.利用上表的数据构造一套哈夫曼编码；b.用a中的编码对文本ABACABAD进行编码；

6、c.对于编码为100010111001010文本用a中的编码进行解码。第9页　共9页第9页　共9页2.用单纯形法解下列线性规划问题(10章迭代改进)P249最大化：3x+5y约束：x+y≤4x+3y≤6x≥,y≥0a.填写初始单纯型表第9页　共9页a.写出每一步的入基变量和离基变量b.填写最终单纯型表并给出最优解目标函数的最大值：最优解为：第9页　共9页