考
生 信 息 栏 ＿＿
＿
＿＿
＿学
院＿＿＿
＿＿
＿系＿
＿
＿
＿
＿
＿
专
业
＿
＿
＿
＿
＿
＿
年
级
姓
名
＿
＿
＿
＿
＿
＿
学号＿
＿＿＿
＿ 装 订 线
考 生
信 息 栏 ＿
＿＿
＿＿
＿学院＿
＿＿
＿＿
＿
系＿
＿
＿
＿
＿
＿
专业
＿
＿
＿
＿
＿
＿年
级
姓名
＿
＿
＿
＿
＿
＿
学号＿
＿＿＿＿ 装 订 线 pro2(n) ex1(n/2) end if return end ex1 3．用Floyd 算法求下图每一对顶点之间的最短路径长度，计算矩阵D 0，D 1，D 2和D 3，其中D k [i, j]表示从顶点i 到顶点j 的不经过编号大于k 的顶点的最短路径长度。

三．算法填空题（共34分） 1．（10分）设n 个不同的整数按升序存于数组A[1..n]中，求使得A[i]=i 的下标i 。

下面是求解该问题的分治算法。

算法 SEARCH 输入：正整数n ，存储n 个按升序排列的不同整数的数组A[1..n]。

输出：A[1..n]中使得A[i]=i 的一个下标i ，若不存在，则输出 no solution 。

i=find ( (1) ) if i>0 then output i else output “no solution ” end SEARCH 过程 find (low, high) // 求A[low..high] 中使得A[i]=i 的一个下标并返回，若不存在，
考
生 信
息 栏 ＿＿
＿＿＿＿学
院＿
＿＿
＿＿
＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级
姓
名
＿
＿
＿
＿
＿
＿
学号＿
＿＿＿
＿ 装
订
线
《算法设计与分析》期考试卷(A)标准答案 一. 填空题：
1. 元运算 考
生 信 息 栏 ＿
＿
＿＿＿＿学
院＿
＿＿
＿＿
＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级
姓
名
＿
＿
＿
＿＿
＿ 学号＿
＿
＿＿
＿ 装
订
线
2. O
3.
∑∈n D I I t I p )()(
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
阶最高的函数是：n 3
2. 该递归算法的时间复杂性T(n)满足下列递归方程：
⎩⎨⎧>+===1
n ,n log T(n/2)T(n)1n , 1T(n)2 将n=k
2, a=1, c=2, g(n)=n log 2, d=1代入该类递归方程解的一般形式得： T(n)=1+∑-=1k 0i i 22n log =1+k n log 2-∑-=1k 0i i =1+ k n log 2-
2)1k (k -=n log 2122+n log 2
12+1 所以，T(n)= n log 2122+n log 212+1=)(log 2n Θ。

3.
⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∞=051060320D 0 ⎥⎥⎥⎦
⎤⎢⎢⎢⎣⎡∞=051050320D 1 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∞=05850320D 2
⎥⎥⎥⎦
⎤⎢⎢⎢⎣⎡=058503270D 3
三. 算法填空题：
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<s
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)
最新文件---------------- 仅供参考--------------------已改成-----------word文本--------------------- 方便更改
11 / 11word.。