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

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

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

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

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

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

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

7、]中，同時(shí)尋找最大值和最小值，并分析你中，同時(shí)尋找最大值和最小值，并分析你的算法的時(shí)間復(fù)雜度。的算法的時(shí)間復(fù)雜度。[假設(shè)假設(shè)n為2的方冪的方冪]解答算法：解答算法：MINMAX輸入：入：n個(gè)整數(shù)元素的數(shù)個(gè)整數(shù)元素的數(shù)組A[1..n]n為2的方的方冪。輸出：(xy)，A中的最大元素和最小元素。中的最大元素和最小元素。過(guò)程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個(gè)元素組成的數(shù)組上執(zhí)行的元素比較次數(shù)，則可得到算法所作個(gè)元素組成的數(shù)組上執(zhí)行的元素比較次數(shù)，