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

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

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

A:效率主要指處理機(jī)時(shí)間和存儲(chǔ)器容量?jī)蓚€(gè)方面

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

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

D:程序的效率與程序的長(zhǎng)度強(qiáng)相關(guān)

答案:效率主要指處理機(jī)時(shí)間和存儲(chǔ)器容量?jī)蓚€(gè)方面

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

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

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

A:硬盤(pán)容量

B:問(wèn)題的規(guī)模

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

D:計(jì)算機(jī)性能

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

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

計(jì)算機(jī)算法指的是（）。

A:排序方法

B:解決問(wèn)題的有限運(yùn)算序列

C:調(diào)度方法

D:計(jì)算方法

答案:解決問(wèn)題的有限運(yùn)算序列

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

A:O(n)

B:O(n2)

C:O(nlog2n)

D:O(1)

答案:O(n)

；O(nlog2n)

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

A:錯(cuò)B:對(duì)

答案:錯(cuò)用漸進(jìn)表示法分析算法復(fù)雜度的增長(zhǎng)趨勢(shì)。（）

A:錯(cuò)B:對(duì)

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

A:錯(cuò)B:對(duì)

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

）。

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

答案:O(nlog2n)下列代碼的時(shí)間復(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

第二章單元測(cè)試

可用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:對(duì)B:錯(cuò)

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

A:對(duì)B:錯(cuò)

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

A:錯(cuò)B:對(duì)

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

A:

B:

C:

D:

答案:

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

A:錯(cuò)B:對(duì)

答案:對(duì)

A:

B:

C:

D:

答案:

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

A:對(duì)B:錯(cuò)

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

A:錯(cuò)B:對(duì)

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

A:

B:

C:

D:,

答案:

第三章單元測(cè)試

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

A:錯(cuò)B:對(duì)

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

A:對(duì)B:錯(cuò)

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

A:對(duì)B:錯(cuò)

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

A:問(wèn)題可分為相互獨(dú)立的子問(wèn)題

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

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

D:子問(wèn)題的解相互獨(dú)立

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

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

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

A:錯(cuò)B:對(duì)

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

A:錯(cuò)B:對(duì)

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

A:錯(cuò)B:對(duì)

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

A:錯(cuò)B:對(duì)

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

A:錯(cuò)B:對(duì)

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

A:集合覆蓋問(wèn)題

B:0/1背包問(wèn)題

C:貨箱裝載問(wèn)題

D:偶圖覆蓋問(wèn)題

答案:貨箱裝載問(wèn)題

第四章單元測(cè)試

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

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

B:子問(wèn)題的重疊性

C:無(wú)后效性

D:子問(wèn)題相互獨(dú)立

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

；子問(wèn)題的重疊性

；無(wú)后效性

（1）計(jì)算動(dòng)態(tài)規(guī)劃數(shù)組；（2）確定動(dòng)態(tài)規(guī)劃函數(shù)；（3）構(gòu)造最優(yōu)解；（4）定義子問(wèn)題。動(dòng)態(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）

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

，。（）

A:錯(cuò)B:對(duì)

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

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個(gè)矩陣相乘，矩陣維度r1=2,r2=10,r3=2,r4=10,r5=2，則鏈乘的最少次數(shù)是（）。

A:44

B:88

C:40

D:80

答案:88

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

A:

B:

C:

D:

答案:

設(shè)有有向加權(quán)圖如下圖所示，每?jī)蓪?duì)點(diǎn)之間的最短路徑長(zhǎng)度（）。

A:

B:

C:

D:

答案:

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

A:

B:

C:

D:

答案:

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

A:4

B:1

C:2

D:3

答案:2

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

A:-1

B:2

C:1

D:0

答案:2

第五章單元測(cè)試

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

A:對(duì)B:錯(cuò)

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

A:錯(cuò)B:對(duì)

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)的是（）。

A:分支限界法

B:回溯法

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

D:回溯法和分支限界法

答案:回溯法

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

A:廣度優(yōu)先

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

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

D:深度優(yōu)先

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

回溯算法和分支限界法的問(wèn)題的解空間樹(shù)不會(huì)是（）。

A:無(wú)序樹(shù)

B:有序樹(shù)

C:排列樹(shù)

D:子集樹(shù)

答案:無(wú)序樹(shù)

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)下列問(wèn)題中可以用回溯算法解決的是？（）

A:貨箱裝船問(wèn)題

B:N皇后問(wèn)題

C:旅行商問(wèn)題

D:0/1背包問(wèn)題

答案:貨箱裝船問(wèn)題

；N皇后問(wèn)題

；旅行商問(wèn)題

；0/1背包問(wèn)題

回溯法的效率不依賴(lài)于以下哪一個(gè)因素？（）

A:問(wèn)題的解空間的形式

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

C:滿(mǎn)足顯約束的x[k]值的個(gè)數(shù)

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

答案:問(wèn)題的解空間的形式

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

A:O(m)

B:O(n)

C:O(m2)

D:O(mn)

答案:O(mn)

第六章單元測(cè)試

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

A:鏈表B:樹(shù)C:堆棧

D:數(shù)組

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

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

C:擴(kuò)展節(jié)點(diǎn)優(yōu)先D:活動(dòng)節(jié)點(diǎn)優(yōu)先

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

A:隨機(jī)

B:節(jié)點(diǎn)的優(yōu)先級(jí)C:先進(jìn)先出D:后進(jìn)后出

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

A:堆棧式分支限界法

B:FIFO隊(duì)列式

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

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

答案:FIFO隊(duì)列式

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

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

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

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

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

D:擴(kuò)展節(jié)點(diǎn)的擴(kuò)展方式不同

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

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

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

；擴(kuò)展節(jié)點(diǎn)的擴(kuò)展方式不同

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

A:搜索過(guò)程中，保留下來(lái)的孩子節(jié)點(diǎn)是活動(dòng)節(jié)點(diǎn)，被插入活動(dòng)節(jié)點(diǎn)表中

B:必須當(dāng)活動(dòng)節(jié)點(diǎn)表為空時(shí)，算法才算結(jié)束

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

D:搜索過(guò)程中，保留下來(lái)的孩子節(jié)點(diǎn)是可能導(dǎo)致可行解或最優(yōu)解的節(jié)點(diǎn)

答案:搜索過(guò)程中，保留下來(lái)的孩子節(jié)點(diǎn)是活動(dòng)節(jié)點(diǎn)，被插入活動(dòng)節(jié)點(diǎn)表中

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

；搜索過(guò)程中，保留下來(lái)的孩子節(jié)點(diǎn)是可能導(dǎo)致可行解或最優(yōu)解的節(jié)點(diǎn)

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

A:對(duì)B:錯(cuò)

答案:錯(cuò)分支限界法中活動(dòng)節(jié)點(diǎn)可以多次擴(kuò)展。（）

A:對(duì)B:錯(cuò)

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

A:對(duì)B:錯(cuò)

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

A:對(duì)B:錯(cuò)

答案:對(duì)

第七章單元測(cè)試

快速排序問(wèn)題屬于()

A:NP難問(wèn)題

B:難解問(wèn)題C:易解問(wèn)題D:不可解問(wèn)題

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

A:NP難問(wèn)題

B:NP問(wèn)題C:難解問(wèn)題D:易解問(wèn)題

答案:NP問(wèn)題停機(jī)問(wèn)題不屬于()

A:難解問(wèn)題B:決策問(wèn)題C:不可計(jì)算問(wèn)題D:NP難問(wèn)題

答案:NP難問(wèn)題

下面的問(wèn)題屬于NP問(wèn)題的有（）

A:矩陣乘法鏈問(wèn)題

B:找出圖中所有點(diǎn)對(duì)的最短路徑問(wèn)題

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

D:定理識(shí)別問(wèn)題

答案:矩陣乘法鏈問(wèn)題

；找出圖中所有點(diǎn)對(duì)的最短路徑問(wèn)題

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

NP完全題可能屬于()

A:P類(lèi)問(wèn)題

B:難解問(wèn)題

C:NP類(lèi)問(wèn)題

D:NP難問(wèn)題

答案:P類(lèi)問(wèn)題

；NP類(lèi)問(wèn)題

；NP難問(wèn)題

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

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

B:所有的P