算法設(shè)計(jì)與分析復(fù)習(xí)考試exam

1、一、 （20）判斷請(qǐng)?jiān)谡_的陳述前面括號(hào)中打，在錯(cuò)誤的陳述前面括號(hào)中F）回溯法用深度優(yōu)先或廣度優(yōu)先法搜索狀態(tài)空間樹(shù)（ T）O(f(n)+O(g(n) = （F）f(n)=（F）已知團(tuán)問(wèn)題（Cliqueproblem）為NP題，那么下列問(wèn)題是一個(gè)判定問(wèn)題：給定一個(gè)圖 G，求G 中最大團(tuán)的尺寸（size）K。（F）隨機(jī)化快速排序的worstcase現(xiàn)于輸入數(shù)組恰好為已按非（T）基于比較的排序問(wèn)題的下界是(nlogn（ F）所有問(wèn)題當(dāng)中最難的一組問(wèn)題被稱為NP 完備 （F）P和NP問(wèn)題的關(guān)系用PNP來(lái)表示是錯(cuò)誤T）動(dòng)態(tài)規(guī)劃算法通過(guò)增加空間復(fù)雜性來(lái)降低時(shí)間復(fù)雜性二、 （30）簡(jiǎn)答題當(dāng)n3求解 TSP

2、問(wèn)題的最近鄰居算法的性能比是多少？這一性能比是請(qǐng)給出基于比較的尋找數(shù)組A1n中最大和最小元素問(wèn)題的最緊的下界，并說(shuō)明這個(gè)下界是用了課上介紹的哪種或哪幾種尋找3n/2-函數(shù)f(n)跟在g(n)的后面則說(shuō)明應(yīng)該滿足g(n)是（f(n)：f (n) 10nf (n) n1/3 f (n) nnf4 (n) 2 logc nf5 (n) log策略和樹(shù)中各節(jié)點(diǎn)代表的狀態(tài)（化簡(jiǎn)的 CNF 形式。 三、 （15）設(shè)計(jì)一求解以下問(wèn)題的分治算法，寫(xiě)出偽代碼，分去的某天開(kāi)始對(duì)一支給定的連續(xù) n天（這些天數(shù)記為 i 1,2,.n 對(duì)每天 i，有當(dāng)天這只每股的價(jià)格 p(i)（為簡(jiǎn)單起見(jiàn)，假設(shè)這個(gè)價(jià)格在每一天之內(nèi)是固

3、定的。 假設(shè)在這 n 天內(nèi)，舉例說(shuō)，假設(shè) n=4，p(1)=4，p(2)=1，p(3)=1.5，p(4)=3，那么你的算法應(yīng)該返回“24（在第2天買(mǎi)并且在第4天賣(mài)意味著每股將掙 2 ，是這個(gè)期間最大的收益。 四、 （15 分）寫(xiě)出用動(dòng)態(tài)規(guī)劃方法求兩個(gè)序列的最長(zhǎng)公共子序列下A 和B 的最長(zhǎng)公共子序列：五、 （15 分）設(shè)計(jì)一求解以下問(wèn)題的貪心算法，寫(xiě)出偽代碼，并給定m臺(tái)機(jī)器M1 M 2 Mm 和n項(xiàng)作業(yè)，要把每一項(xiàng)作配給一臺(tái)機(jī)器來(lái)完每一項(xiàng)作業(yè) j有處理時(shí)間t j . 若 A(i)表示分配給機(jī)Mi的作業(yè)集，則Mi需要工作的總時(shí)間（亦稱Mi的負(fù)載）為T(mén)i t 完成n項(xiàng)作業(yè)的工期T為所有機(jī)器的最大負(fù)載，即 T maxi要求找到一種分配方案，使得完成這 n 項(xiàng)作業(yè)的工期例如，下圖即為將處理時(shí)間分別為 2，3，7，4，2，2 的六項(xiàng)作業(yè)分配給三臺(tái)機(jī)器的一種分配方案，其中M 1 的負(fù)載最大，為 9，則該方案完成這六項(xiàng)作業(yè)的工期為 9。273273242對(duì)各作業(yè)處理時(shí)間進(jìn)行排序，安排時(shí)間最長(zhǎng)的作業(yè)先執(zhí)行。時(shí)間復(fù)雜度為O（nlogn。六、