湖南大学2014算法设计与分析期中试题(及答案)

一、 函数渐进阶。对于下列各组f(x)和g(x)，确定他们的关系（15分）

a) f(x)=log n10+1；g(x)= log n – 10 b) f(x)=5? n10；g(x)= 10n c) f(x)=；g(x)= log n +5

二、 设n个不同的整数排好序后存于T[0:n-1]中。若存在下标i，0≤i

三、 分别用贪心算法（20分）、动态规划法（20分）设计求解0-1背包问题的算法。要求：1.说明算法策略（每种方法5分）；2.主要算法步骤（10分）；3.分析算法的时间复杂度（5分）

四、 试设计解决TSP问题的贪心算法（10分），分析时间复杂度（5分），试分析是否存在O(n2log n)的有效算法（5分）。

1 / 6

1函数渐进阶。对于下列各组f(x)和g(x)，确定他们的关系（15分）

a) f(x)=log n10+1；g(x)= log n – 10 b) f(x)=5? n10；g(x)= 10n c) f(x)=；g(x)= log n +5

2 / 6

2设n个不同的整数排好序后存于T[0:n-1]中。若下标i，0≤i

解答：由题可知，数组T[ ]是排列好的整数集。可以用二分搜索的算法对问题进行操作。取中间值T[mid],如果T[mid]=mid则可以返回mid；如果T[mid]mid在0到mid-1之间进行上述操作。

Int Findi(int T[],int m,int n) {

Int mid=(m+n)/2;

If (T[mid]==mid) return mid;

else if(T[mid]>mid) return Findi(T[],m,mid-1); else return Findi(T[],mid+1,n); }

3 / 6