算法設計與分析知到智慧樹期末考試答案題庫2025年天津大學非確定性算法與算法的確定性是相互矛盾的。（）

答案:錯問題X可以多項式地規約到問題Y，那么（）

答案:X至多與Y一樣“難”問題X可以多項式地規約到問題Y，并且X是P類問題，則Y也是P類問題。（）

答案:錯問題X可以多項式地規約到問題Y，則（）敘述正確。

答案:如果Y屬于P類問題，那么X屬于P類問題；如果Y屬于NP類問題，那么X也屬于NP類問題；如果Y屬于NP類問題，那么X也有可能屬于P類問題問題X可以多項式地規約到Y，意味著X至多與Y一樣難。（）

答案:對問題Q是NP難問題，則（）

答案:Q至少與NP類問題一樣“難”；Q可能屬于NP類問題問題Q是NPC問題，則（）

答案:Q至多與NP難問題一樣“難”采用漸近復雜性來分析算法得出的不是時間量，而是一種增長趨勢的度量。()

答案:對遞歸算法與遞推算法是同一種算法。（）

答案:錯適用于貪心算法求解的問題一般具備貪心選擇性質和最優子結構性質。（）

答案:對貪心算法適用于求解的問題一般具備以下幾個特征().

答案:滿足貪心選擇性質；滿足最優子結構性質貪心算法是一種自頂向下的求解方法，分步做出貪心選擇，逐步將問題變成規模較小的問題求解。（）

答案:對貪心算法所做出的選擇可能依賴于到目前為止已經做出的選擇，但是不依賴于將來的選擇或子問題的解。（）

答案:對設某堆中有n個結點，則在該堆中插入一個新結點的時間復雜度為O(log2n)。（）

答案:對設有5個物品，背包承重為10，5個物品價值p=[6,3,5,4,6]，質量w=[2,2,6,5,4]，則該0/1背包問題的解向量為（）。

答案:[1,1,0,0,1]設有5個物品，背包承重為10，5個物品價值p=[6,3,5,4,6]，質量w=[2,2,6,5,4]，則使用基于迭代的動態規劃方法求解該0/1背包問題時，出現過（）等總價值的中間結果。

答案:6；9；10設M1,5=M1M2M3M4M5表示5個矩陣相乘，矩陣維度r=[10,5,1,10,2,10]，令c(i,j)為計算Mi,j的優化乘法數，則c(3,5)為（）。

答案:40設M1,5=M1M2M3M4M5表示4個矩陣相乘，矩陣維度r=[10,5,1,10,2,10]，若使用動態規劃方法求解該問題，則在填表求解過程中，可能會出現（）等中間過程結果。

答案:50；150；200設M1,4=M1M2M3M4表示4個矩陣相乘，矩陣維度r1=3,r2=8,r3=3,r4=8,r5=3，則鏈乘的最少次數是（）。

答案:171設M1,4=M1M2M3M4表示4個矩陣相乘，矩陣維度r1=2,r2=10,r3=2,r4=10,r5=2，則鏈乘的最少次數是（）。

答案:88計算機算法指的是（）。

答案:解決問題的有限運算序列計算一個整數的完全平方根問題不屬于（）

答案:決策問題若使用基于迭代的動態規劃方法計算n個長度為p字符串的最長公共子序列長度，則其時間復雜度和空間復雜分別為（）。

答案:若使用基于迭代的動態規劃方法計算n個長度為p字符串的最長公共子序列長度，則其時間復雜度和空間復雜分別為（）。能夠用動態規劃算法求解的問題一定屬于()

答案:NP問題考慮改進的快速排序算法，在每一次劃分時選取中點元素(使用選擇算法選取中點元素)作為支點元素進行劃分，這種改進快速排序算法的最壞運行時間為（）。

答案:考慮改進的快速排序算法，在每一次劃分時選取中點元素(使用選擇算法選取中點元素)作為支點元素進行劃分，這種改進快速排序算法的最壞運行時間為（）。考慮快速排序算法在劃分執行過程中總選擇A[1]作為支點元素，其中A[1,…,n]是待劃分的數組，則該快速排序算法的時間復雜度函數為().

答案:考慮快速排序算法在劃分執行過程中總選擇A[1]作為支點元素，其中A[1,…,n]是待劃分的數組，則該快速排序算法的時間復雜度函數為().素數檢驗問題屬于難解問題（）

答案:錯算法的空間復雜度是指算法程序中指令（或語句）的條數。（）

答案:錯算法的有窮性是指算法必須能在執行有限個步驟之后終止。（）

答案:對算法的時間復雜度取決于（）。

答案:待處理數據的初態；問題的規模算法的復雜性分析研究問題的實例編碼長度與復雜性的關系。（）

答案:對算法分析的兩個主要方面是時間復雜度和空間復雜度的分析。（）

答案:對程序塊（）不是回溯法中遍歷排列樹的算法框架程序（）。

答案:程序塊（）不是回溯法中遍歷排列樹的算法框架程序（）。用漸進表示法分析算法復雜度的增長趨勢。（）

答案:對用回溯法解題的一個顯著特征是在搜索過程中動態產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。（）

答案:對用回溯法解批處理作業調度問題時，該問題的解空間結構為子集樹結構。（）

答案:錯用回溯法求解最優裝載問題時，若待選物品為m種，則該問題的解空間樹的結點個數為2m。（）

答案:錯用分支限界法求解帶截止期的作業調度問題時，活動節點的優先級是按照什么來排列的？（）

答案:下界值從小到大用不同方法解決0/1背包問題時，設背包容量為C，有n個物品，則其空間復雜度（僅考慮算法本身所產生的空間大小，不考慮用于存儲輸入與最終結果的空間）可能為（）。

答案:用不同方法解決0/1背包問題時，設背包容量為C，有n個物品，則其空間復雜度（僅考慮算法本身所產生的空間大小，不考慮用于存儲輸入與最終結果的空間）可能為（）。活動節點一旦成為擴展節點，就一次性產生其所有兒子節點。（）

答案:對比較分支限界法和回溯法，兩者的不同是()

答案:在一般情況下，分支限界法與回溯法的求解目標不同；分支限界法與回溯法的搜索方式不同；分支限界法需要借助活動節點表數據結構，而回溯法則不需要；擴展節點的擴展方式不同某算法所需時間由以下方程表示，求出該算法時間復雜度（

）。

答案:O(nlog2n)某算法所需時間由以下方程表示，求出該算法時間復雜度（

）。

答案:O(nlog2n)無論是有向圖還是無向圖，用鄰接矩陣來表示時所需要的存儲空間都是（）.

答案:無論是有向圖還是無向圖，用鄰接矩陣來表示時所需要的存儲空間都是（）.斐波那契數列FN的定義為：F0=0,F1=1,FN=FN?1+FN?2,N=2,3,…。用遞歸函數計算FN的時間復雜度是：（）。

答案:O(2N)插入排序算法在最好情況下的時間復雜度是（）。

答案:插入排序算法在最好情況下的時間復雜度是（）。插入排序算法在最壞情況下的時間復雜度是（）。

答案:插入排序算法在最壞情況下的時間復雜度是（）。快速排序問題屬于()

答案:易解問題快速排序算法在最好情況下的時間復雜度是（）。

答案:快速排序算法在最好情況下的時間復雜度是（）。快速排序算法在最壞情況下的時間復雜度是（）。

答案:快速排序算法在最壞情況下的時間復雜度是（）。歸并排序法的時間復雜度和空間復雜度分別是（）。

答案:O(nlog2n)；O(n)將長度分別為m,n的兩個單鏈表合并為一個單鏈表的時間復雜度為O(m+n)。（）

答案:錯對于非確定性算法，當驗證器對于實例w和證書c返回“False”時，說明算法對實例w無解。（）

答案:錯對于分支限界法與回溯法，下面說法正確的是（）。

答案:求解目標不同；對擴展結點的擴展方式不同；存儲空間的要求不同對于一個加權連通無向圖，在Kruskal’sMST(KrusKal’s最小生成樹)算法中,若使用最大隊列代替最小隊列，則可生成一個最大成本樹(而不是最小成本樹).()

答案:對如果問題的最優解包含其子問題的最優解，則稱該問題具備最優子結構性質。（）

答案:對大Ω符號用來描述函數在漸近意義上增長率的下限。()

答案:對大Θ記號的定義可以用極限形式描述：若Limn-＞∞︱f(n)/g(n)︱=c，則f(n)=Θ(g(n))，其中c的值要求滿足的條件是（）。

答案:0＜c＜∞大O記號的定義可以用極限形式描述：若Limn-＞∞︱f(n)/g(n)︱=c，則f(n)=O(g(n))，其中c的值要求滿足的條件是（）。

答案:0≤c＜∞大O符號用來描述函數在漸近意義上增長率的上限。()

答案:對在快速排序算法中選擇不同的元素作為支點元素進行劃分可能得到不同情形的時間復雜度。假定問題的規模為n，快速排序算法針對不同情形復雜度的結果可能為().

答案:在快速排序算法中選擇不同的元素作為支點元素進行劃分可能得到不同情形的時間復雜度。假定問題的規模為n，快速排序算法針對不同情形復雜度的結果可能為().在對問題的解空間樹進行搜索的方法中，一個結點有多次機會成為活結點的是（）。

答案:回溯法在回溯法中，并不是先構造出整棵狀態空間樹，再進行搜索，而是在搜索過程，逐步構造出狀態空間樹，即邊搜索，邊構造。（）

答案:對在分支限界法中，每一個活動節點只有兩次次機會成為擴展節點。（）

答案:錯在分支限界法中，是采用()的策略，依次生成擴展節點的所有分支。

答案:廣度優先在使用遞歸算法時，必須有一個明確的遞歸結束條件，稱為遞歸出口，否則將無限進行下去。（）

答案:對在使用動態規劃方法解決實際問題時，應盡量用迭代取代遞歸，并盡可能減少空間復雜度。（）

答案:對在一個至少包含三個頂點的加權連通單向圖中，假定邊的權重互不相同，則權重最大的邊不可能被包含在任何最小生成樹中。()

答案:錯回溯算法是嘗試搜索算法中最為基本的一種算法，其采用了一種不能走就掉頭的思想作為其控制結構。（）

答案:對回溯算法和分支限界法的問題的解空間樹可以是無序樹。（）

答案:錯回溯算法和分支限界法的問題的解空間樹不會是（）。

答案:無序樹回溯法的解（x1,x2,……,xn）的隱約束一般指個元素之間應滿足的某種關系。（）

答案:對回溯法的算法框架按照問題的解空間一般分為子集樹算法框架和（）算法框架（）。

答案:排列樹回溯法的效率依賴于下列哪些因素（）。

答案:滿足顯約束的值的個數；計算約束函數的時間；計算限界函數的時間回溯法的效率不依賴于以下哪一個因素？（）

答案:問題的解空間的形式回溯法求問題的所有解時，要回溯到根，且根結點的子樹都要已被搜索遍才結束。（）

答案:錯回溯法是指具有限界函數的深度優先生成法。（）

答案:對回溯法是一種既帶有系統性又帶有跳躍性的搜索算法。（）

答案:對回溯法搜索解空間樹時，常用的兩種剪枝函數為（）。

答案:限界函數；約束函數回溯法在解空間樹T上的搜索方式是（）。

答案:深度優先回溯法與分支限界法一樣，都是一種在問題的解空間樹中搜索問題解的算法。（）

答案:對可用Master方法求解的遞歸方程的形式為（）。

答案:T(n)=aT(n/b)+f(n),a≥1,b＞1,為整數,f(n)＞0.可以解決0/1背包問題的方法包括（）。

答案:回溯法；分支限界法；動態規劃法；貪心法動態規劃的適用條件為無后效性、子問題相互獨立、最優子結構性質。（）

答案:錯動態規劃的適用條件為（）。

答案:無后效性；子問題的重疊性；最優子結構性質動態規劃方法適合解決（）等問題。

答案:最短路徑問題；背包問題；旅行商問題利用窮舉因子的方法判斷一個數是否為合數的算法時間復雜性具有偽多項式界。（）

答案:對分支限界法比回溯法更節省存儲空間。（）

答案:錯分支限界法在問題的解空間樹中，按()策略，從根節點出發搜索解空間樹。

答案:廣度優先分支限界法在“分支”過程中的搜索策略是()

答案:廣度優先分支限界法和回溯法的區別中不包括（）

答案:解空間結構分支限界法保留下來的活動節點是有可能導致可行解或最優解的節點，回溯法則不是。（）

答案:錯分支限界法主要有哪幾種方式實現？（）

答案:FIFO隊列式；優先隊列式分支限界法分支限界法中活動節點可以多次擴展。（）

答案:錯分支限界法中“限界”的目的是減小搜索空間，提高搜索效率。（）

答案:對分支限界法中，解空間組織成()結構然后進行搜索。

答案:樹分支限界法一般比回溯法使用更多內存空間。（）

答案:對分支限界法一般更適合求解最優化問題。（）

答案:對關于旅行商問題的說法，錯誤的是（）

答案:旅行商問題的解空間與最短路徑問題相同關于多項式規約，下面敘述正確的是()

答案:所有的P類問題都可以多項式地規約到NP類問題；所有的NP類問題都可以多項式地規約到NP難問題關于回溯算法和分支限界法以下哪個是不正確描述（）。

答案:回溯法中每個活結點只有一次機會成為擴展結點關于動態規劃的描述，正確的是（）。

答案:動態規劃是解決多階段決策過程最優化解的一種常用算法思想；動態規劃求解的問題必須滿足最優化原理；動態規劃得到的是精確解關于P類問題，下面敘述正確的是（）

答案:存在求解P類問題的算法，其復雜性的上界為多項式。關于NP類問題，下面敘述正確的是（）

答案:NP類問題一定包含P類問題。關于N-puzzle問題描述錯誤的是（）

答案:估計成本可以比實際成本高，A-star算法仍然可以找到最優解偶圖覆蓋問題是NP-hard問題，對于任何輸入，使用貪心算法只能求得近似解。（）

答案:錯停機問題屬于NP難問題。（）

答案:錯停機問題不屬于()

答案:NP難問題假定圖中所有邊的權值都非負，那么兩點之間的最短路徑一定被包含在圖的最小生成樹中。（）

答案:錯使用動態規劃方法解決矩陣乘法鏈問題的時間復雜度和空間復雜度分別為（）。

答案:使用動態規劃方法解決矩陣乘法鏈問題的時間復雜度和空間復雜度分別為（）。使用動態規劃方法所解決的問題所應該具有的性質包括（）等。

答案:無后效性；子問題的重疊性優先隊列式分支限界法選取擴展節點的原則是()

答案:節點的優先級以深度優先方式系統搜索問題解的算法稱為（）。

答案:回溯算法以下哪些是算法漸近分析常用的符號？()

答案:以下哪些是算法漸近分析常用的符號？()以下哪個選項是正確的（）

答案:以下哪個選項是正確的（）以下可以用來描述算法的有？（）。

答案:文字敘述；程序語句；偽代碼和流程圖令T是圖G的最小生成樹，那么對于任意點對s和t，圖G中從s到t的最短路徑也是T中從s到t的最短路.（）

答案:錯與回溯法一樣，分支限界也是搜索一個解空間，而這個解空間通常組織成一棵樹。（）

答案:對不斷回頭尋找目標的方法稱為（）。

答案:回溯法下面給出的四種排序方法中，所需要的比較次數與待排數據的輸入無關的是（）.

答案:選擇排序下面算法時間復雜性為偽多項式的有（）

答案:下面算法時間復雜性為偽多項式的有（）下面的問題屬于NP問題的有（）

答案:計算兩個正整數的最大公約數；矩陣乘法鏈問題；找出圖中所有點對的最短路徑問題下面的問題中，屬于難解的問題有()

答案:在整個互聯網里，查找含有”NP問題”的網頁；漢諾塔問題下面的問題中，不屬于易解的問題有（）

答案:子集和數問題；4-皇后問題；TSP問題下面哪種函數是回溯法中為避免無效搜索采取的策略（）。

答案:剪枝函數下述有關分支限界法搜索過程描述錯誤的是（）

答案:搜索過程中，所有孩子節點已產生的節點稱為擴展節點；搜索過程中，所有孩子節點已產生的節點稱為活動節點下述有關分支限界法搜索過程描述正確的是（）

答案:當解空間樹是一棵樹時，搜索從根節點開始；搜索過程中，擴展節點一次性生成所有的孩子節點；搜索過程中，保留下來的孩子節點是可能導致可行解或最優解的節點；搜索過程中，舍棄的孩子節點是導致不可行解和非最優解的節點下述有關分支限界法搜索過程描述正確的是()

答案:搜索過程中，保留下來的孩子節點是可能導致可行解或最優解的節點；搜索過程中，擴展節點一次性生成所有的孩子節點；搜索過程中，保留下來的孩子節點是活動節點，被插入活動節點表中下述關于分支限界法的說法中，錯誤的是（）

答案:分支限界法不能求解n皇后問題下列問題可使用貪心算法求得最優解的是（）.

答案:貨箱裝載問題下列問題中可以用回溯算法解決的是？（）

答案:0/1背包問題；貨箱裝船問題；N皇后問題；旅行商問題下列算法為在數組A[0,...,n-1]中找出最大值和最小值的元素，其平均比較次數為（

）。

答案:3n/2-3/2下列算法中通常以自底向上的方式求解最優解的是（）。

答案:動態規劃法下列排序算法的常規實現中，哪些空間復雜度是O(1)：（）。

答案:冒泡；選擇下列屬于回溯算法可以解答的問題有（）。

答案:旅行商問題；N皇后問題；貨箱裝船問題；最大完備子圖問題下列敘述中正確的是（）。

答案:O(Nlog2N)；O(1)下列函數中漸進時間復雜度相同的是（）

答案:下列函數中漸進時間復雜度相同的是（）下列函數中漸近時間復雜度最小的是（）

答案:下列函數中漸近時間復雜度最小的是（）下列函數中漸近時間復雜度最大的是（）

答案:下列函數中漸近時間復雜度最大的是（）下列關于效率的說法正確的是（）。

答案:效率是一個性能要求，其目標應該在需求分析時給出；提高程序效率的根本途徑在于選擇良好的設計方法，數據結構與算法；效率主要指處理機時間和存儲器容量兩個方面下列代碼的時間復雜度是（

）。

答案:O(log2N)一共有10個臺階，一次可以跨2個或者1個臺階，一共有（）種走法。

答案:89一個問題的貪心選擇性質是指問題的最優解可通過一系列具備最優(貪心)選擇得到。（）

答案:對一個問題可用動態規劃算法或貪心算法求解的關鍵特征是問題的（）。

答案:最優子結構性質一個連通圖中具有最小權重的邊，必定被包含在圖的最小生成樹中。()

答案:對T(n)=O(f(n))中，函數O（）說明存在足夠大的正整數M，使得T(n)≤M×f(n)。（）

答案:對Prim算法和Kruskal算法都是貪心算法，但這兩種算法都可以求得最小生成樹問題得最優解（）

答案:對Ｏ(f(n))+Ｏ(g(n))=Ｏ(max