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

复习

一、简答题（每小题5分，选答2题，共10分）

1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。

4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。

二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52

算法 Mystery(n) //输入：非负整数n

S=0

for i ? 1 to n do

S ? S + i*i Return S

a. 该算法求的是什么？ b. 它的基本操作是什么？ c. 该基本操作执行了多少次？ d. 该算法的效率类型是什么？

2. 考虑下面的递归算法。P52

算法 Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ? A[0]; maxval ? A[0] for i ?1 to n-1 do if A[i] < minval minval ? A[i] if A[i] > maxval maxval ? A[i] return maxval – minval a. 该算法求的是什么？ b. 它的基本操作是什么？ c. 该基本操作执行了多少次？ d. 该算法的效率类型是什么？

3. 考虑下面的递归算法P59 算法 Q(n) //输入：正整数 if n=1 return 1 else return Q(n-1) + 2*n -1

a. 建立该函数值的递推关系并求解，以确定该算法计算的是什么； b. 建立该算法所做的乘法运算次数的递推关系并求解； c. 建立该算法所做的加减运算次数的递推关系并求解。

三、算法设计题（每小题10分，共20分）

1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调用树。(4章分治法)P102

第 1 页 共 9页

2. 对于下面的有向图，应用基于DFS的算法来解拓扑排序问题。(5章减治法)P133.

第 2 页 共 9页

3. 用自底向上算法为列表1, 8, 6, 5, 3, 7, 4进行堆排序。(6章变治法)P175

4. 应用Horspool算法在下面的文本中查找模式BARBER：BSS_KNER_BARBER (7章时空权衡)P201

四、计算题（每小题10分，共20分）

第 3 页 共 9页

1. 对于输入30, 20, 56, 75, 31, 19和散列函数h(K)=K mod 11(7章时空权衡)P207 a. 构造它们的开散列表；

b. 求在本表中成功查找的最大键值比较次数； c. 求在本表中成功查找的平均键值比较次数。

2. 对由下面邻居矩阵定义的有向图，应用Warshall算法求它的传递闭包。(8章动态规划)P222

第 4 页 共 9页

3. 对于下面具有权重矩阵的有向图，求解完全最短路径问题。(8章动态规划)P223

4. 应用Prim算法或Kruskal算法求下列图的最小生成树。(9章贪婪技术)P245

第 5 页 共 9页

本文来源：https://www.bwwdw.com/article/um2t.html