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

1、計(jì)算機(jī)算法設(shè)計(jì)與分析復(fù)習(xí)題、填空題1、一個(gè)算法復(fù)雜性的咼低體現(xiàn)在計(jì)算機(jī)運(yùn)行該算法所需的時(shí)間和存儲(chǔ)器資源上，因此算法的復(fù)雜性有一時(shí)間 _ 復(fù)雜性和空間復(fù)雜性之分。2、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時(shí)，這些子問題的規(guī)模都大致 _ 相同_。3、 使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素，在最佳情況下，搜索的 時(shí)間復(fù)雜性為0( 1)，在最壞情況下，搜索的時(shí)間復(fù)雜性為O(ogn_)4、已知一個(gè)分治算法耗費(fèi)的計(jì)算時(shí)間T(n)，T(n)滿足如下遞歸方程：解得此遞歸方可得T(n)= 0 (_nlogn_)。5、 動(dòng)態(tài)規(guī)劃算法有一個(gè)變形方法_備忘錄方法_ 。這種方法

2、不同于動(dòng)態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，同樣也可避免相同子問題的重復(fù)求解。6. _遞歸的二分查找算法在divide階段所花的時(shí)間是0(1)_，conquer階段所花的時(shí)間是T(n/2)，算法的時(shí)間復(fù)雜度是0( log n) _。7 . Prim算法利用貪心 策略求解 最小牛成樹冋題，其時(shí)間復(fù)雜度是0(。8、 背包問題可用 貪心法:回溯法等策略求解。9、 用動(dòng)態(tài)規(guī)劃算法計(jì)算矩陣連乘問題的最優(yōu)值所花的時(shí)間是一0(n3,子冋題空間大小是0( n2)。10、 圖的m著色問題可用 回遡法求解，其解空間樹中葉子結(jié)點(diǎn)個(gè)數(shù)是m2，解空

3、間樹中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是一 _。11、 單源最短路徑問題可用貪心法、一分支限界等策略求解。12、 一個(gè)算法的優(yōu)劣可以用(時(shí)間復(fù)雜度)與(空間復(fù)雜度)與來衡量。13、 回溯法在問題的解空間中，按(深度優(yōu)先方式)從根結(jié)點(diǎn)出發(fā)搜索解空間樹。14、 直接或間接地調(diào)用自身的算法稱為(遞歸算法)。15、 二記號(hào)在算法復(fù)雜性的表示法中表示(漸進(jìn)確界或緊致界)。T(n)*0( 1)2T( n/ 2)+0( n)n : 216、 在分治法中，使子問題規(guī)模大致相等的做法是出自一種(平衡(banlancing)子問題)的思想。17、 動(dòng)態(tài)規(guī)劃算法適用于解(具有某種最優(yōu)性質(zhì))問題。18、 貪心算法做出的選擇只是(在

4、某種意義上的局部)最優(yōu)選擇。19、 最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是(問題的最優(yōu)解包含其子問題的最優(yōu)解)20、回溯法按（ 深度優(yōu)先 ）策略從根結(jié)點(diǎn)出發(fā)搜索解空間樹。21、拉斯維加斯算法找到的解一定是（ 正確解 ）。22、按照符號(hào)O的定義O（f）+O（g） 等于O（maxf（n）,g（n） 。23、二分搜索技術(shù)是運(yùn)用（ 分治 ）策略的典型例子。24、動(dòng)態(tài)規(guī)劃算法中，通常不同子問題的個(gè)數(shù)隨問題規(guī)模呈（多項(xiàng)式 ）級(jí)增長(zhǎng)。25、（最優(yōu)子結(jié)構(gòu)性質(zhì) ）和（ 子問題重疊性質(zhì) ）是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本 要 素。26、（最優(yōu)子結(jié)構(gòu)性質(zhì) ）和（ 貪心選擇性質(zhì) ）是貪心算法的基本要素。27、（選擇能產(chǎn)生最優(yōu)解的貪心準(zhǔn)則

5、 ）是設(shè)計(jì)貪心算法的核心問題。28、分支限界法常以（ 廣度優(yōu)先 ） 或（以最小耗費(fèi) （最大效益 ）優(yōu)先）的方式搜 索 問題的解空間樹。29、貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列（局部最優(yōu) ）的選 擇，即貪心選擇達(dá)到。30、 按照活結(jié)點(diǎn)表的組織方式的不同，分支限界法包括（隊(duì)列式 （FIFO）分支限界 法） 和（ 優(yōu)先隊(duì)列式分支限界法 ）兩種形式。31、 如果對(duì)于同一實(shí)例， 蒙特卡洛算法不會(huì)給出兩個(gè)不同的正確解答， 則稱該蒙 特卡 洛算法是（ 一致的 ）。32、 哈夫曼編碼可利用（ 貪心法 ）算法實(shí)現(xiàn)。33概率算法有 數(shù)值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（

6、Las Vegas）算法和舍伍德（Sherwood） 算法34以自頂向下的方式求解最優(yōu)解的有（ 貪心算法 ）35、 下列算法中通常以自頂向下的方式求解最優(yōu)解的是（貪心法）。36、 在對(duì)問題的解空間樹進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn) 的是 （ 回溯法）37、 旅行售貨員問題不能用（）解決可以用回溯法解決，分支限界法，NP完 全性理論與近似算法38、 貪心算法不能解決（0-1背包問題N皇后問題 ）?？梢越鉀Q背包問題39、 投點(diǎn)法是（ 概率算法）的一種。40、 若線性規(guī)劃問題存在最優(yōu)解，它一定不在（ 可行域內(nèi)部 ）、簡(jiǎn)答題1、（8分）寫出下列復(fù)雜性函數(shù)的偏序關(guān)系（即按照漸進(jìn)階從低到高

7、排序）2n3nlog n n! nlog n n2nn103參考解答：103丫log n丫n log n丫n2丫2n丫3n n! nn2、(8分)現(xiàn)在有8位運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽，要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n - 1天。請(qǐng)利用分治法的思想，給這8位運(yùn)動(dòng)員設(shè)計(jì)一個(gè)合理的比賽日程。參考解答：3 8分)某體育館有一羽毛球場(chǎng)出和，現(xiàn)在總具有10位客戶屮諳和用此羽毛 球場(chǎng)，每個(gè)客戶所租用的時(shí)間單元如下表所示,s(i)表示開始租用時(shí)刻,f(i)表示結(jié)束租用時(shí)刻，10個(gè)客戶的申請(qǐng)如下表所示 i123456789

8、10s(i)03153511886f(i)65498713121110同一時(shí)刻，該羽毛球場(chǎng)只能租借給一位客戶，請(qǐng)?jiān)O(shè)計(jì)一個(gè)租用安排方案，在 這10位客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針對(duì)上表的10個(gè)客戶申請(qǐng)，最多可以安排幾位客戶申請(qǐng)。參考解答：將這10位客戶的申請(qǐng)按照結(jié)束時(shí)間f(i)遞增排序，如下表： i12345678910s(i(i)45678910111213選擇申請(qǐng)1 (1,4 )依次檢查后續(xù)客戶申請(qǐng)，只要與已選擇的申請(qǐng)相容不沖突，則選擇該申請(qǐng)。直到所有申請(qǐng)檢查完畢。申請(qǐng)4 (5,7 )、申請(qǐng)8 (8,11 )、申請(qǐng)10 (11,13)最后，

9、可以滿足：申請(qǐng)1 (1,4 )、申請(qǐng)4(5,7 )、申請(qǐng)8(8,11 )、申請(qǐng)10( 11,13)共4個(gè)客戶申請(qǐng)。這已經(jīng)是可以滿足的最大客戶人數(shù)4、（8分）對(duì)于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為p為矩陣Ai的列?，F(xiàn)有四個(gè)矩陣，其中各矩陣維數(shù)分別為A1A2AA50 x1010漢4040 x3030漢5P0漢P1P1匯P2P2漢P3P3代P4請(qǐng)根據(jù)以上的遞歸關(guān)系，計(jì)算出矩陣連乘積A AAA所需要的最少數(shù)乘次數(shù)。參考解答：r m11 + m24 + PoPQq=0+8000 + 50乂乂10八八5 = 10500m14 = min m12 m34 P。P2P4二20000 6000 50

10、40 5 = 36000m13 m44 + P。psp4= 27000 + 0十50匯30漢5 = 34500 -105005、 （8分）有這樣一類特殊0-1背包問題：可選物品 重量越輕的物品價(jià)值越高。n=6, c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個(gè)數(shù)，c為背包載重量，P表示物品的價(jià)值，W表示物品的重 量。請(qǐng) 問對(duì)于此0-1背包問題，應(yīng)如何選擇放進(jìn)去的物品，才能使到放進(jìn)背包的物品總價(jià)值最大，能獲得的最大總價(jià)值多少？參考解答：因?yàn)樵?-1背包問題比較特殊，恰好重量越輕的物品價(jià)值越高，所以優(yōu)先取重量輕的物品放進(jìn)背包。最終可以把重量分別為2, 3

11、, 4, 5的三個(gè)物品放進(jìn)背包，得到的價(jià)值和為15 + 8 + 6 + 4 = 33，為最大值。6請(qǐng)用英文寫出三種以上能求解0-1背包問題的設(shè)計(jì)算法策略。 參考解答：Dyn amic Programmi ngBacktrackBran ch-a n d-Bo und（每答對(duì)一條給一分）7請(qǐng)說明動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。.Imi,jn0mkinmi,k mk 1, j pAPkPj其中mi,j為計(jì)算矩陣連乘Ai, Aj所需的最少數(shù)乘次數(shù)i= ji:jPi-i為矩陣Ai的行,參考解答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是自底向上計(jì)算各個(gè)子問題的最優(yōu)解，即先

12、計(jì)算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu)8請(qǐng)說明：（1）優(yōu)先隊(duì)列可用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)？（2）優(yōu)先隊(duì)列插入算法基本思 想?（3）優(yōu)先隊(duì)列插入算法時(shí)間復(fù)雜度？參考解答：（1）堆。（1分）（2）在小根堆中，將元素x插入到堆的末尾， 然后將元素x的關(guān)鍵字與其雙親的關(guān)鍵字比較， 若元素x的關(guān)鍵字小于其雙親的關(guān)鍵字，則將元素x與其雙親交換，然后再將元素x與其新雙親的關(guān)鍵字相比，直到元素x的關(guān)鍵字大于雙親的關(guān)鍵字，或元素x到根為止。（4分）（3）0（log n）（1分）9.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟是怎么的？請(qǐng)簡(jiǎn)述。參考解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征

13、。（6分）（2） 遞歸地定義最優(yōu)值。（3） 以自底向上的方式計(jì)算出最優(yōu)值。（4） 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。10.分治法所能解決的問題一般具有哪幾個(gè)特征？請(qǐng)簡(jiǎn)述。參考解答：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（6分）（2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；（3）禾U用該問題分解出的子問題的解可以合并為該問題的解；（4）原問題所分解出的各個(gè)子問題是相互獨(dú)立的， 即子問題之間不包 含 公共的子問題。11.分支限界法的搜索策略是什么？ 參考解答：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再從當(dāng)前的 活結(jié)點(diǎn) 表中選擇下一個(gè)擴(kuò)展結(jié)

14、點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加速搜索的進(jìn) 程，在每一個(gè) 活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界），并根據(jù)函數(shù)值，從當(dāng)前活結(jié) 點(diǎn)表中選擇一個(gè)最有 利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)， 使搜索朝著解空間上有最優(yōu)解的分 支推進(jìn)， 以便盡快地找出一 個(gè)最優(yōu)解。（6分）12算法的要特性是什么？ 參考解答：確定性、可實(shí)現(xiàn)性、輸入、輸出、有窮性13算法分析的目的是什么？ 參考解答：分析算法占用計(jì)算機(jī)資源的情況，對(duì)算法做出比較和評(píng)價(jià)，設(shè)計(jì)出額 更好的 算法。14算法的時(shí)間復(fù)雜性與問題的什么因素相關(guān)？參考解答：算法的時(shí)間復(fù)雜性與問題的規(guī)模相關(guān)，是問題大小n的函數(shù)。15算法的漸進(jìn)時(shí)間復(fù)雜性的含義？參考解答：當(dāng)問題的規(guī)模n趨向無窮大

15、時(shí)，影響算法效率的重要因素是T（n）的數(shù)量級(jí)，而其他因素僅是使時(shí)間復(fù)雜度相差常數(shù)倍，因此可以用T（n）的數(shù)量級(jí)（階）評(píng)價(jià)算法。時(shí)間復(fù)雜度T（n）的數(shù)量級(jí)（階）稱為漸進(jìn)時(shí)間復(fù)雜性。16最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性有什么不同？ 參考解答：最壞情況下的時(shí) 間復(fù)雜性和平均時(shí)間復(fù)雜性考察的是n固定時(shí)，不同 輸入實(shí)例下的算法所耗時(shí)間。 最壞 情況下的時(shí)間復(fù)雜性取的輸入實(shí)例中最大的時(shí) 間復(fù)雜度：W(n) = max T(n , I) , I ? Dn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概 率的乘積和：A(n)=刀P(l)T(n ,1) I ? Dn17簡(jiǎn)述二分檢索(折半查找)算法的基本過程

16、。參考解答：設(shè)輸入是一個(gè)按非降次序排列的元素表Ai : j和x,選取A(i+j)/2與x比較，如果A(i+j)/2=x，則返回(i+j)/2，如果A(i+j)/2x，則Ai :(i+j)/2-1找x，否則在A (i+j)/2+1: j找x。上述過程被反復(fù)遞歸調(diào)用。18背包問題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎？參考解答:不相同。目標(biāo)函數(shù):獲得最大利潤。最優(yōu)量度:最大利潤/重量比。19采用回溯法求解的問題，其解如何表示？有什么規(guī)定？參考解答：?jiǎn)栴}的解可以表示為n元組：(xi,x2, , xJ,Xi? S, S為有窮集合，Xi? S,(Xi,X2, , Xn)具備完備性，即(Xi,X2, , X

17、n)是合理的，貝(X, Xi)( (心心) )一定合理。20回溯法的搜索特點(diǎn)是什么？參考解答： 在解空間樹上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取 值，如果xk是合理的就搜索xk為根節(jié)點(diǎn)的子樹， 如果xk取完了所有的值， 便回溯到xk-1。21 n皇后問題回溯算法的判別函數(shù)place的基本流程是什么？參考解答：將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如 果不相 容就返回false，測(cè)試完畢則返回true。22為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用？參考解答： 子問題的規(guī)模還很大時(shí)，必須繼續(xù)使用分治法，反復(fù)分治，必然要用 到遞 歸.23為什么要分析最壞情況下的算法時(shí)間

18、復(fù)雜性？參考解答： 最壞情況下的時(shí)間復(fù)雜性決定算法的優(yōu)劣， 并且最壞情況下的時(shí)間復(fù) 雜性 較平均時(shí)間復(fù)雜性游可操作性。24簡(jiǎn)述漸進(jìn)時(shí)間復(fù)雜性上界的定義。參考解答：T(n)是某算法的時(shí)間復(fù)雜性函數(shù)，f(n)是一簡(jiǎn)單函數(shù)，存在正整數(shù)No和C, nNo,有T(n)vf(n)，這種關(guān)系記作T(n)=O(f(n)。25二分檢索算法最多的比較次數(shù)？參考解答： 二分檢索算法的最多的比較次數(shù)為log n。26快速排序算法最壞情況下需要多少次比較運(yùn)算？參考解答：最壞情況下快速排序退化成冒泡排序，需要比較n2次。27貪心算法的基本思想？參考解答： 是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級(jí)處理方法?；舅悸肥牵菏紫雀?/p>

19、據(jù)題意，選取一種量度標(biāo)準(zhǔn)；然后按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序，依 次選擇輸入量加入部分解中。 如果當(dāng)前這個(gè)輸入量的加入， 不滿足約束條件， 則 不把此輸入 加到這部分解中28回溯法的解(Xi,X2,Xn)的隱約束一般指什么？參考解答：回溯法的解(X1,X2, , Xn)的隱約束一般指?jìng)€(gè)元素之間應(yīng)滿足的某 種關(guān)系。29闡述歸并排序的分治思路。參考解答： 講數(shù)組一分為二， 分別對(duì)每個(gè)集合單獨(dú)排序， 然后將已排序的兩個(gè)序 列歸 并成一個(gè)含n個(gè)元素的分好類的序列。 如果分割后子問題還很大， 則繼續(xù)分 治，直到 一個(gè)元素。30快速排序的基本思想是什么。參考解答：快速排序的基本思想是在待排序的N個(gè)記錄中任

20、意取一個(gè)記錄，把該 記錄放 在最終位置后， 數(shù)據(jù)序列被此記錄分成兩部分。 所有關(guān)鍵字比該記錄關(guān)鍵 字小的放在 前一部分， 所有比它大的放置在后一部分， 并把該記錄排在這兩部分 的中間，這個(gè)過 程稱作一次快速排序。 之后重復(fù)上述過程， 直到每一部分內(nèi)只有 一個(gè)記錄為止。31什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？參考解答： 在定義一個(gè)過程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成 分，既調(diào) 用它自己本身， 這稱為直接遞歸。 如果過程或者函數(shù)P調(diào)用過程或者函 數(shù)Q, Q又調(diào) 用P,這個(gè)稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。32什么是哈密頓環(huán)問題？參考解答：哈密頓環(huán)是指

21、一條沿著圖G的N條邊環(huán)行的路徑，它的訪問每個(gè)節(jié)點(diǎn) 一次并且返回它的開始位置。33用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？參考解答：當(dāng)前選擇的節(jié)點(diǎn)Xk是從未到過的節(jié)點(diǎn),即Xk工Xi(i=1,2, ,k-1)，且C(Xk-1, Xk)工A，如果k=-1，貝UC(Xk, X1)34請(qǐng)寫出prim算法的基本思想。參考解答： 思路是：最初生成樹T為空，依次向內(nèi)加入與樹有最小鄰接邊的n-1條邊。處理過程：首先加入最小代價(jià)的一條邊到T,根據(jù)各節(jié)點(diǎn)到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇 下一條 邊加入，直至加入n-1條邊。三、算法設(shè)計(jì)題1.【最長(zhǎng)上升子序列問題】(

22、 8分)一一提示：此題可采用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)對(duì)于給定的一個(gè)序列，仁N叮000。我們可以得到一些遞增上升的子序列(不忌,川,無)，這里1 iAiA|iAN。比如，對(duì)于序列(1, 7, 3, 5, 9, 4, 8)，有 它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長(zhǎng)的長(zhǎng)度是4,比如子序列(1, 3, 5, 8)。你的任務(wù)：就是對(duì)于給定的序列，求出最長(zhǎng)上升子序列的長(zhǎng)度。要求寫出你設(shè)計(jì)的算法思想及遞推函數(shù)的公式表達(dá)。.參考解答：設(shè)f(i)表示：從左向右掃描過來直到以ai元素結(jié)尾的序列，獲得的最長(zhǎng)上升子序列的長(zhǎng)度，且子序列包含ai元素(1 n)。r1i = 1f二max

23、f(j) 1:當(dāng)ai ? a j;1乞j: :i i 1 1 i 1;j(仁j:i ),都有aiaj即，f(i)是從f(1)，f(2),至U f(i -1)中找最大的一個(gè)值，再加1。或者 就是1。主要是 看ai這個(gè)元素能否加入到之前已經(jīng)獲得的最長(zhǎng)上升子序列，如果能加入，是之前已獲得的最長(zhǎng)上升子序列長(zhǎng)度加一；如果不能加入，就取這最后一個(gè)元素作為一個(gè)單獨(dú)子序列，長(zhǎng)度為1。最后，所要求的整個(gè)序列的最長(zhǎng)公共子序列長(zhǎng)度為maxf(i): 1=i=當(dāng)前最優(yōu)解代價(jià)bestf，則剪枝。2分(3)見(1)中所畫的圖。5分(4)最優(yōu)解為3,1,2，最優(yōu)值為25。3分4.【Gray碼構(gòu)造問題】(8分)一一提示：此題

24、可采用分治遞歸算法實(shí)現(xiàn) 問題描述：格雷碼是一個(gè)長(zhǎng)度為2n的序列，滿足：(a)每個(gè)元素都是長(zhǎng)度為n比特的串(b)序列中無相同元素(c)連續(xù)的兩個(gè)元素恰好只有1個(gè)比特不同 例如：n=2時(shí)，格雷碼為00, 01,11,10。Gray碼是一種編碼，這種編碼可以避免在讀取時(shí)，因各數(shù)據(jù)位時(shí)序上的差異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運(yùn)算，請(qǐng)你設(shè)計(jì)種構(gòu)造方法，輸入長(zhǎng)度序列n,輸出格雷碼(你只要做出一種構(gòu)造方案即可，格雷碼并不唯一)。參考解答：此題可用分治法解決。當(dāng)1時(shí)，輸出格雷碼0, 1當(dāng)n1時(shí)，格雷碼的長(zhǎng)度為2n，即共有2n個(gè)碼序列。此時(shí)，將問題一分為 二，即上 半部分和下半部分。上半部

25、分最高位設(shè)為0,下半部分最高位設(shè)為1剩下n-1位的格雷碼 的構(gòu)造采用遞歸的思路。評(píng)分準(zhǔn)則：1)答到使用分治算法，并且推導(dǎo)出分治算法的過程，邊界設(shè)定清晰(即當(dāng) 僅輸出1位的格雷碼如何處理)，本題即可得滿分；11421810169 232 1 1 2333330253626X2)說明使用分治算法，但漏邊界條件，扣2分以上；實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和?，F(xiàn)采用Dijkstra算法計(jì) 算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將此過程填入下表中。迭代Sudist2dist 3dist4dist 5初始11234參考解答：

26、（13分）迭代Sudist2dist 3dist4dist 5初始1-103010011 , 2210603010021 , 2, 441050309031 , 2, 4, 331050306041 , 2, 3, 4, 55105030606.（13分）有0-1背包問題如下：n=6, c=20, P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個(gè)數(shù)，c為背包載重量，P表示物品的價(jià)值，W表示物品的 重量。 請(qǐng)問對(duì)于此0-1背包問題，應(yīng)如何選擇放進(jìn)去的物品，才能使到 放進(jìn)背包的物品 總價(jià)值最大。P=（15, 8, 6, 4, 3，1）W=（2，3, 4, 5, 8，10），單位重量物品價(jià)值（7.5 , 2.67, 1.5,0.8,0.375,0.1）10100其它情況酌情考慮5.（13分）給定帶權(quán)有向圖（如下圖所示）G =（V,E），其中每條邊的權(quán)是非負(fù)參考解答：（13分）可知隨著物品的重量增加，物品的價(jià)值減少；因此可以用貪心算法來求解。以選取單位重量物品價(jià)值高為貪心策略。1.先把重量