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

精品文檔計(jì)算機(jī)算法設(shè)計(jì)與分析復(fù)習(xí)題一、填空題1、一個(gè)算法復(fù)雜性的高低體現(xiàn)在計(jì)算機(jī)運(yùn)行該算法所需的時(shí)間和存儲(chǔ)器資源上，因此算法的復(fù)雜性有 時(shí)間 復(fù)雜性和空間復(fù)雜性之分。2、出自于“平衡子問(wèn)題”的思想，通常分治法在分割原問(wèn)題，形成若干子問(wèn)題時(shí)，這些子問(wèn)題的規(guī)模都大致 相同 。3、使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素，在最佳情況下，搜索的時(shí)間復(fù)雜性為O（1），在最壞情況下，搜索的時(shí)間復(fù)雜性為O（ logn ）。4、已知一個(gè)分治算法耗費(fèi)的計(jì)算時(shí)間T(n)，T(n)滿足如下遞歸方程：解得此遞歸方可得T(n)= O（ ）。5、動(dòng)態(tài)規(guī)劃算法有一個(gè)變形方法 備忘錄方法 。這種方法不同于動(dòng)態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，同樣也可避免相同子問(wèn)題的重復(fù)求解。6遞歸的二分查找算法在divide階段所花的時(shí)間是 O(1) ，conquer階段所花的時(shí)間是 T(n/2) ，算法的時(shí)間復(fù)雜度是 O( log n) 。 7Prim算法利用貪心 策略求解 最小生成樹(shù)問(wèn)題，其時(shí)間復(fù)雜度是 O(n2) 。8背包問(wèn)題可用 貪心法 ， 回溯法 等策略求解。9用動(dòng)態(tài)規(guī)劃算法計(jì)算矩陣連乘問(wèn)題的最優(yōu)值所花的時(shí)間是 O(n3) ， 子問(wèn)題空間大小是 O(n2) 。10圖的m著色問(wèn)題可用 回溯 法求解，其解空間樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)是 mn ，解空間樹(shù)中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是 m 。11單源最短路徑問(wèn)題可用貪心法 、 分支限界 等策略求解。12、一個(gè)算法的優(yōu)劣可以用（時(shí)間復(fù)雜度）與（空間復(fù)雜度）與來(lái)衡量。13、回溯法在問(wèn)題的解空間中，按（深度優(yōu)先方式）從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。14、直接或間接地調(diào)用自身的算法稱(chēng)為（遞歸算法）。15、q 記號(hào)在算法復(fù)雜性的表示法中表示（漸進(jìn)確界或緊致界）。16、在分治法中，使子問(wèn)題規(guī)模大致相等的做法是出自一種（平衡(banlancing)子問(wèn)題）的思想。17、動(dòng)態(tài)規(guī)劃算法適用于解（具有某種最優(yōu)性質(zhì)）問(wèn)題。18、貪心算法做出的選擇只是（在某種意義上的局部）最優(yōu)選擇。19、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是（問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解）。20、回溯法按（深度優(yōu)先）策略從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。21、拉斯維加斯算法找到的解一定是（正確解）。22、按照符號(hào)O的定義O(f)+O(g)等于O(maxf(n),g(n)。23、二分搜索技術(shù)是運(yùn)用（分治）策略的典型例子。24、動(dòng)態(tài)規(guī)劃算法中，通常不同子問(wèn)題的個(gè)數(shù)隨問(wèn)題規(guī)模呈（多項(xiàng)式）級(jí)增長(zhǎng)。25、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（子問(wèn)題重疊性質(zhì)）是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。26、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（貪心選擇性質(zhì)）是貪心算法的基本要素。27、（選擇能產(chǎn)生最優(yōu)解的貪心準(zhǔn)則）是設(shè)計(jì)貪心算法的核心問(wèn)題。28、分支限界法常以（廣度優(yōu)先） 或（以最小耗費(fèi)(最大效益)優(yōu)先）的方式搜索問(wèn)題的解空間樹(shù)。29、貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列（局部最優(yōu)）的選擇，即貪心選擇達(dá)到。30、按照活結(jié)點(diǎn)表的組織方式的不同，分支限界法包括（隊(duì)列式(FIFO)分支限界法）和（優(yōu)先隊(duì)列式分支限界法）兩種形式。31、如果對(duì)于同一實(shí)例，蒙特卡洛算法不會(huì)給出兩個(gè)不同的正確解答，則稱(chēng)該蒙特卡洛算法是（一致的）。32、哈夫曼編碼可利用（貪心法）算法實(shí)現(xiàn)。33概率算法有數(shù)值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法34以自頂向下的方式求解最優(yōu)解的有（貪心算法）35、下列算法中通常以自頂向下的方式求解最優(yōu)解的是（貪心法）。 36、在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)的是（回溯法）37、旅行售貨員問(wèn)題不能用（）解決 可以用回溯法解決，分支限界法，NP完全性理論與近似算法38、貪心算法不能解決（0-1背包問(wèn)題 N皇后問(wèn)題）?？梢越鉀Q背包問(wèn)題39、投點(diǎn)法是（概率算法）的一種。40、若線性規(guī)劃問(wèn)題存在最優(yōu)解，它一定不在（可行域內(nèi)部）二、簡(jiǎn)答題1、（8分）寫(xiě)出下列復(fù)雜性函數(shù)的偏序關(guān)系（即按照漸進(jìn)階從低到高排序）：參考解答：2、（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è)合理的比賽日程。參考解答：12345678214365873412785643218765567812346587214378563412876543213、（8分）某體育館有一羽毛球場(chǎng)出租，現(xiàn)在總共有10位客戶(hù)申請(qǐng)租用此羽毛球場(chǎng)，每個(gè)客戶(hù)所租用的時(shí)間單元如下表所示，s(i)表示開(kāi)始租用時(shí)刻，f(i)表示結(jié)束租用時(shí)刻，10個(gè)客戶(hù)的申請(qǐng)如下表所示：i12345678910s(i)03153511886f(i)65498713121110同一時(shí)刻，該羽毛球場(chǎng)只能租借給一位客戶(hù)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)租用安排方案，在這10位客戶(hù)里面，使得體育館能盡可能滿足多位客戶(hù)的需求，并算出針對(duì)上表的10個(gè)客戶(hù)申請(qǐng)，最多可以安排幾位客戶(hù)申請(qǐng)。參考解答：將這10位客戶(hù)的申請(qǐng)按照結(jié)束時(shí)間f(i)遞增排序，如下表：i12345678910s(i(i)45678910111213選擇申請(qǐng)1（1,4）依次檢查后續(xù)客戶(hù)申請(qǐng)，只要與已選擇的申請(qǐng)相容不沖突，則選擇該申請(qǐng)。直到所有申請(qǐng)檢查完畢。申請(qǐng)4（5,7）、申請(qǐng)8（8,11）、申請(qǐng)10（11,13）最后，可以滿足：申請(qǐng)1（1,4）、申請(qǐng)4（5,7）、申請(qǐng)8（8,11）、申請(qǐng)10（11,13）共4個(gè)客戶(hù)申請(qǐng)。這已經(jīng)是可以滿足的最大客戶(hù)人數(shù)。4、（8分）對(duì)于矩陣連乘所需最少數(shù)乘次數(shù)問(wèn)題，其遞歸關(guān)系式為：其中mi，j為計(jì)算矩陣連乘AiAj所需的最少數(shù)乘次數(shù)，pi-1為矩陣Ai的行，為矩陣Ai的列?，F(xiàn)有四個(gè)矩陣，其中各矩陣維數(shù)分別為：A1A2A3A4501010404030305p 0 p 1p 1 p 2p 2 p 3p 3 p 4請(qǐng)根據(jù)以上的遞歸關(guān)系，計(jì)算出矩陣連乘積A1A2A3A4所需要的最少數(shù)乘次數(shù)。參考解答：5、（8分）有這樣一類(lèi)特殊0-1背包問(wèn)題：可選物品重量越輕的物品價(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)問(wèn)對(duì)于此0-1背包問(wèn)題，應(yīng)如何選擇放進(jìn)去的物品，才能使到放進(jìn)背包的物品總價(jià)值最大，能獲得的最大總價(jià)值多少？參考解答：因?yàn)樵?1背包問(wèn)題比較特殊，恰好重量越輕的物品價(jià)值越高，所以?xún)?yōu)先取重量輕的物品放進(jìn)背包。最終可以把重量分別為2，3，4，5的三個(gè)物品放進(jìn)背包，得到的價(jià)值和為15 + 8 + 6 + 4 = 33，為最大值。6.請(qǐng)用英文寫(xiě)出三種以上能求解0-1背包問(wèn)題的設(shè)計(jì)算法策略。參考解答：Dynamic Programming Backtrack Branch-and-Bound （每答對(duì)一條給一分）7.請(qǐng)說(shuō)明動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。參考解答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是自底向上計(jì)算各個(gè)子問(wèn)題的最優(yōu)解，即先計(jì)算子問(wèn)題的最優(yōu)解，然后再利用子問(wèn)題的最優(yōu)解構(gòu)造大問(wèn)題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu)8.請(qǐng)說(shuō)明：(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）O( log n)（1分）9.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟是怎么的？請(qǐng)簡(jiǎn)述。參考解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(6分) （2）遞歸地定義最優(yōu)值。 （3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。10.分治法所能解決的問(wèn)題一般具有哪幾個(gè)特征？請(qǐng)簡(jiǎn)述。參考解答：（1）該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；(6分) （2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì);（3） 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解； （4）原問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。11.分支限界法的搜索策略是什么？參考解答：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(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ù)雜性與問(wèn)題的什么因素相關(guān)？參考解答：算法的時(shí)間復(fù)雜性與問(wèn)題的規(guī)模相關(guān)，是問(wèn)題大小n的函數(shù)。15 算法的漸進(jìn)時(shí)間復(fù)雜性的含義？參考解答：當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，影響算法效率的重要因素是T(n)的數(shù)量級(jí)，而其他因素僅是使時(shí)間復(fù)雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(jí)(階)評(píng)價(jià)算法。時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱(chēng)為漸進(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) , IDn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概率的乘積和：A(n) =P(I)T(n，I) IDn17 簡(jiǎn)述二分檢索（折半查找）算法的基本過(guò)程。參考解答：設(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。上述過(guò)程被反復(fù)遞歸調(diào)用。18 背包問(wèn)題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎？參考解答：不相同。目標(biāo)函數(shù)：獲得最大利潤(rùn)。最優(yōu)量度：最大利潤(rùn)/重量比。19 采用回溯法求解的問(wèn)題，其解如何表示？有什么規(guī)定？參考解答：?jiǎn)栴}的解可以表示為n元組：（x1,x2,xn），xiSi, Si為有窮集合，xiSi, （x1,x2,xn）具備完備性，即（x1,x2,xn）是合理的，則（x1,x2,xi）(in)一定合理。20 回溯法的搜索特點(diǎn)是什么？ 參考解答：在解空間樹(shù)上跳躍式地深度優(yōu)先搜索，即用判定函數(shù)考察xk的取值，如果xk是合理的就搜索xk為根節(jié)點(diǎn)的子樹(shù)，如果xk取完了所有的值，便回溯到xk-1。21 n皇后問(wèn)題回溯算法的判別函數(shù)place的基本流程是什么？參考解答：將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，如果不相容就返回false，測(cè)試完畢則返回true。22 為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用？參考解答：子問(wèn)題的規(guī)模還很大時(shí)，必須繼續(xù)使用分治法，反復(fù)分治，必然要用到遞歸.23 為什么要分析最壞情況下的算法時(shí)間復(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)f(n)，這種關(guān)系記作T(n)=O(f(n)。25 二分檢索算法最多的比較次數(shù)？參考解答：二分檢索算法的最多的比較次數(shù)為 log n 。26 快速排序算法最壞情況下需要多少次比較運(yùn)算？參考解答：最壞情況下快速排序退化成冒泡排序，需要比較n2次。27 貪心算法的基本思想？參考解答：是一種依據(jù)最優(yōu)化量度依次選擇輸入的分級(jí)處理方法?；舅悸肥牵菏紫雀鶕?jù)題意，選取一種量度標(biāo)準(zhǔn)；然后按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序，依次選擇輸入量加入部分解中。如果當(dāng)前這個(gè)輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中28 回溯法的解（x1,x2,xn）的隱約束一般指什么？參考解答：回溯法的解（x1,x2,xn）的隱約束一般指?jìng)€(gè)元素之間應(yīng)滿足的某種關(guān)系。29 闡述歸并排序的分治思路。參考解答：講數(shù)組一分為二，分別對(duì)每個(gè)集合單獨(dú)排序，然后將已排序的兩個(gè)序列歸并成一個(gè)含n個(gè)元素的分好類(lèi)的序列。如果分割后子問(wèn)題還很大，則繼續(xù)分治，直到一個(gè)元素。30 快速排序的基本思想是什么。 參考解答：快速排序的基本思想是在待排序的N個(gè)記錄中任意取一個(gè)記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個(gè)過(guò)程稱(chēng)作一次快速排序。之后重復(fù)上述過(guò)程，直到每一部分內(nèi)只有一個(gè)記錄為止。31 什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？參考解答：在定義一個(gè)過(guò)程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過(guò)程或者函數(shù)的成分，既調(diào)用它自己本身，這稱(chēng)為直接遞歸。如果過(guò)程或者函數(shù)P調(diào)用過(guò)程或者函數(shù)Q，Q又調(diào)用P，這個(gè)稱(chēng)為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。32 什么是哈密頓環(huán)問(wèn)題？參考解答：哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑，它的訪問(wèn)每個(gè)節(jié)點(diǎn)一次并且返回它的開(kāi)始位置。33 用回溯法求解哈密頓環(huán)，如何定義判定函數(shù)？參考解答：當(dāng)前選擇的節(jié)點(diǎn)Xk是從未到過(guò)的節(jié)點(diǎn),即XkXi(i=1,2,k-1)，且C(Xk-1, Xk)，如果k=-1，則C(Xk, X1) 。34 請(qǐng)寫(xiě)出prim算法的基本思想。參考解答：思路是：最初生成樹(shù)T為空，依次向內(nèi)加入與樹(shù)有最小鄰接邊的n-1條邊。處理過(guò)程：首先加入最小代價(jià)的一條邊到T，根據(jù)各節(jié)點(diǎn)到T的鄰接邊排序，選擇最小邊加入，新邊加入后，修改由于新邊所改變的鄰接邊排序，再選擇下一條邊加入，直至加入n-1條邊。三、算法設(shè)計(jì)題1.【最長(zhǎng)上升子序列問(wèn)題】（8分） 提示：此題可采用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)對(duì)于給定的一個(gè)序列，。我們可以得到一些遞增上升的子序列，這里。比如，對(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)度。要求寫(xiě)出你設(shè)計(jì)的算法思想及遞推函數(shù)的公式表達(dá)。.參考解答：設(shè)表示：從左向右掃描過(guò)來(lái)直到以元素結(jié)尾的序列，獲得的最長(zhǎng)上升子序列的長(zhǎng)度，且子序列包含元素（）。即，是從，到中找最大的一個(gè)值，再加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）見(jiàn)（1）中所畫(huà)的圖。5分（4）最優(yōu)解為3，1，2，最優(yōu)值為25。3分4.【Gray碼構(gòu)造問(wèn)題】（8分） 提示：此題可采用分治遞歸算法實(shí)現(xiàn)問(wèn)題描述：“格雷碼”是一個(gè)長(zhǎng)度為的序列，滿足：（a）每個(gè)元素都是長(zhǎng)度為n比特的串（b）序列中無(wú)相同元素（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)n1時(shí)，輸出格雷碼0, 1當(dāng)n1時(shí)，格雷碼的長(zhǎng)度為，即共有個(gè)碼序列。此時(shí)，將問(wèn)題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0，下半部分最高位設(shè)為1。剩下n-1位的格雷碼的構(gòu)造采用遞歸的思路。評(píng)分準(zhǔn)則：1) 答到使用分治算法，并且推導(dǎo)出分治算法的過(guò)程，邊界設(shè)定清晰（即當(dāng)僅輸出1位的格雷碼如何處理），本題即可得滿分；2) 說(shuō)明使用分治算法，但漏邊界條件，扣2分以上；其它情況酌情考慮。5.（13分）給定帶權(quán)有向圖（如下圖所示）G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱(chēng)為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和?，F(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將此過(guò)程填入下表中。43211初始dist5dist4dist3dist2uS迭代參考解答：（13分）6030501051，2，3，4，546030501031，2，4，339030501041，2，4210030601021，211003010-1初始dist5dist4dist3dist2uS迭代6.（13分）有0-1背包問(wèn)題如下：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)問(wèn)對(duì)于此0-1背包問(wèn)題，應(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）參考解答：（13分）可知隨著物品的重量增加，物品的價(jià)值減少；因此可以用貪心算法來(lái)求解。以選取單位重量物品價(jià)值高為貪心策略。1.先把重量為2的物品放進(jìn)背包，此時(shí)剩余載重量為17，P為15。2.把重量為3的物品放進(jìn)背包，此時(shí)剩余載重量為14，P為23；3.把重量為4的物品放進(jìn)背包，此時(shí)剩余載重量為10，P為29；4.把重量為5的物品放進(jìn)背包