2. O 3.
I?Dn?p(I)t(I)
4. 将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间 5. 分解，递归，组合
6. 在问题的状态空间树上作带剪枝的DFS搜索（或：DFS+剪枝）
7. 前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的 8. 局部 9. 高
10. 归并排序算法 11. 不同
12. v=random (low, high); 交换A[low]和A[v]的值 随机选主元 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
阶最高的函数是：3n
2. 该递归算法的时间复杂性T(n)满足下列递归方程： ? , n?1?T(n)?1
?T(n)?T(n/2)?log2n , n?1将n=2, a=1, c=2, g(n)=log2n, d=1代入该类递归方程解的一般形式得：
k?1nT(n)=1+?log2i=1+klog2n-?i
2i?0i?0k?1k
k(k?1)112=log2n+log2n+1 2221122所以，T(n)= log2n+log2n+1=?(logn)。
22=1+ klog2n-3.
?0?2??0?2??0?2??????? D0?306 D1?305 D2?305 ??????????1050???1050???850???072??? D3?305 ????850??
三. 算法填空题：
1. (1) 1, n (2) low>high (3) A[mid]=mid
(4) mid+1, high (5) find(low, mid-1) 2. (1) 0 (2) i+d (3) C[i, k-1]+C[k, j]+r[i]*r[k]*r[j+1] (4) C[i, j] (5) C[1, n]
3. (1) i>=1 (2)k[i]+1 (3) 1
(4) i+1 (5) k[i]=0 (6) tag[x, y]=0
(7) x=x-dx[k[i]]; y=y-dy[k[i]]
四. 算法设计题：
1. 贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油
耗尽前所能到达的最远的油站为止，在该油站再加满油。 算法 MINSTOPS
输入：A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶的公里数
m，存储各加油站离起点A的距离的数组d[1..n]。
输出：从A地到B地的最少加油次数k以及最优解x[1..k]（x[i]表示第i次加油的加油
站序号），若问题无解，则输出no solution。
d[n+1]=s; //设置虚拟加油站第n+1站。 for i=1 to n
if d[i+1]-d[i]>m then
output “no solution”; return //无解，返回 end if
end for
k=1; x[k]=1 //在第1站加满油。
s1=m //s1为用汽车的当前油量可行驶至的地点与A点的距离 i=2
while s1
if d[i+1]>s1 then //以汽车的当前油量无法到达第i+1站。 k=k+1; x[k]=i //在第i站加满油。 s1=d[i]+m //刷新s1的值 end if i=i+1
end while
output k, x[1..k]
MINSTOPS
最坏情况下的时间复杂性：Θ(n)
相关推荐：
loading