算法設(shè)計與分析知到智慧樹章節(jié)測試課后答案2024年秋天津大學VIP

算法設(shè)計與分析知到智慧樹章節(jié)測試課后答案2024年秋天津大學第一章單元測試

下列關(guān)于效率的說法正確的是（）。

A:效率主要指處理機時間和存儲器容量兩個方面

B:提高程序效率的根本途徑在于選擇良好的設(shè)計方法，數(shù)據(jù)結(jié)構(gòu)與算法

C:效率是一個性能要求，其目標應(yīng)該在需求分析時給出

D:程序的效率與程序的長度強相關(guān)

答案:效率主要指處理機時間和存儲器容量兩個方面

；提高程序效率的根本途徑在于選擇良好的設(shè)計方法，數(shù)據(jù)結(jié)構(gòu)與算法

；效率是一個性能要求，其目標應(yīng)該在需求分析時給出

算法的時間復(fù)雜度取決于（）。

A:硬盤容量

B:問題的規(guī)模

C:待處理數(shù)據(jù)的初態(tài)

D:計算機性能

答案:問題的規(guī)模

；待處理數(shù)據(jù)的初態(tài)

計算機算法指的是（）。

A:排序方法

B:解決問題的有限運算序列

C:調(diào)度方法

D:計算方法

答案:解決問題的有限運算序列

歸并排序法的時間復(fù)雜度和空間復(fù)雜度分別是（）。

A:O(n)

B:O(n2)

C:O(nlog2n)

D:O(1)

答案:O(n)

；O(nlog2n)

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

A:錯B:對

答案:錯用漸進表示法分析算法復(fù)雜度的增長趨勢。（）

A:錯B:對

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

A:錯B:對

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

）。

A:O(n)B:O(log2n)C:O(n2)D:O(nlog2n)

答案:O(nlog2n)下列代碼的時間復(fù)雜度是（

）。

A:O(N)B:O(1)C:O(log3N)D:O(log2N)

答案:O(log2N)下列算法為在數(shù)組A[0,...,n-1]中找出最大值和最小值的元素，其平均比較次數(shù)為（

）。

A:3n/2B:

n-3/2C:3n/2-3/2D:

2n-1

答案:3n/2-3/2

第二章單元測試

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

A:T(n)=aT(n/b)+f(n),a≥1,b＞1,為整數(shù),f(n)＞0.

B:T(n)=T(n-a)+T(n-b)+f(n)，a≥1,b＞1

C:T(n)=T(n-a)+T(a)+f(n)，a≥1

D:T(n)=T(n/a)+T(n/b)+f(n)，a≥1,b＞1

答案:T(n)=aT(n/b)+f(n),a≥1,b＞1,為整數(shù),f(n)＞0.

A:對B:錯

答案:對假定，,遞歸方程的解是.()

A:對B:錯

答案:對假設(shè)數(shù)組A包含n個不同的元素，需要從數(shù)組A中找出n/2個元素，要求所找的n/2個元素的中點元素也是數(shù)組A的中點元素。針對該問題的任何算法需要的時間復(fù)雜度的下限必為。()

A:錯B:對

答案:錯使用Master方法求解遞歸方程的解為（）.

A:

B:

C:

D:

答案:

考慮包含n個二維坐標點的集合S，其中n為偶數(shù)，且所有坐標點中的均不相同。一條豎直的直線若能把S集合分成左右兩部分坐標點個數(shù)相同的子集合，則稱直線L為集合S的一條分界線。若給定集合S，則可在時間內(nèi)找到這條分界線L。()

A:錯B:對

答案:對

A:

B:

C:

D:

答案:

從n個數(shù)中找出前k個最小的元素并對所選擇的前k個最小的元素進行排序。使用歸并排序算法將這n個數(shù)進行排序的時間復(fù)雜度為，從排好序的數(shù)組中提取有序的k個最小數(shù)的時間復(fù)雜度為，因此總的運行時間復(fù)雜度為.()

A:對B:錯

答案:對假定問題對于規(guī)模為n的所有不同輸入，存在一個分治算法其平均時間復(fù)雜度為，則算法在最壞情形下的時間復(fù)雜度可能為（）

A:錯B:對

答案:對使用分治算法求解最大最小問題。假定問題的規(guī)模,每次將問題分成規(guī)模接近的兩個子問題，遞歸地對子問題求解并將子問題的解合并得到大問題的解，該分治算法的復(fù)雜度函數(shù)可寫為()

A:

B:

C:

D:,

答案:

第三章單元測試

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

A:錯B:對

答案:錯令是一個加權(quán)圖，令T是G的最小生成樹，則T中任意兩個頂點和之間的路徑必定是圖G中該兩點之間的最短路徑。()

A:對B:錯

答案:錯對于一個加權(quán)連通無向圖，在Kruskal’sMST(KrusKal’s最小生成樹)算法中,若使用最大隊列代替最小隊列，則可生成一個最大成本樹(而不是最小成本樹).()

A:對B:錯

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

A:問題可分為相互獨立的子問題

B:滿足貪心選擇性質(zhì)

C:滿足最優(yōu)子結(jié)構(gòu)性質(zhì)

D:子問題的解相互獨立

答案:滿足貪心選擇性質(zhì)

；滿足最優(yōu)子結(jié)構(gòu)性質(zhì)

0/1背包問題是NP-hard問題，任何求解0/1背包問題的貪心算法都不能保證得到該問題的最優(yōu)解。（）

A:錯B:對

答案:對一個連通圖中具有最小權(quán)重的邊，必定被包含在圖的最小生成樹中。()

A:錯B:對

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

A:錯B:對

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

A:錯B:對

答案:對貪心算法是一種自頂向下的求解方法，分步做出貪心選擇，逐步將問題變成規(guī)模較小的問題求解。（）

A:錯B:對

答案:對下列問題可使用貪心算法求得最優(yōu)解的是（）.

A:集合覆蓋問題

B:0/1背包問題

C:貨箱裝載問題

D:偶圖覆蓋問題

答案:貨箱裝載問題

第四章單元測試

動態(tài)規(guī)劃的適用條件為（）。

A:最優(yōu)子結(jié)構(gòu)性質(zhì)

B:子問題的重疊性

C:無后效性

D:子問題相互獨立

答案:最優(yōu)子結(jié)構(gòu)性質(zhì)

；子問題的重疊性

；無后效性

（1）計算動態(tài)規(guī)劃數(shù)組；（2）確定動態(tài)規(guī)劃函數(shù)；（3）構(gòu)造最優(yōu)解；（4）定義子問題。動態(tài)規(guī)劃一般可以將步驟依次劃分為：（）。

A:（4）（1）（2）（3）

B:（4）（3）（1）（2）

C:（4）（2）（1）（3）

D:（3）（4）（2）（1）

答案:（4）（2）（1）（3）

使用動態(tài)規(guī)劃方法解決0/1背包問題，設(shè)V(i,j)表示將前i(1≤i≤n)個物品裝入容量為j(1≤j≤C)的背包獲得的最大價值，在決策其動態(tài)規(guī)劃函數(shù)為：

，。（）

A:錯B:對

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

A:[1,0,0,1,1]

B:[1,1,0,0,1]

C:[1,0,0,0,1]

D:[0,0,1,1,0]

答案:[1,1,0,0,1]

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

A:44

B:88

C:40

D:80

答案:88

使用動態(tài)規(guī)劃方法解決矩陣乘法鏈問題的時間復(fù)雜度和空間復(fù)雜度分別為（）。

A:

B:

C:

D:

答案:

設(shè)有有向加權(quán)圖如下圖所示，每兩對點之間的最短路徑長度（）。

A:

B:

C:

D:

答案:

設(shè)有有向加權(quán)圖如下圖所示，起點0點與其他點之間的最短路徑長度（）。

A:

B:

C:

D:

答案:

設(shè)有一個網(wǎng)(i,Ci)如下圖所示，則滿足i≤5且Ci≤7的最大不交叉網(wǎng)子集有（）個。

A:4

B:1

C:2

D:3

答案:2

有字符串a(chǎn)=ABCB,b=BDCA，則使用動態(tài)規(guī)劃方法求解a與b的最長公共子序列時，下表X處的值為()。

A:-1

B:2

C:1

D:0

答案:2

第五章單元測試

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

A:對B:錯

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

A:錯B:對

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

A:對B:錯

答案:錯在對問題的解空間樹進行搜索的方法中，一個結(jié)點有多次機會成為活結(jié)點的是（）。

A:分支限界法

B:回溯法

C:動態(tài)規(guī)劃

D:回溯法和分支限界法

答案:回溯法

回溯法在解空間樹T上的搜索方式是（）。

A:廣度優(yōu)先

B:活結(jié)點優(yōu)先

C:最小耗費優(yōu)先

D:深度優(yōu)先

答案:深度優(yōu)先

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

A:無序樹

B:有序樹

C:排列樹

D:子集樹

答案:無序樹

回溯法求問題的所有解時，要回溯到根，且根結(jié)點的子樹都要已被搜索遍才結(jié)束。（）

A:對B:錯

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

A:貨箱裝船問題

B:N皇后問題

C:旅行商問題

D:0/1背包問題

答案:貨箱裝船問題

；N皇后問題

；旅行商問題

；0/1背包問題

回溯法的效率不依賴于以下哪一個因素？（）

A:問題的解空間的形式

B:計算上界函數(shù)bound的時間

C:滿足顯約束的x[k]值的個數(shù)

D:產(chǎn)生x[k]的時間

答案:問題的解空間的形式

用回溯法解圖的m著色問題時，使用下面的函數(shù)OK檢查當前擴展結(jié)點的每一個兒子所相應(yīng)的顏色的可用性，則需耗時（漸進時間上限）（）。

A:O(m)

B:O(n)

C:O(m2)

D:O(mn)

答案:O(mn)

第六章單元測試

分支限界法中，解空間組織成()結(jié)構(gòu)然后進行搜索。

A:鏈表B:樹C:堆棧

D:數(shù)組

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

A:廣度優(yōu)先B:深度優(yōu)先

C:擴展節(jié)點優(yōu)先D:活動節(jié)點優(yōu)先

答案:廣度優(yōu)先優(yōu)先隊列式分支限界法選取擴展節(jié)點的原則是()

A:隨機

B:節(jié)點的優(yōu)先級C:先進先出D:后進后出

答案:節(jié)點的優(yōu)先級分支限界法主要有哪幾種方式實現(xiàn)？（）

A:堆棧式分支限界法

B:FIFO隊列式

C:優(yōu)先隊列式分支限界法

D:廣度優(yōu)先分支限界法

答案:FIFO隊列式

；優(yōu)先隊列式分支限界法

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

A:分支限界法與回溯法的搜索方式不同

B:分支限界法需要借助活動節(jié)點表數(shù)據(jù)結(jié)構(gòu)，而回溯法則不需要

C:在一般情況下，分支限界法與回溯法的求解目標不同

D:擴展節(jié)點的擴展方式不同

答案:分支限界法與回溯法的搜索方式不同

；分支限界法需要借助活動節(jié)點表數(shù)據(jù)結(jié)構(gòu)，而回溯法則不需要

；在一般情況下，分支限界法與回溯法的求解目標不同

；擴展節(jié)點的擴展方式不同

下述有關(guān)分支限界法搜索過程描述正確的是()

A:搜索過程中，保留下來的孩子節(jié)點是活動節(jié)點，被插入活動節(jié)點表中

B:必須當活動節(jié)點表為空時，算法才算結(jié)束

C:搜索過程中，擴展節(jié)點一次性生成所有的孩子節(jié)點

D:搜索過程中，保留下來的孩子節(jié)點是可能導致可行解或最優(yōu)解的節(jié)點

答案:搜索過程中，保留下來的孩子節(jié)點是活動節(jié)點，被插入活動節(jié)點表中

；搜索過程中，擴展節(jié)點一次性生成所有的孩子節(jié)點

；搜索過程中，保留下來的孩子節(jié)點是可能導致可行解或最優(yōu)解的節(jié)點

分支限界法保留下來的活動節(jié)點是有可能導致可行解或最優(yōu)解的節(jié)點，回溯法則不是。（）

A:對B:錯

答案:錯分支限界法中活動節(jié)點可以多次擴展。（）

A:對B:錯

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

A:對B:錯

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

A:對B:錯

答案:對

第七章單元測試

快速排序問題屬于()

A:NP難問題

B:難解問題C:易解問題D:不可解問題

答案:易解問題能夠用動態(tài)規(guī)劃算法求解的問題一定屬于()

A:NP難問題

B:NP問題C:難解問題D:易解問題

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

A:難解問題B:決策問題C:不可計算問題D:NP難問題

答案:NP難問題

下面的問題屬于NP問題的有（）

A:矩陣乘法鏈問題

B:找出圖中所有點對的最短路徑問題

C:計算兩個正整數(shù)的最大公約數(shù)

D:定理識別問題

答案:矩陣乘法鏈問題

；找出圖中所有點對的最短路徑問題

；計算兩個正整數(shù)的最大公約數(shù)

NP完全題可能屬于()

A:P類問題

B:難解問題

C:NP類問題

D:NP難問題

答案:P類問題

；NP類問題

；NP難問題

關(guān)于多項式規(guī)約，下面敘述正確的是()

A:所有的NPC問題都可以多項式地規(guī)約到NP難問題

B:所有的P