算法分析與設計智慧樹知到期末考試答案章節(jié)答案2024年湖南中醫(yī)藥大學

算法分析與設計智慧樹知到期末考試答案+章節(jié)答案2024年湖南中醫(yī)藥大學在n皇后問題中，如果在棋盤的某一個位置(i,j)去除一個皇后，則()。

答案:M[j]=0###L[i+j]=0###R[i-j+N]=0###A[i][j]=0關于0-1背包問題，以下說法正確的是()。

答案:每種物品均只有一件###對于每種物品，只有裝入和不裝兩種選擇，不允許裝入物品的一部分###其目標是使得裝入背包物品的總價值最大關于部分背包問題的描述，以下正確的是()。

答案:部分背包問題的時間復雜度為O(nlogn)###部分背包問題使用貪心算法可以求得全局最優(yōu)解###部分背包問題允許將一個物品的一部分裝入背包()不能夠使用貪心算法求解。

答案:0-1背包問題###圖的m著色問題###n皇后問題馬的遍歷問題的剪枝條件為()。

答案:不能走出棋盤邊界###每個點只經(jīng)過一次在裝載問題中，已知c為輪船的載重量，bestw是當前最優(yōu)解，ew是當前擴展結點的重量，r是剩余集裝箱的重量，w[i]是待裝載集裝箱的重量，當()時，需要將對應的子樹剪掉。

答案:ew+w[i]>c###ew+r<=bestwPrim算法適合稠密圖，其時間復雜度只與邊的數(shù)目有關。

答案:錯解決有10個圓盤的漢諾塔問題，至少需要移動圓盤1024次。

答案:錯含有n個頂點的連通圖的生成樹含有n(n+1)/2條邊。

答案:錯用回溯法解決0-1背包問題的基本思想是從第1個物品開始逐個選擇物品，當剩余容量裝不下后續(xù)考慮的物品或者得不到更優(yōu)解時，再通過回溯來修改先前的裝入方案，直到求得全局最優(yōu)解為止。

答案:對以下代碼的時間復雜度為()。i=1;while(i<=n){i+=2;}

答案:O(n)小明的表哥為他推薦了一些學習計算機編程的小視頻，這些視頻的播放時間長短不完全相同?，F(xiàn)在給定一段時間，為了能夠快速計算出在這段時間內(nèi)小明最多可以看多少個視頻，可以使用()算法。

答案:貪心已知一只青蛙一次可以跳上1級臺階，也可以跳上2級。該青蛙跳上一個5級的臺階總共有()種跳法。

答案:8圖的m著色問題可使用()算法求解。

答案:回溯輸入數(shù)組(6,-1,5,4,-7)，它的最大子段和以及子段的起始位置和結束位置(位置均從1開始)分別是()、()和()。

答案:14,1,4函數(shù)f(n)=3nlogn^3+n+2的漸進表達式是（）。

答案:O(nlogn)馬的遍歷問題的剪枝函數(shù)：棋盤大小為m*n，A[][]數(shù)組用于記錄馬的行走過程。boolcheck(intx,inty){if(x>=1&&x<=n&&y>=1&&y<=m&&(!A[x][y]))____(1)___;else____(2)____;}

答案:(1)returntrue(2)returnfalse以深度優(yōu)先方式搜索問題解的算法稱為()。

答案:回溯法如果使用窮舉法求解0-1背包問題，將產(chǎn)生（）種裝物品的方案。

答案:2^n()描述算法形象直觀，且易于理解。

答案:程序流程圖4皇后問題的解的個數(shù)為()。

答案:2可使用()設計一個求取一個序列的最長遞增子序列的高效算法。

答案:動態(tài)規(guī)劃如果從最后一個物品開始裝入背包，0-1背包問題的最優(yōu)解為()?！緉為物品數(shù)量，c為背包容量】

答案:m[1][c]以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為()。

答案:分支限界法在圖的m著色問題中，如果有5個頂點，3種顏色，則解空間樹為()。

答案:一棵6層（包括第一層）的3叉樹關于二分查找的設計思想，以下說法正確的是()。

答案:如果key大于a[mid]，則在升序序列的后半部分繼續(xù)查找###如果key等于a[mid]，則返回mid###如果key小于a[mid]，則在升序序列的前半部分繼續(xù)查找###待查找元素key首先和最中間的值a[mid]進行比較分支限界法最常見的實現(xiàn)方式包括()。

答案:優(yōu)先隊列式分支限界法###隊列式分支限界法關于Prim算法和Dijkstra算法，以下說法正確的是()。

答案:兩個算法在不優(yōu)化時的時間復雜度都為O(V^2)，V表示頂點的個數(shù)###兩個算法都需要引入一個數(shù)組用于記錄一個點是否被訪問過###兩個算法都是貪心算法的經(jīng)典實例###兩個算法都包含了松弛操作，在松弛時對相應的數(shù)據(jù)結構進行更新如果馬的初始位置為(x,y)，在不考慮重復和出界的情況下，()是下一個可以到達的遍歷位置。

答案:(x-2,y-1)###(x-2,y+1)###(x+2,y-1)###(x-1,y+2)()不是使用自然語言描述算法的優(yōu)點。

答案:直觀形象###格式規(guī)范###易于自動生成代碼遞歸的應用場景包括()。

答案:采用的數(shù)據(jù)結構是遞歸的###問題的定義是遞歸的###問題的求解方法是遞歸的以下不等式正確的是()。

答案:O(logn)###O(nlogn)###O(n)下列關于動態(tài)規(guī)劃算法與分治法的說法正確的是（）

答案:動態(tài)規(guī)劃算法與分治法類似，基本思想是將待求解問題分解成若干個子問題###動態(tài)規(guī)劃算法經(jīng)分解得到的子問題往往不是獨立的，有些子問題被重復計算多次###分治算法經(jīng)分解得到的子問題往往是獨立的能夠使用貪心算法求解的問題需要具備的基本要素為()。

答案:最優(yōu)子結構###貪心選擇性質關于貪心算法，以下說法正確的是()。

答案:貪心算法在每一步選擇中都采取最好或者最優(yōu)（最有利）的選擇策略###部分背包問題可以使用貪心算法求解以下表達式正確的是()。

答案:O(Cf(N))=O(f(N))###O(f)O(g)=O(fg)###O(f)+O(g)=O(f+g)###O(f)+O(g)=O(max(f,g))以下采用分治策略的算法包括()。

答案:快速排序###二分查找分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹，在分支限界法中，每一個活結點有多次機會成為擴展結點。

答案:錯動態(tài)規(guī)劃算法通過保存已解決子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。

答案:對在最壞情況下，快速排序的效率仍然高于其他所有排序算法。

答案:錯對于同一背包和相同的一組物品，作為部分背包問題求解得到的總價值一定大于等于作為0-1背包問題求解得到的總價值。

答案:對在解決活動安排問題時應首先對活動進行排序，排序的依據(jù)是按照活動開始時間降序排列。

答案:錯在圖的m著色問題中，當搜索的當前節(jié)點t<=N時，依次嘗試m種顏色，調(diào)用剪枝函數(shù)check()進行判斷。如果當前顏色可以使用，則進入下一層搜索；當搜索到葉子節(jié)點時（t>N），即輸出一種著色方案。

答案:對使用貪心算法求解找硬幣問題時，總能找到問題的最優(yōu)解。

答案:錯在使用回溯法求解0-1背包問題時，為了能夠更加高效地進行剪枝，可以通過將剩余物品的價值進行求和的方法得到右子樹的最優(yōu)上界。

答案:錯為了提高問題求解效率，有時候需要在某些遞歸算法中消除遞歸調(diào)用，使其轉化為非遞歸算法。

答案:對對于有64片圓盤的漢諾塔問題，如果每移動一次圓盤需要1秒，則一小時以內(nèi)可以完成全部圓盤的移動。

答案:錯貪心算法中每次做出的貪心選擇都是局部最優(yōu)選擇。

答案:對使用動態(tài)規(guī)劃算法求解最長公共子序列問題，引入數(shù)組c[i][j]存儲序列x[1..i]和y[1..j]的最長公共子序列的長度，則對于長度為m和n的兩條序列，其最長公共子序列的長度為c[m][n]。

答案:對在對Dijkstra算法進行初始化時，如果兩個頂點之間沒有邊，則它們之間的距離為無窮大。

答案:對二分查找算法是運用()的典型實例。

答案:分治策略如果斐波那契數(shù)列的第一項F(0)=1，第二項F(1)=1，則F(8)=___________。

答案:34以下算法中效率最優(yōu)的算法是()。

答案:T(n)=T(n/2)+O(1)直接或間接地調(diào)用自身的算法稱為()。

答案:遞歸如果從第一個物品開始裝入背包，在能夠裝入的情況下，背包的最優(yōu)價值m[i][j]=()。

答案:max{m[i-1][j],m[i-1][j-wi]+vi}函數(shù)f(n)=1+1/n^2的漸近表達式為()。

答案:O(1)在對問題的解空間樹進行搜索的方法中,一個活結點最多有一次機會成為活結點的是()。

答案:分支限界法代碼填空【快速排序的分區(qū)函數(shù)：以第1個元素為基準元素】intswap(inta[],inti,intj){inttemp=a[i];a[i]=a[j];a[j]=temp;}intpartition(inta[],intp,intq){intx=a[p];inti=p,j;for(j=p+1;j<=q;j++){if(a[j]<=x){i++;______(1)________;}}_________(2)___________;returni;}

答案:(1)swap(a,i,j)(2)swap(a,p,i)函數(shù)n^2/10+2^n的漸進表達式為()。

答案:O(2^n)回溯法搜索狀態(tài)空間樹是按照()的順序。

答案:深度優(yōu)先遍歷在裝載問題中，如果右子樹表示不將此集裝箱裝上船。設bestw是當前最優(yōu)解；ew是當前擴展結點所相應的重量；r是剩余集裝箱的重量，則當()時，可將其右子樹剪去。

答案:ew+r<=bestw關于回溯法和分支限界法，以下說法正確的是()。

答案:分支限界法通常用于求滿足約束條件的一個解或特定意義下的最優(yōu)解###在回溯法中，活結點的所有可行子結點均被遍歷后才從棧中彈出###在分支限界法中，每個結點只有一次成為擴展結點的機會###回溯法通常用于求滿足約束條件的所有解如果一個給定裝載問題有解，則采用的裝載策略為：首先將第一艘輪船盡可能裝滿；再將剩余的集裝箱裝上第二艘輪船。

答案:對優(yōu)先隊列式分支限界法將活結點表組織成一個優(yōu)先隊列，按優(yōu)先隊列中規(guī)定的結點優(yōu)先級選取優(yōu)先級最高的下一個結點成為當前擴展結點。

答案:對分支限界法采用的搜索策略是()。

答案:廣度優(yōu)先搜索隊列具有()的性質。

答案:先進先出使用隊列式分支限界法求解裝載問題時，每次從隊列Q中取出隊首元素作為當前擴展結點。取隊首元素后，判斷當前Q是否為空。如Q非空，則將尾部標記-1加入Q，算法開始處理下一層的活結點。

答案:錯根據(jù)活結點表的組織方式不同，分支限界法包括()等形式。

答案:隊列式分支限界法###優(yōu)先隊列式分支限界法關于分支限界法的基本思想，下列描述正確的是()。

答案:每一個活結點只有一次機會成為擴展結點###一直持續(xù)到找到所求的解或活結點表為空時為止###從活結點表中取下一結點成為當前擴展結點，并重復結點擴展過程###那些導致不可行解或導致非最優(yōu)解的子結點被舍棄，其余子結點被加入活結點表中###活結點一旦成為擴展結點，就一次性產(chǎn)生其所有子結點應用分支限界法的三個關鍵問題包括()。

答案:如何組織活結點表###如何設計合適的剪枝函數(shù)###如何確定最優(yōu)解的解向量四皇后問題一共有2個可行解，八皇后問題一共有76個可行解。

答案:錯在N皇后問題中，需要將棋盤當做一個二維數(shù)組來分析，對于該二維數(shù)組，以下說法正確的是()。

答案:對于任意一條右斜線上的兩個點，它們的橫坐標和縱坐標相減的值相同。###對于任意一條左斜線上的兩個點，它們的橫坐標和縱坐標相加的值相同。用m種顏色給n個頂點著色、且使一條邊的兩個頂點顏色不同，則對應的解空間樹是一棵()。

答案:高為n的m叉樹任何一張地圖只用()種顏色就能使具有共同邊界的國家著上不同的顏色。

答案:4使用回溯法求解0-1背包問題時，計算右子樹上界的方法是通過貪心策略求得上界，即將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包，此時得到的價值就是右子樹中解的上界。

答案:對馬的遍歷問題能否有可行解，與()有關。

答案:棋盤大小###馬的初始位置回溯法的主要用途包括求問題的所有解、求問題的最優(yōu)解和求問題的任一解。

答案:對回溯法采用的搜索策略是()。

答案:深度優(yōu)先搜索關于使用回溯法求解0-1背包問題，以下說法正確的是()。

答案:使用約束函數(shù)剪去不合理的左子樹（裝該物品）。###使用限界函數(shù)剪去得不到更優(yōu)解的右子樹（不裝該物品）?；厮莘ㄖ械募糁瘮?shù)包括()。

答案:限界函數(shù)###約束函數(shù)能夠使用貪心算法求解的問題需具備的基本要素包括()。

答案:貪心選擇性質###最優(yōu)子結構性質在對Dijkstra算法進行初始化時，如果兩個頂點之間沒有邊，則它們之間的距離為()。

答案:無窮大在求解部分背包問題時采用的貪心策略是()。

答案:選擇單位重量下價值最大的物品Prim算法適合稀疏圖，其時間復雜度只與邊的數(shù)目有關。

答案:錯使用貪心算法求解最優(yōu)裝載問題，其時間復雜度為()。

答案:O(nlogn)()能夠使用貪心算法求解。

答案:單源最短路徑問題###活動安排問題###最小生成樹問題###部分背包問題###最優(yōu)裝載問題在解決活動安排問題時應首先對活動進行排序，排序的依據(jù)是()。

答案:按照活動結束時間升序排列Dijkstra算法可用于求解()。

答案:每對頂點間最短路徑問題###單對頂點最短路徑問題###單終點最短路徑問題###單源最短路徑問題下列關于貪心算法與動態(tài)規(guī)劃算法說法正確的是()。

答案:貪心算法與動態(tài)規(guī)劃算法求解的問題都具備最優(yōu)子結構性質###貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是貪心算法要求問題具有貪心選擇性質0-1背包問題與部分背包問題的區(qū)別在于()。

答案:在0-1背包問題中，物品只有裝入和不裝入兩種情況，而部分背包問題允許只裝入物品的一部分###若用貪心算法解決0-1背包問題，只能得到近似最優(yōu)解某工廠預計明年有A,B,C,D四個新建項目，每個項目的投資額分別為15,10,12,8（萬元），投資收益分別為12,8,9,5（萬元），投資總額為30萬元，選擇項目()可以使總收益最大。（不允許部分投資某個項目）

答案:B###D###C輸入數(shù)組（-1,0,1,-2,3），它的最大子段和是()。

答案:3字符序列abcde與字符序列abdge的最長公共子序列長度為()，最長公共子串長度為()。

答案:4,2關于備忘錄法，以下說法正確的是()。

答案:備忘錄法為每個解過的子問題建立備忘錄以備需要時查看，又稱查表法。###備忘錄法可以避免相同子問題的重復求解。###備忘錄法的控制結構與直接使用遞歸方法的控制結構相同。使用動態(tài)規(guī)劃算法求兩條長度分別為m和n的序列的最長公共子序列，其時間復雜度為()。

答案:O(n*m)在使用動態(tài)規(guī)劃算法求解0-1背包問題時，若m[i][j]=m[i+1][j-w[i]]+v[i]，說明第i個物品在剩余背包容量為j時可以裝入，并且裝入比不裝入的背包總價值更大，裝入后，背包剩余容量減少w[i]，價值增加v[i]。

答案:對序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為()。

答案:4使用動態(tài)規(guī)劃算法求最大子段和的時間復雜度為()。

答案:O(n)使用窮舉法求解最長遞增子序列的時間復雜度為()。

答案:O(n*2^n)能夠使用動態(tài)規(guī)劃算法來求解的問題通常需要具備兩個重要的性質，它們分別是()。

答案:最優(yōu)子結構###重疊子問題在使用分治法設計算法時，最好使子問題的規(guī)模大致相同，即將一個問題分成大小相等的多個子問題的處理方法是行之有效的。

答案:對快速排序是對傳統(tǒng)排序算法()的一種改進。

答案:冒泡排序在經(jīng)典的漢諾塔問題中，如果有5個圓盤需要從A柱移至C柱，最少需要移動()步。

答案:31給定遞歸公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=()。

答案:O(n^2)已知某樓房共20層，如果采用二分查找，請問最多猜()次就能猜出任意一個樓層。

答案:5已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是()。

答案:計算1到50的和。遞歸的優(yōu)點包括()。

答案:可讀性強###結構清晰###容易用數(shù)學歸納法來證明算法的正確性分治法能解決的問題一般具有（）等特征。

答案:最優(yōu)子結構###分解出的子問題的解可以合并為原問題的解###子問題相互獨立###該問題縮小到一定程度時可以容易地解決遞歸函數(shù)是指在一個函數(shù)體中出現(xiàn)直接或間接調(diào)用該函數(shù)自身的函數(shù)。

答案:對關于快速排序的時間復雜度，()是正確的。

答案:在平均情況下時間復雜度為O(nlogn)###在最壞情況下時間復雜度為O(n^2)###在最好情況下時間復雜度為O(nlogn)對于f(n)=n，下列說法正確的是（）。

答案:f(n)=O(n^3)###f(n)=O(n)###f(n)=O(n^2)程序是算法用某種程序設計語言的具體實現(xiàn)，程序需滿足算法的所有性質。

答案:錯如果存在正的常數(shù)C和自然數(shù)N0,使得當N≥N0時有f(N)≤Cg(N),則稱函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N)),即f(N)的階不高于g(N）的階。

答案:對一個算法的優(yōu)劣由（）決定。

答案:時間復雜度###空間復雜度函數(shù)f(n)=20log3^n的漸進表達式是（）。

答案:O(n)使用偽代碼描述算法具有（）等優(yōu)點。

答案:易于轉化為程序語言代碼###簡單易懂###容易修改算法通常具有（）的性質。

答案:輸出：至少有一個輸出###確定性：組成算法的每條指令清晰、無歧義###輸入：有零個或多個輸入###有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限算法是指解決問題的方法或過程，它包含一系列步驟，用來將輸入數(shù)據(jù)轉換成輸出結果。

答案:對分析以下代碼的時間復雜度：intfunc(intn){inti=1,k=0;while(i<=n){k++;i=i*2;}returnk;}

答案:O(logn)常用的描述算法的形式有（）。

答案:偽代碼###程序流程圖###自然語言為了得到裝入集裝箱的數(shù)量以及裝入的總重量和集裝箱編號，在使用貪心算法求解最優(yōu)裝載問題時，每成功裝入一個集裝箱，則()。

答案:更新輪船已裝載總重量###裝入集裝箱總數(shù)加1###更新輪船的剩余重量###記錄裝載的集裝箱編號()是回溯法的應用實例。

答案:n皇后問題###0-1背包問題###圖的m著色問題關于最長公共子序列問題，以下說法正確的是()。

答案:如果兩個序列的最后一個元素相同，則它們的最長公共子序列長度為去掉最后一個元素后，兩個剩余序列的最長公共子序列長度加1###空序列和一條非空序列的最長公共子序列的長度為0###兩個序列的最長公共子序列可能不唯一###兩個序列的最長公共子序列包含了這兩個序列前綴的最長公共子序列一個算法的優(yōu)劣可以用()來衡量。

答案:時間復雜度###空間復雜度關于Prim算法中的數(shù)據(jù)結構，以下說法正確的是()。

答案:使用used[n]標記頂點是否被訪問###使用數(shù)組lowcost[n]記錄不在S中的頂點到S的最短距離###使用數(shù)組closeset[n]記錄不在S中的頂點在S中的最近鄰接點程序需要具備以下哪些性質？

答案:輸出：至少有一個輸出###確定性###輸入：有零個或多個輸入已知4個物品A、B、C、D的重量分別為[15,10,12,7]，價值分別為[50,20,40,40]，每一個物品均不能分解?，F(xiàn)有一個容量為30的背包，選擇物品()可以使得背包中物品的總價值最大。

答案:C###B###D關于活動安排問題，以下說法正確的是()。

答案:算法每次總是選擇具有最早完成時間的相容活動加入集合中。###對于活動安排問題，貪心算法能求得的整體最優(yōu)解，即它最終所確定的相容活動集合的規(guī)模最大。###活動安排問題的貪心選擇意義在于使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。()屬于搜索算法。

答案:回溯法###分支限界法在圖的m著色問題中需要使用到的數(shù)據(jù)結構包括()。

答案:用一個二維數(shù)組以鄰接矩陣的方式存儲地圖###用一個一維數(shù)組存儲每一個點所著顏色能夠使用分治法求解的問題通常具有的特征包括()。

答案:問題縮小到一定的規(guī)?？梢灾苯忧蠼?##分解出的各個子問題相互獨立###分解出的子問題的解可以合并為原問題的解###問題可以分解為若干個規(guī)模更小的相同類型的子問題關于Dijkstra算法中的數(shù)據(jù)結構，以下說法正確的是()。

答案:需要一個used[]數(shù)組用于記錄一個點是否已訪問過###需要一個dis[]數(shù)組用于保存源點到其他點的最短路徑值###如果源點到某一個點i之間有一條邊，則dis[i]的初始值為這條邊的權重###如果源點到某一個點i沒有直接的邊相連，則dis[i]的初始值為無窮大在物品重量和背包容量都是正整數(shù)的情況下，0-1背包問題可以用()求解。

答案:動態(tài)規(guī)劃算法###回溯法###窮舉法關于Dijkstra算法，以下說法正確的是()。

答案:有向圖和無向圖都可以使用Dijkstra算法來求單源最短路徑###Dijkstra算法既可以用于求解單源最短路徑問題，也可以用于求解單終點最短路徑問題###在Dijkstra算法中，通過松弛操作來更新源點到其他頂點的距離遞歸的基本要素包括()。

答案:遞歸表達式###遞歸結束條件使用貪心算法求解最優(yōu)裝載問題，其時間復雜度為O(n)。

答案:錯使用遞歸對整數(shù)進行求和的速度比使用循環(huán)的速度更快。

答案:錯動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

答案:對在計算最長公共子序列的長度時，為了減少空間需求可以使用滾動數(shù)組。給定兩個序列，長度分別為m和n，可以將短的序列作為行，長的序列作為列，最后可將空間需求減至O(min(m,n))。

答案:對動態(tài)規(guī)劃的基本步驟是先找出最優(yōu)解的性質，并刻畫其結構特征，然后遞歸地定義最優(yōu)值，以自底向上的方式計算出最優(yōu)值，最后根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。

答案:對如果圖中存在負權邊，則不能使用Dijkstra算法來求源點到其他點之間的最短路徑。

答案:對在Prim算法中，每次從不在集合S的點中選出一個點j使得其與S內(nèi)的某點i的距離最短，則(i，j)就是生成樹上的一條邊，同時將j點加入S。

答案:對在馬的遍歷問題中，對于棋盤上任意一點A(x,y)，有八個擴展方向，可以用數(shù)組fx[8]={1,2,2,1,-1,-2,-2,-1},fy[8]={2,1,-1,-2,-2,-1,1,2}來模擬馬走“日”時下標的變化過程。

答案:對快速排序算法的性能取決于劃分的對稱性，劃分越對稱，排序的效率越高。

答案:對Dijkstra算法采用了和Prim算法類似的松弛操作，松弛操作的目的是減少dis[i]的值，如果從源點s到達i有更優(yōu)的路徑則更新dis[i]。

答案:對解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法和分支限界法。

答案:對Dijkstra算法是一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法。

答案:對在最好情況下、最壞情況下、平均情況下的時間復雜度中，可操作性最好的且最有實際價值的，是最壞情況下的時間復雜度。

答案:錯二分查找又稱為折半查找，它是一種高效的查找方法，但是二分查找要求列表中的元素是有序的，是分治算法的典型實例之一。

答案:對隊列Queue具有先進后出的性質。

答案:錯對于一個二維數(shù)組而言，同一條右斜線上的坐標x和y之和為一個相同的數(shù)。

答案:錯任何一張地圖只用4種顏色就能使具有共同邊界的國家著上不同的顏色。

答案:對如果不對頂點的選取過程進行優(yōu)化，Dijkstra算法的時間復雜度為O(EV)?！綱表示頂點的數(shù)量，E表示邊的數(shù)量】

答案:錯回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。

答案:對logn^5+n^1/2=O(n^1/2)

答案:對使用分治設計算法來求解問題時，通常在分解問題時要求子問題的規(guī)模盡量一致。

答案:對某個問題的最優(yōu)解包含著其子問題的最優(yōu)解，這種性質稱為最優(yōu)子結構性質。

答案:對使用分支限界法設計求解裝載問題的算法時，在隊列中增加一個-1作為層的尾部標記。

答案:對快速排序是對冒泡排序的一種改進，它通過分區(qū)函數(shù)將待排序數(shù)據(jù)分為兩組，其中一組中的數(shù)據(jù)都比另一組中的數(shù)據(jù)大，再遞歸對兩組中的數(shù)據(jù)分別進行快速排序。

答案:對對于有5種物品的0-1背包問題，其解空間數(shù)量為()。

答案:32()是動態(tài)規(guī)劃算法的基本要素之一。

答案:子問題重疊性質給定5個集裝箱，它們的重量分別是3,4,5,2,1，已知船的裝載量為10，該船最多可裝載的集裝箱數(shù)量是()個。

答案:4使用回溯法解決0-1背包問題中，在計算右子樹的最優(yōu)上界時，采用了()思想。

答案:貪心通常以自底向上的方式求解最優(yōu)解的算法是()。

答案:動態(tài)規(guī)劃法使用回溯法求解0-1背包問題，限界函數(shù)（用于剪去一些不包含最優(yōu)解的右子樹）的時間復雜度為(