(完整版)算法设计与分析期末考试卷及答案a

一．填空题（每空2分，共30分） 1．算法的时间复杂性指算法中 的执行次数。 2．在忽略常数因子的情况下，O、和三个符号中， 提供了算法运行时间的一个上界。 3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： , nn0f(n)d  f(n)af(n/c)g(n) , nn0 其中，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 lowpro2(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=(lowhigh)/2 if (3) then return mid else if A[mid]一. 填空题： 1. 元运算

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

《算法设计与分析》期考试卷 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 s1if 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)