算法設(shè)計與分析c&k

1、1網(wǎng)絡(luò)學(xué)院算法試題C及答案一填空題：（每題4分，共20分）1.環(huán)境?？臻g用來保存函數(shù)調(diào)用返回時恢復(fù)運(yùn)行所需要的信息，具體包括環(huán)境棧空間用來保存函數(shù)調(diào)用返回時恢復(fù)運(yùn)行所需要的信息，具體包括。（返回地址；所有局部變量的值、遞歸函數(shù)的傳值形式參數(shù)的值；所有引用參數(shù)以及常量（返回地址；所有局部變量的值、遞歸函數(shù)的傳值形式參數(shù)的值；所有引用參數(shù)以及常量引用參數(shù)的定義。引用參數(shù)的定義。）2估算程序運(yùn)行時間的方法通常有兩種，分別為估算程序運(yùn)行時間的方

2、法通常有兩種，分別為和。（操作計數(shù)方法，統(tǒng)計程序的執(zhí)行步數(shù)）（操作計數(shù)方法，統(tǒng)計程序的執(zhí)行步數(shù)）3遞歸函數(shù)的兩大基本要素是遞歸函數(shù)的兩大基本要素是和。（遞歸方程和邊界條件）（遞歸方程和邊界條件）4一個分治法將規(guī)模為一個分治法將規(guī)模為n(n1)的問題分成的問題分成k個規(guī)模為個規(guī)模為n／m的子問題去解。設(shè)分解閥值的子問題去解。設(shè)分解閥值n0=1，且解規(guī)模為且解規(guī)模為1的問題耗費(fèi)的問題耗費(fèi)1個單位時間個單位時間。再設(shè)將原問題分解為再設(shè)將原問題

3、分解為k個子問題以及由個子問題以及由k個子問題的解合并為原問題的解需用子問題的解合并為原問題的解需用f(n)個單位時間。用個單位時間。用T(n)表示該分治法解規(guī)模為表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則問題所需的計算時間，則T(n)=。（kT(nm)f(n)）5采用回溯法求解問題時，通常采用兩種策略（即兩種剪枝函數(shù)）避免無效的搜索，它們采用回溯法求解問題時，通常采用兩種策略（即兩種剪枝函數(shù)）避免無效的搜索，它們分別是分別

4、是?????????????和?????????????。（約束函數(shù)，限界函數(shù)）（約束函數(shù)，限界函數(shù)）二簡答題：（每小題6分，共18分）1.簡述分治法的總體思想：簡述分治法的總體思想：a)將難以直接求解的大問題分解為將難以直接求解的大問題分解為k個相同的子問題個相同的子問題b)對這對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問個子問題，如此遞歸的進(jìn)行下去，直

5、到問題規(guī)模足夠小，很容易求出其解為止題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止c)將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。來問題的解。d)經(jīng)分解得到的各個子問題相互獨立。經(jīng)分解得到的各個子問題相互獨立。2.2.假設(shè)以加法和乘法為關(guān)鍵操作，估算下述假設(shè)以加法和乘法為關(guān)鍵操作，估算下述n次多項式求值函數(shù)的時

6、間復(fù)雜度（取次多項式求值函數(shù)的時間復(fù)雜度（取T為整為整型）型）templateTPolyEval(Tcoeff[]intnconstTf(i=1i3－2－4長度為長度為8但實際路徑為但實際路徑為1―2―4長度為長度為5；所以貪心算法不總能得到整體的最優(yōu)解，但它們還是最優(yōu)解的最好近似；所以貪心算法不總能得到整體的最優(yōu)解，但它們還是最優(yōu)解的最好近似；2請用分治法設(shè)計算法：在一個整數(shù)組請用分治法設(shè)計算法：在一個整數(shù)組A[1..n]A[1..n

7、]中，同時尋找最大值和最小值，并分析你中，同時尋找最大值和最小值，并分析你的算法的時間復(fù)雜度。的算法的時間復(fù)雜度。[假設(shè)假設(shè)n為2的方冪的方冪]解答算法：解答算法：MINMAX輸入：入：n個整數(shù)元素的數(shù)個整數(shù)元素的數(shù)組A[1..n]n為2的方的方冪。輸出：(xy)，A中的最大元素和最小元素。中的最大元素和最小元素。過程Min_Max(lowhigh)ifhighlow=1thenifA[low]A[high]thenreturn(A[l

8、ow]A[high])elsereturn(A[high]A[low])endif.else=?(lowhigh)2?(x1y1)=Min_Max(low)(x2y2)=Min_Max(1high)x=min(x1x2)y=max(y1y2)return(xy)endif該算法的復(fù)雜度分析：該算法的復(fù)雜度分析：設(shè)C(n)表示算法在由表示算法在由n個元素組成的數(shù)組上執(zhí)行的元素比較次數(shù)，則可得到算法所作個元素組成的數(shù)組上執(zhí)行的元素比較次數(shù)，