算法设计与分析期末考试卷及答案a.doc

一．填空题（每空2分，共30分）
1．算法的时间复杂性指算法中 的执行次数。
2．在忽略常数因子的情况下，O、和三个符号中， 提供了算法运行时间的一个上界。
3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。
4．分治算法的时间复杂性常常满足如下形式的递归方程：

其中，g(n)表示 。
5. 分治算法的基本步骤包括 。
6．回溯算法的基本思想是 。
7．动态规划和分治法在分解子问题方面的不同点是 。
8．贪心算法中每次做出的贪心选择都是 最优选择。
9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越 。
10．选择排序、插入排序和归并排序算法中， 算法是分治算法。
11．随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到 的结果。
12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤 ，就可得到一个随机化快速排序算法，该随机化步骤的功能是 。
算法 QUICKSORT
输入：n个元素的数组A[1..n]。
输出：按非降序排列的数组A中的元素。

考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏
＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿ 学号＿＿＿＿＿
装 订 线

1. quicksort(1, n)
end QUICKSORT
过程 quicksort(A, low, high)
// 对A[low..high]中的元素按非降序排序。
2. if low<high then
3. w=SPLIT(A, low, high)
//算法SPLIT以A[low]为主元将A[low..high]划分成两部 //分，返回主元的新位置。
4. quicksort (A, low, w-1)
5. quicksort (A, w+1, high)
6． end if
end quicksort
13．下面算法的基本运算是 运算，该算法的时间复杂性阶为( )。
算法 SPLIT
输入：正整数n，数组A[1..n]。
输出：…。
i=1
x=A[1]
for j=2 to n
if A[j]<=x then
i=i+1
if ij then A[i]A[j]
end if
end for
A[i]A[1]
w =i
return w, A
end SPLIT
二．计算题和简答题（每小题7分，共21分）
1．用O、、表示函数f与g之间阶的关系，并分别指出下列函数中阶最低和最高的函数：
(1)　f (n)=100 g(n)=
(2) f(n)=6n+n g(n)=3n
(3) f(n)= n/logn-1 g(n)=
(4) f(n)= g(n)=
(5) f(n)= g(n)=
2．下面是一个递归算法，其中，过程pro1和pro2的运算时间分别是1和。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。
算法 EX1
输入：正整数n，n=2k。
输出：…
ex1(n)
end EX1
过程 ex1(n)
if n=1 then
pro1(n)
else
考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏
＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿ 学号＿＿＿＿＿
装 订 线

pro2(n)
ex1(n/2)
end if
return
end ex1
3．用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[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的一个下标并返回，若不存在，

//则返回0。
if (2) then return 0
else
mid=
if (3) then return mid
else
if A[mid]<mid then
return find( (4) )
else
return (5)
end if
end if
end if
end find
2．(10分) 下面是求解矩阵链乘问题的动态规划算法。
矩阵链乘问题：给出n个矩阵M1, M2, …, Mn , Mi 为riri+1阶矩阵，i=1, 2, …, n，求计算M1M2…Mn所需的最少数量乘法次数。
记 Mi, j=MiMi+1…Mj , i<=j。设C[i, j], 1<=i<=j<=n, 表示计算Mi, j的所需的最少数量乘法次数，则

算法 MATCHAIN
输入：矩阵链长度n, n个矩阵的阶r[1..n+1], 其中r[1..n]为n个矩阵的行数，r[n+1]为第n个矩阵的列数。
输出：n个矩阵链乘所需的数量乘法的最少次数。
考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏
＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿ 学号＿＿＿＿＿
装 订 线

for i=1 to n C[i, i]= （1）
　for d=1 to n-1
for i=1 to n-d
　　　j= (2)
C[i, j]= ∞
for k=i+1 to j
x= (3)
if x<C[i, j] then
(4) =x
end if
end for
end for
end for
return (5)
end MATCHAIN
3．(14分) 下面是用回溯法求解马的周游问题的算法。
马的周游问题：给出一个nxn棋盘，已知一个中国象棋马在棋盘上的某个起点位置（x0, y0），求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线。（设马走日字。）
算法 HORSETRAVEL
输入：正整数n，马的起点位置(x0, y0)，1<=x0, y0<=n 。
输出：一条从起点始访问nxn棋盘每个格点恰好一次，最后回到起点的周游路线；若问题无解，则输出no solution。
tag[1..n, 1..n]=0
dx[1..8]={2, 1, -1, -2, -2, -1, 1, 2}
dy[1..8]={1, 2, 2, 1, -1, -2, -2, -1}
flag=false
x=x0; y=y0 ; tag[x, y]=1
m=n*n
i=1; k[i]=0
while (1) and not flag
while k[i]<8 and not flag
k[i]= (2)
x1= x+dx[k[i]]; y1= y+dy[k[i]]
if ((x1,y1)无越界and tag[x1, y1]=0) or ((x1,y1)=(x0,y0) and i=m) then
x=x1; y=y1
tag[x, y]= (3)
if i=m then flag=true
else
i= (4)
(5)
end if
end if
end while
i=i-1
(6)
　 (7)
end while
if flag then outputroute(k) //输出路径
else output “no solution”　
end HORSETRAVEL

考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏
＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿ 学号＿＿＿＿＿
装 订 线

四．算法设计题（15分）
1. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为公里，0=，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。

《算法设计与分析》期考试卷(A)标准答案

一. 填空题：
1. 元运算
2. O
3.
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
阶最高的函数是：
2. 该递归算法的时间复杂性T(n)满足下列递归方程：

将n=, a=1, c=2, g(n)=, d=1代入该类递归方程解的一般形式得：
T(n)=1+=1+k-
=1+ k-=++1
所以，T(n)= ++1=。
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)