复习
一、简答题（每小题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
2. 对于下面的有向图，应用基于DFS的算法来解拓扑排序问题。

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

(6章变治法)P175
4. 应用Horspool算法在下面的文本中查找模式BARBER：BSS_KNER_BARBER (7章时空权衡)P201
四、计算题（每小题10分，共20分）
1. 对于输入30, 20, 56, 75, 31, 19和散列函数h(K)=K mod 11(7章时空权衡)P207
a. 构造它们的开散列表；
b. 求在本表中成功查找的最大键值比较次数；
c. 求在本表中成功查找的平均键值比较次数。

2. 对由下面邻居矩阵定义的有向图，应用Warshall算法求它的传递闭包。

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

(8章动态规划)P223
4. 应用Prim算法或Kruskal算法求下列图的最小生成树。

(9章贪婪技术)P245
五、综合题（每小题15分，共30分）
1.
字符 A B C D -
出现概率0.4 0.1 0.2 0.15 0.15
a.利用上表的数据构造一套哈夫曼编码；
b.用a中的编码对文本ABACABAD进行编码；
c.对于编码为1010文本用a中的编码进行解码。

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