湖南大學2014算法設計與分析期中試題(及答案)

1、一、函數(shù)漸進階。對于下列各組 f(x)和g(x)，確定他們的關系(15 分)a) f(x)=log n10+1; g(x)= log n -10b) f(x)=5 n10； g(x)=10nc) f(x)=； g(x)= log n +5二、設n個不同的整數(shù)排好序后存于 T0:n-1中。若存在下標i, 0in ,使得Ti=i,試設計一個時間復雜度為O(logn)的算法找到該下標(15分)，并用 C/C+編程實現(xiàn)(10 分)。三、分別用貪心算法( 20 分)、動態(tài)規(guī)劃法( 20 分)設計 求解 0-1 背包問題的算法。要求： 1.說明算法策略(每種 方法 5 分)； 2.主要算法步驟( 10 分

2、)； 3.分析算法的時 間復雜度( 5 分)四、試設計解決TSP問題的貪心算法(10分)，分析時間復雜度(5分)，試分析是否存在O(n2log n)的有效算法( 5 分)。5 / 61函數(shù)漸進階。對于下列各組f(x)和g(x)，確定他們的關系(15 分)a) f(x)=log n1+1; g(x)= log n TOb) f(x)=5 n10； g(x)=10nc) f(x)=; g(x)= log n +52設n個不同的整數(shù)排好序后存于T0:n-1中。若下標i ,0in ,使得Ti=i，試設計一個時間復雜度為O(logn)的存在算法找到該下標(15分)，并用C/C+編程實現(xiàn)(10分)。解答：

3、由題可知，數(shù)組 T 是排列好的整數(shù)集。可以用二分 搜索的 算法 對問題進行操作。 取中 間 值 Tmid, 如果 Tmid=mid 則可以返回 mid ；如果 Tmidmid 在 0 到 mid-1 之間進行 上述操作。Int Findi(int T,int m,int n)Int mid=(m+n)/2;If (Tmid=mid) return mid;else if(Tmidmid) return Findi(T,m,mid-1);else return Findi(T,mid+1,n);算法設計：輸入：一個數(shù)組 T ，起始地址 m ，末端地址 n 比較指定數(shù)組位置的中間元素T(m+n)/

4、 2 與中間地址 (m+n)/2.1) 如果 T(m+n)/2等于(m+n)/2，則返回(m+n)/2 ;2) 如果T(m+n)/2大于(m+n)/2，則返回在數(shù)組 T中m位到(m+n)/2-1 之間進行此算法的返回值；3) 如果T(m+n)/2小于(m+n)/2，則返回在數(shù)組 T中(m+n)/2+1 到n之間進行此算法的返回值；輸出：一個值，若存在則返回i;若不存在則返回0.3 分別用貪心算法（ 20 分）、動態(tài)規(guī)劃法（ 20 分）設計求 解 0-1 背包問題的算法。要求： 1. 說明算法策略（每種方法5 分）； 2.主要算法步驟（ 10 分）； 3. 分析算法的時間復雜 度（5 分）4試設計解決TSP問題的貪心算法（10分），分析時間復雜 度O（n2） （5分），試分析是否存在 O（n2log n）的有效算法（5 分）。答：貪心策略 ：在當前節(jié)點下遍歷所有能到達的下一節(jié)點，選擇 距離最近的節(jié)點作為下一節(jié)點。基本思路：1、從一節(jié)點出發(fā)遍歷所有能到達的下一節(jié)點，選擇距離最近的節(jié)點作為下一節(jié)點；2、然后把當前節(jié)點標記已走過，