計(jì)算機(jī)算法設(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(_logn_)。4、已知一個(gè)分治算法耗費(fèi)的計(jì)算時(shí)間 T(n)，T(n)滿足如下遞歸方程：T(n) = 0( 1)(2T (n/2)+0(n)解得此遞歸方可得T(n)= O (_ n log n。這種方法

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

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

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

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

6、和舍伍德（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)階從低到高排序）2n 3n

7、log n n! nlog n n2 nn 103參考解答：103 Y log n Y nlog n y n2 3 n!Y nn每個(gè)選手必須與其他選手各賽一次; 每個(gè)選手一天只能賽一次；循環(huán)賽一共進(jìn)行n - 1天。2、(8分)現(xiàn)在有8位運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽，要設(shè)計(jì)一個(gè)滿足以下要求的比 賽日程表：(1)(2)請(qǐng)利用分治法的思想，給這8位運(yùn)動(dòng)員設(shè)計(jì)一個(gè)合理的比賽日程。 參考解答：(3)表示結(jié)束租用時(shí)刻，10個(gè)客戶的申請(qǐng)如下表所示:i12345678910s(i)03153511886f(i)65498713121110同一時(shí)刻，該羽毛球場(chǎng)只能租借給一位客戶， 請(qǐng)?jiān)O(shè)計(jì)一個(gè)租用安排方案，在 這10位

8、客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針對(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)最后，可以滿足：申請(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)是可以滿足的最大客戶

9、人數(shù)。4、（8分）對(duì)于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：.I0i=j皿 j=佃nmi,k +mk+1, j + PiPkPjj其中mi，j為計(jì)算矩陣連乘Ai, Aj所需的最少數(shù)乘次數(shù)，“為矩陣Ai的行,p為矩陣Ai的列?，F(xiàn)有四個(gè)矩陣，其中各矩陣維數(shù)分別為:AAAA50x1010x4040x30305p 0X p 1p 1X p 2P 2% P 3P 3X P 4請(qǐng)根據(jù)以上的遞歸關(guān)系，計(jì)算出矩陣連乘積A AAA所需要的最少數(shù)乘次數(shù)。參考解答：m11 + m24 +90944=0+ 8000 + 50咒 10咒 5 = 10500m14 =min m12 +m34 + p? p4 =2

10、0000+ 6000 +50x40x 5 = 36000m13pm44 + Po p3 P4 = 27000 + 0 + 50x 30x 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)先取

11、重量輕的物品放進(jìn)背包。最終可以把重量分別為2, 3, 4, 5的三個(gè)物品放進(jìn)背包，得到的價(jià)值和為15 + 8 + 6 + 4 = 33，為最大值。6. 請(qǐng)用英文寫出三種以上能求解0-1背包問題的設(shè)計(jì)算法策略。參考解答：Dyn amic P rogrammi ngBacktrackBran ch-a nd-Bo und（每答對(duì)一條給一分）7. 請(qǐng)說明動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。參考解答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是自底向上計(jì)算各個(gè)子問題的最優(yōu)解，即先計(jì)算子問題的最優(yōu)解， 然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu)8. 請(qǐng)說明：（

12、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)特征。（6分）（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值

13、時(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）禾用該問題分解出的子問題的解可以合并為該問題的解；即子問題之間不包（4）原問題所分解出的各個(gè)子問題是相互獨(dú)立的， 含公共的子問題。，然后再從當(dāng)前的 為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加速搜索的進(jìn) ，并根據(jù)函數(shù)值，從當(dāng)前活結(jié)11. 分支限界法的搜索策略是什么？參考解答：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支）活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。程，在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)

14、函數(shù)值（限界）使搜索朝著解空間上有最優(yōu)解的分（6分）點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。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趨向無窮大時(shí)，影響算法效率的重要因素是 T（n）的 數(shù)量級(jí)，而其他因素僅是使時(shí)間復(fù)雜度相差常數(shù)倍，因此可以用 T（n）的數(shù)量級(jí)( 階

15、) 評(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(I)T(n , I) I Dn17 簡(jiǎn)述二分檢索(折半查找)算法的基本過程。參考解答：設(shè)輸入是一個(gè)按非降次序排列的元素表Ai : j和x，選取A(i+j)/2與 x 比較，如果

16、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ù):獲得最大利潤(rùn)。最優(yōu)量度:最大利潤(rùn) /重量比。19 采用回溯法求解的問題，其解如何表示？有什么規(guī)定？參考解答：?jiǎn)栴}的解可以表示為n元組：(xi,x 2, , Xn),Xi S, S為有窮集合， Xi S, ( xi,x 2, , Xn)具備完備性，即(xi,x 2, , Xn)是合理的，貝(Xl,X2, Xi) (in) 一定合理。20 回溯

17、法的搜索特點(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í)間復(fù)雜性？參考解答： 最壞情況

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

19、種量度標(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è)元素的分好類的序列。 如果分割后子問題還很大， 則繼續(xù)分 治，直到一個(gè)元素。30 快速排序的基本思想是什么。參考解答：快速排序的基本思想是在待排序的 N個(gè)記錄中任意取一個(gè)記

20、錄，把該 記錄放在最終位置后， 數(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)是指一條沿著圖G

21、的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)工，如果 k=-1，貝U C(Xk, X1)MX。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è)序列(a,a2,，a , 1N1000。我們可以得到一些遞增 上升的子序列 佝1,42,Qk),這里1 i1 ci2 “ a j;1 j 1I 1 i1; Vj ( j i ),都有 ai = a j即，f(i)是從f(1), f(2),至yf(i-1)中找最大的一個(gè)值，再加1。或者1。就是1。主要是看ai這個(gè)元素能否加入到之前已經(jīng)獲得的最長(zhǎng)上升子序列， 如 果能加入，是之前已獲得的最長(zhǎng)上升子序列長(zhǎng)度加一； 如果不能加入，就取這最 后一個(gè)元素作為一個(gè)單獨(dú)子序列，長(zhǎng)度為最后，所要求的整個(gè)序列的最長(zhǎng)公共子序列長(zhǎng)度為maxf(i)

23、: 1=i=當(dāng)前最優(yōu)解代價(jià)（2）若當(dāng)前代價(jià)f（3）見（1）中所畫的圖。5分（4）最優(yōu)解為3，1, 2，最優(yōu)值為25。3分問題描述:“格雷碼”是一個(gè)長(zhǎng)度為2n的序列，滿足:4. 【Gray碼構(gòu)造問題】（8分）一一提示：此題可采用分治遞歸算法實(shí)現(xiàn)(a)(b)(c)每個(gè)元素都是長(zhǎng)度為n比特的串 序列中無相同元素連續(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)造方案即可，

24、格 雷碼并不唯一）。參考解答：此題可用分治法解決。當(dāng)n= 1時(shí)，輸出格雷碼0, 1當(dāng)n1時(shí)，格雷碼的長(zhǎng)度為2n，即共有2n個(gè)碼序列。此時(shí)，將問題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0,下半部分最高位設(shè)為1。剩下n-1位的格雷碼的構(gòu)造采用遞歸的思路。評(píng)分準(zhǔn)則：1）答到使用分治算法，并且推導(dǎo)出分治算法的過程，邊界設(shè)定清晰（即當(dāng) 僅輸出1位的格雷碼如何處理），本題即可得滿分；2）說明使用分治算法，但漏邊界條件，扣 2分以上；其它情況酌情考慮。實(shí)數(shù)。另外，還給定V中的一個(gè)點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)50算從源頂點(diǎn)1到其它頂點(diǎn)間最短5. （ 13分）給定帶權(quán)有向圖34L一旨路上各邊10loG =（V,E），其中每條邊的權(quán)是非負(fù)現(xiàn)在要計(jì)算從源到所有其它各頂徑。請(qǐng)將此口?，F(xiàn)采用 Dijkstra 算法計(jì)60 呈填入下表中。迭代Sudist2dist3dist4dist5初始1123420參考解答：（13分）迭代Sudist2dist3dist4dist5初始1-103010011 , 2210603010021 , 2, 441050309031 , 2, 4, 331050306041 , 2,