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

答案:錯(cuò)問題X可以多項(xiàng)式地規(guī)約到問題Y，那么（）

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

答案:錯(cuò)問題X可以多項(xiàng)式地規(guī)約到問題Y，則（）敘述正確。

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

答案:對(duì)問題Q是NP難問題，則（）

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

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

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

答案:錯(cuò)適用于貪心算法求解的問題一般具備貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。（）

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

答案:滿足貪心選擇性質(zhì)；滿足最優(yōu)子結(jié)構(gòu)性質(zhì)貪心算法是一種自頂向下的求解方法，分步做出貪心選擇，逐步將問題變成規(guī)模較小的問題求解。（）

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

答案:對(duì)設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（）

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

答案:[1,1,0,0,1]設(shè)有5個(gè)物品，背包承重為10，5個(gè)物品價(jià)值p=[6,3,5,4,6]，質(zhì)量w=[2,2,6,5,4]，則使用基于迭代的動(dòng)態(tài)規(guī)劃方法求解該0/1背包問題時(shí)，出現(xiàn)過（）等總價(jià)值的中間結(jié)果。

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

答案:40設(shè)M1,5=M1M2M3M4M5表示4個(gè)矩陣相乘，矩陣維度r=[10,5,1,10,2,10]，若使用動(dòng)態(tài)規(guī)劃方法求解該問題，則在填表求解過程中，可能會(huì)出現(xiàn)（）等中間過程結(jié)果。

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

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

答案:88計(jì)算機(jī)算法指的是（）。

答案:解決問題的有限運(yùn)算序列計(jì)算一個(gè)整數(shù)的完全平方根問題不屬于（）

答案:決策問題若使用基于迭代的動(dòng)態(tài)規(guī)劃方法計(jì)算n個(gè)長度為p字符串的最長公共子序列長度，則其時(shí)間復(fù)雜度和空間復(fù)雜分別為（）。

答案:若使用基于迭代的動(dòng)態(tài)規(guī)劃方法計(jì)算n個(gè)長度為p字符串的最長公共子序列長度，則其時(shí)間復(fù)雜度和空間復(fù)雜分別為（）。能夠用動(dòng)態(tài)規(guī)劃算法求解的問題一定屬于()

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

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

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

答案:錯(cuò)算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)。（）

答案:錯(cuò)算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止。（）

答案:對(duì)算法的時(shí)間復(fù)雜度取決于（）。

答案:待處理數(shù)據(jù)的初態(tài)；問題的規(guī)模算法的復(fù)雜性分析研究問題的實(shí)例編碼長度與復(fù)雜性的關(guān)系。（）

答案:對(duì)算法分析的兩個(gè)主要方面是時(shí)間復(fù)雜度和空間復(fù)雜度的分析。（）

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

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

答案:對(duì)用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。（）

答案:對(duì)用回溯法解批處理作業(yè)調(diào)度問題時(shí)，該問題的解空間結(jié)構(gòu)為子集樹結(jié)構(gòu)。（）

答案:錯(cuò)用回溯法求解最優(yōu)裝載問題時(shí)，若待選物品為m種，則該問題的解空間樹的結(jié)點(diǎn)個(gè)數(shù)為2m。（）

答案:錯(cuò)用分支限界法求解帶截止期的作業(yè)調(diào)度問題時(shí)，活動(dòng)節(jié)點(diǎn)的優(yōu)先級(jí)是按照什么來排列的？（）

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

答案:用不同方法解決0/1背包問題時(shí)，設(shè)背包容量為C，有n個(gè)物品，則其空間復(fù)雜度（僅考慮算法本身所產(chǎn)生的空間大小，不考慮用于存儲(chǔ)輸入與最終結(jié)果的空間）可能為（）?；顒?dòng)節(jié)點(diǎn)一旦成為擴(kuò)展節(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子節(jié)點(diǎn)。（）

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

答案:在一般情況下，分支限界法與回溯法的求解目標(biāo)不同；分支限界法與回溯法的搜索方式不同；分支限界法需要借助活動(dòng)節(jié)點(diǎn)表數(shù)據(jù)結(jié)構(gòu)，而回溯法則不需要；擴(kuò)展節(jié)點(diǎn)的擴(kuò)展方式不同某算法所需時(shí)間由以下方程表示，求出該算法時(shí)間復(fù)雜度（

）。

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

）。

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

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

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

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

答案:插入排序算法在最壞情況下的時(shí)間復(fù)雜度是（）?？焖倥判騿栴}屬于()

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

答案:快速排序算法在最好情況下的時(shí)間復(fù)雜度是（）?？焖倥判蛩惴ㄔ谧顗那闆r下的時(shí)間復(fù)雜度是（）。

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

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

答案:錯(cuò)對(duì)于非確定性算法，當(dāng)驗(yàn)證器對(duì)于實(shí)例w和證書c返回“False”時(shí)，說明算法對(duì)實(shí)例w無解。（）

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

答案:求解目標(biāo)不同；對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同；存儲(chǔ)空間的要求不同對(duì)于一個(gè)加權(quán)連通無向圖，在Kruskal’sMST(KrusKal’s最小生成樹)算法中,若使用最大隊(duì)列代替最小隊(duì)列，則可生成一個(gè)最大成本樹(而不是最小成本樹).()

答案:對(duì)如果問題的最優(yōu)解包含其子問題的最優(yōu)解，則稱該問題具備最優(yōu)子結(jié)構(gòu)性質(zhì)。（）

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

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

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

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

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

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

答案:回溯法在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。（）

答案:對(duì)在分支限界法中，每一個(gè)活動(dòng)節(jié)點(diǎn)只有兩次次機(jī)會(huì)成為擴(kuò)展節(jié)點(diǎn)。（）

答案:錯(cuò)在分支限界法中，是采用()的策略，依次生成擴(kuò)展節(jié)點(diǎn)的所有分支。

答案:廣度優(yōu)先在使用遞歸算法時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口，否則將無限進(jìn)行下去。（）

答案:對(duì)在使用動(dòng)態(tài)規(guī)劃方法解決實(shí)際問題時(shí)，應(yīng)盡量用迭代取代遞歸，并盡可能減少空間復(fù)雜度。（）

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

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

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

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

答案:無序樹回溯法的解（x1,x2,……,xn）的隱約束一般指個(gè)元素之間應(yīng)滿足的某種關(guān)系。（）

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

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

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

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

答案:錯(cuò)回溯法是指具有限界函數(shù)的深度優(yōu)先生成法。（）

答案:對(duì)回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。（）

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

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

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

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

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

答案:回溯法；分支限界法；動(dòng)態(tài)規(guī)劃法；貪心法動(dòng)態(tài)規(guī)劃的適用條件為無后效性、子問題相互獨(dú)立、最優(yōu)子結(jié)構(gòu)性質(zhì)。（）

答案:錯(cuò)動(dòng)態(tài)規(guī)劃的適用條件為（）。

答案:無后效性；子問題的重疊性；最優(yōu)子結(jié)構(gòu)性質(zhì)動(dòng)態(tài)規(guī)劃方法適合解決（）等問題。

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

答案:對(duì)分支限界法比回溯法更節(jié)省存儲(chǔ)空間。（）

答案:錯(cuò)分支限界法在問題的解空間樹中，按()策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。

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

答案:廣度優(yōu)先分支限界法和回溯法的區(qū)別中不包括（）

答案:解空間結(jié)構(gòu)分支限界法保留下來的活動(dòng)節(jié)點(diǎn)是有可能導(dǎo)致可行解或最優(yōu)解的節(jié)點(diǎn)，回溯法則不是。（）

答案:錯(cuò)分支限界法主要有哪幾種方式實(shí)現(xiàn)？（）

答案:FIFO隊(duì)列式；優(yōu)先隊(duì)列式分支限界法分支限界法中活動(dòng)節(jié)點(diǎn)可以多次擴(kuò)展。（）

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

答案:對(duì)分支限界法中，解空間組織成()結(jié)構(gòu)然后進(jìn)行搜索。

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

答案:對(duì)分支限界法一般更適合求解最優(yōu)化問題。（）

答案:對(duì)關(guān)于旅行商問題的說法，錯(cuò)誤的是（）

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

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

答案:回溯法中每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)關(guān)于動(dòng)態(tài)規(guī)劃的描述，正確的是（）。

答案:動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化解的一種常用算法思想；動(dòng)態(tài)規(guī)劃求解的問題必須滿足最優(yōu)化原理；動(dòng)態(tài)規(guī)劃得到的是精確解關(guān)于P類問題，下面敘述正確的是（）

答案:存在求解P類問題的算法，其復(fù)雜性的上界為多項(xiàng)式。關(guān)于NP類問題，下面敘述正確的是（）

答案:NP類問題一定包含P類問題。關(guān)于N-puzzle問題描述錯(cuò)誤的是（）

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

答案:錯(cuò)停機(jī)問題屬于NP難問題。（）

答案:錯(cuò)停機(jī)問題不屬于()

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

答案:錯(cuò)使用動(dòng)態(tài)規(guī)劃方法解決矩陣乘法鏈問題的時(shí)間復(fù)雜度和空間復(fù)雜度分別為（）。

答案:使用動(dòng)態(tài)規(guī)劃方法解決矩陣乘法鏈問題的時(shí)間復(fù)雜度和空間復(fù)雜度分別為（）。使用動(dòng)態(tài)規(guī)劃方法所解決的問題所應(yīng)該具有的性質(zhì)包括（）等。

答案:無后效性；子問題的重疊性優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展節(jié)點(diǎn)的原則是()

答案:節(jié)點(diǎn)的優(yōu)先級(jí)以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為（）。

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

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

答案:以下哪個(gè)選項(xiàng)是正確的（）以下可以用來描述算法的有？（）。

答案:文字?jǐn)⑹觯怀绦蛘Z句；偽代碼和流程圖令T是圖G的最小生成樹，那么對(duì)于任意點(diǎn)對(duì)s和t，圖G中從s到t的最短路徑也是T中從s到t的最短路.（）

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

答案:對(duì)不斷回頭尋找目標(biāo)的方法稱為（）。

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

答案:選擇排序下面算法時(shí)間復(fù)雜性為偽多項(xiàng)式的有（）

答案:下面算法時(shí)間復(fù)雜性為偽多項(xiàng)式的有（）下面的問題屬于NP問題的有（）

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

答案:在整個(gè)互聯(lián)網(wǎng)里，查找含有”NP問題”的網(wǎng)頁；漢諾塔問題下面的問題中，不屬于易解的問題有（）

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

答案:剪枝函數(shù)下述有關(guān)分支限界法搜索過程描述錯(cuò)誤的是（）

答案:搜索過程中，所有孩子節(jié)點(diǎn)已產(chǎn)生的節(jié)點(diǎn)稱為擴(kuò)展節(jié)點(diǎn)；搜索過程中，所有孩子節(jié)點(diǎn)已產(chǎn)生的節(jié)點(diǎn)稱為活動(dòng)節(jié)點(diǎn)下述有關(guān)分支限界法搜索過程描述正確的是（）

答案:當(dāng)解空間樹是一棵樹時(shí)，搜索從根節(jié)點(diǎn)開始；搜索過程中，擴(kuò)展節(jié)點(diǎn)一次性生成所有的孩子節(jié)點(diǎn)；搜索過程中，保留下來的孩子節(jié)點(diǎn)是可能導(dǎo)致可行解或最優(yōu)解的節(jié)點(diǎn)；搜索過程中，舍棄的孩子節(jié)點(diǎn)是導(dǎo)致不可行解和非最優(yōu)解的節(jié)點(diǎn)下述有關(guān)分支限界法搜索過程描述正確的是()

答案:搜索過程中，保留下來的孩子節(jié)點(diǎn)是可能導(dǎo)致可行解或最優(yōu)解的節(jié)點(diǎn)；搜索過程中，擴(kuò)展節(jié)點(diǎn)一次性生成所有的孩子節(jié)點(diǎn)；搜索過程中，保留下來的孩子節(jié)點(diǎn)是活動(dòng)節(jié)點(diǎn)，被插入活動(dòng)節(jié)點(diǎn)表中下述關(guān)于分支限界法的說法中，錯(cuò)誤的是（）

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

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

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

）。

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

答案:動(dòng)態(tài)規(guī)劃法下列排序算法的常規(guī)實(shí)現(xiàn)中，哪些空間復(fù)雜度是O(1)：（）。

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

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

答案:O(Nlog2N)；O(1)下列函數(shù)中漸進(jìn)時(shí)間復(fù)雜度相同的是（）

答案:下列函數(shù)中漸進(jìn)時(shí)間復(fù)雜度相同的是（）下列函數(shù)中漸近時(shí)間復(fù)雜度最小的是（）

答案:下列函數(shù)中漸近時(shí)間復(fù)雜度最小的是（）下列函數(shù)中漸近時(shí)間復(fù)雜度最大的是（）

答案:下列函數(shù)中漸近時(shí)間復(fù)雜度最大的是（）下列關(guān)于效率的說法正確的是（）。

答案:效率是一個(gè)性能要求，其目標(biāo)應(yīng)該在需求分析時(shí)給出；提高程序效率的根本途徑在于選擇良好的設(shè)計(jì)方法，數(shù)據(jù)結(jié)構(gòu)與算法；效率主要指處理機(jī)時(shí)間和存儲(chǔ)器容量兩個(gè)方面下列代碼的時(shí)間復(fù)雜度是（

）。

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

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

答案:對(duì)一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（）。

答案:最優(yōu)子結(jié)構(gòu)性質(zhì)一個(gè)連通圖中具有最小權(quán)重的邊，必定被包含在圖的最小生成樹中。()

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

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

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