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

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

程序運(yùn)行結(jié)果往往與輸入相關(guān)，所以程序可以不滿足確定性（）

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

答案:錯(cuò)有關(guān)算法分析的事后統(tǒng)計(jì)法正確的是（）。

A:從理論上講，在各種軟硬件環(huán)境下進(jìn)行算法測(cè)試，得到的資源耗費(fèi)都是一樣的。

B:測(cè)試的結(jié)果與程序的編譯和運(yùn)行環(huán)境有關(guān)

C:結(jié)果與測(cè)試的樣本數(shù)據(jù)有關(guān)

D:結(jié)果是面向機(jī)器，面向程序員，面向語(yǔ)言的

答案:測(cè)試的結(jié)果與程序的編譯和運(yùn)行環(huán)境有關(guān)

；結(jié)果與測(cè)試的樣本數(shù)據(jù)有關(guān)

；結(jié)果是面向機(jī)器，面向程序員，面向語(yǔ)言的

下面哪些內(nèi)容是算法設(shè)計(jì)之前要完成的內(nèi)容?()

A:確定合適的數(shù)據(jù)結(jié)構(gòu)

B:使用何種計(jì)算機(jī)語(yǔ)言設(shè)計(jì)程序

C:證明算法的正確性。

D:是求精確解還是近似解

答案:確定合適的數(shù)據(jù)結(jié)構(gòu)

；是求精確解還是近似解

函數(shù)10logn3+5logn2的漸近表達(dá)式為（）：

A:O(logn3)B:O(nlogn)C:O（logn2）D:O(logn)

答案:O(logn)

下列函數(shù)根據(jù)漸近階從低到高順序是（）

A:logn＜n1/2＜2n＜n3＜n!＜3n

B:logn＜n1/2＜2n＜n3＜3n＜n!C:n1/2＜logn＜2n＜n3＜3n＜n!D:n1/2＜logn＜2n＜n3＜n!＜3n

答案:logn＜n1/2＜2n＜n3＜3n＜n!研究NPC問(wèn)題的意義:一旦某個(gè)NPC問(wèn)題找到了多項(xiàng)式時(shí)間復(fù)雜性的算法，那么所有的NP問(wèn)題都找到了多項(xiàng)式時(shí)間算法。()

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

答案:對(duì)

第二章單元測(cè)試

直接或間接的調(diào)用自身的算法稱為（）。

A:遞歸算法

B:動(dòng)態(tài)規(guī)劃算法

C:貪心算法

D:迭代算法

答案:遞歸算法

Hanoi塔問(wèn)題如下圖所示?，F(xiàn)要求將塔座A上的的所有圓盤(pán)移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤(pán)時(shí)遵守Hanoi塔問(wèn)題的移動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法正確的為：（）

A:

B:

C:

D:

答案:

分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問(wèn)題分割成規(guī)模較小的子問(wèn)題分別解決子問(wèn)題最后將子問(wèn)題的解組合起來(lái)形成原問(wèn)題的解。這要求原問(wèn)題和子問(wèn)題（）。

A:問(wèn)題規(guī)模不同，問(wèn)題性質(zhì)不同

B:問(wèn)題規(guī)模不同，問(wèn)題性質(zhì)相同

C:問(wèn)題規(guī)模相同，問(wèn)題性質(zhì)不同

D:問(wèn)題規(guī)模相同，問(wèn)題性質(zhì)相同

答案:問(wèn)題規(guī)模不同，問(wèn)題性質(zhì)相同

利用二分搜索，最壞情況下的計(jì)算時(shí)間復(fù)雜性為（）。

A:O(logn)B:O（n）C:O(n2)D:O(2n)

答案:O(logn)二分搜索算法只適用（）存儲(chǔ)結(jié)構(gòu)。

A:堆B:任意順序C:順序D:棧

答案:順序使用二分搜索算法在1000個(gè)有序元素表中搜索一個(gè)特定元素，在最壞情況下，搜索總共需要比較的次數(shù)為（）。

A:1000

B:500C:11D:10

答案:10線性時(shí)間選擇的時(shí)間復(fù)雜度為（）。

A:O(logn)B:O(n2)C:O(n)

D:O（nlogn）

答案:O(n)

利用合并排序，其輔助空間為（）：

A:O（n）B:O(logn)C:O(n2)D:O(nlogn)

答案:O（n）利用快速排序，對(duì)數(shù)的序列{16,27,13,2,15,38}，選擇基準(zhǔn)16，進(jìn)行一次劃分，結(jié)果為（）：

A:{15,13,2}16{27,38}

B:{13,2,15}16{27,38}

C:{13,2,15}16{38,27}

D:{2,13,15}16{38,27}

答案:{13,2,15}16{27,38}

分治策略解決棋盤(pán)覆蓋問(wèn)題是一個(gè)漸近意義下最優(yōu)的算法.（）

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

答案:對(duì)

第三章單元測(cè)試

設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，若xm=yn則（）。

A:zk≠xm=yn，且zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。

B:zk≠xm=yn，且zk是Xm-1和Yn-1的最長(zhǎng)公共子序列。

C:zk=xm=yn，且zk是Xm-1和Yn-1的最長(zhǎng)公共子序列。

D:zk=xm=yn，且zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。

答案:zk=xm=yn，且zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。

當(dāng)(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10)=(-1,5,-2,1,-7,-4,2,3,-1,2)時(shí)，最大子段和為().

A:10B:6C:9

D:7

答案:6設(shè)有四個(gè)矩陣A,B,C,D,它們的維數(shù)分別是A=50*10,B=10*40,C=40*30,D=30*50,，則計(jì)算其乘積至少需要（）次乘法

A:87500

B:10500,C:16000,D:36000,

答案:10500,下面關(guān)于動(dòng)態(tài)規(guī)劃解題的步驟內(nèi)容描述正確的是哪些？（）

A:建立遞歸關(guān)系：建立關(guān)于問(wèn)題最優(yōu)值的遞歸定義，即問(wèn)題的最優(yōu)值通過(guò)子問(wèn)題的最優(yōu)值合并得到。

B:構(gòu)造最優(yōu)解：根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問(wèn)題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造。

C:計(jì)算最優(yōu)值：以自頂往下的方法計(jì)算問(wèn)題的最優(yōu)值，也就是先求解規(guī)模較大的問(wèn)題的最優(yōu)值。

D:分析最優(yōu)解的結(jié)構(gòu)：將一個(gè)一般化問(wèn)題可以分解為幾個(gè)性質(zhì)相同的子問(wèn)題，并且問(wèn)題的最優(yōu)解可以通過(guò)子問(wèn)題的最優(yōu)解合并得到，也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。

答案:建立遞歸關(guān)系：建立關(guān)于問(wèn)題最優(yōu)值的遞歸定義，即問(wèn)題的最優(yōu)值通過(guò)子問(wèn)題的最優(yōu)值合并得到。

；構(gòu)造最優(yōu)解：根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問(wèn)題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造。

；分析最優(yōu)解的結(jié)構(gòu)：將一個(gè)一般化問(wèn)題可以分解為幾個(gè)性質(zhì)相同的子問(wèn)題，并且問(wèn)題的最優(yōu)解可以通過(guò)子問(wèn)題的最優(yōu)解合并得到，也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。

問(wèn)題用動(dòng)態(tài)規(guī)劃算法求解效率較高的原因？()

A:貪心選擇性質(zhì)B:最優(yōu)子結(jié)構(gòu)性質(zhì)C:子問(wèn)題重疊性質(zhì)D:遞歸性質(zhì).

答案:子問(wèn)題重疊性質(zhì)對(duì)0-1背包問(wèn)題，n=5，c=12，w={3,7,5,4，4}，v={6,3,5,4，6}，則其最優(yōu)解為（）

A:（0，1，0，1，1）B:（1，0，1，0，1）

C:（1，1，1，1，1）

D:（0，1，1，1，1）

答案:（1，0，1，0，1）

一般來(lái)說(shuō)解同一個(gè)問(wèn)題，動(dòng)態(tài)規(guī)劃法的效率高于分治算法（）

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

答案:錯(cuò)圖象的變位壓縮存儲(chǔ)采用數(shù)據(jù)頭和數(shù)據(jù)存儲(chǔ)的編碼式存儲(chǔ)方式，節(jié)省存儲(chǔ)空間，實(shí)現(xiàn)壓縮。（）

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

答案:對(duì)

第四章單元測(cè)試

在某通訊系統(tǒng)中用到了a，b，c，d，e，f8個(gè)字符，字符頻度（百分比）為45，13，12，16，9，5則字符a的編碼為()：

A:0B:.111C:1100

答案:0活動(dòng)安排問(wèn)題利用貪心法求解，則其復(fù)雜度為（）

A:O(nlogn)B:O(logn)

C:O(n)D:O(n2)

答案:O(nlogn)在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。()

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

答案:對(duì)背包問(wèn)題與0-1背包問(wèn)題求解方法類似，都能用貪心法或動(dòng)態(tài)規(guī)劃方法得到最優(yōu)解（）

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

答案:錯(cuò)有關(guān)分治法、貪心算法和動(dòng)態(tài)規(guī)劃算法的描述，正確的是（）

A:問(wèn)題能用動(dòng)態(tài)規(guī)劃法解的不一定能用貪心算法解；

B:適用三種方法所解的問(wèn)題都是可分解成子問(wèn)題的；

C:用貪心法一定能用動(dòng)態(tài)規(guī)劃法，但是，動(dòng)態(tài)規(guī)劃法的效率一般高于貪心算法。

D:貪心算法和動(dòng)態(tài)規(guī)劃算法共同特征為最優(yōu)子結(jié)構(gòu)性質(zhì);

答案:問(wèn)題能用動(dòng)態(tài)規(guī)劃法解的不一定能用貪心算法解；

；適用三種方法所解的問(wèn)題都是可分解成子問(wèn)題的；

；貪心算法和動(dòng)態(tài)規(guī)劃算法共同特征為最優(yōu)子結(jié)構(gòu)性質(zhì);

下列哪些問(wèn)題能適用貪心法高效求解？（）

A:最小生成樹(shù)問(wèn)題

B:0-1背包問(wèn)題C:哈夫曼編碼問(wèn)題D:單源最短路徑問(wèn)題

答案:最小生成樹(shù)問(wèn)題

；哈夫曼編碼問(wèn)題；單源最短路徑問(wèn)題

第五章單元測(cè)試

使用回溯法求解0-1背包問(wèn)題時(shí)，計(jì)算右子樹(shù)上界的方法是通過(guò)貪心策略求得上界（）

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

答案:對(duì)適用回溯法解旅行售貨員問(wèn)題，只有當(dāng)搜索到最后一個(gè)城市時(shí)，才能判斷當(dāng)前路徑是否是該問(wèn)題的一個(gè)解。（）

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

答案:錯(cuò)下面關(guān)于用回溯法解題說(shuō)法，正確的是().

A:這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。

B:解空間樹(shù)有子集樹(shù)與排列樹(shù)兩種;

C:顯式地存儲(chǔ)整個(gè)解空間；

D:在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間；

答案:這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。

；解空間樹(shù)有子集樹(shù)與排列樹(shù)兩種;

；在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間；

回溯法中的剪枝函數(shù)包括()。

A:隨機(jī)數(shù)生成函數(shù)

B:約束函數(shù)

C:限界函數(shù)

D:遞歸函數(shù)

答案:約束函數(shù)

；限界函數(shù)

回溯法解題步驟,正確的是（）

A:確定易于搜索的解空間結(jié)構(gòu);

B:以深度優(yōu)先方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索;

C:確定最優(yōu)子結(jié)構(gòu)的性質(zhì);

D:針對(duì)所給問(wèn)題，定義問(wèn)題的解空間;

答案:確定易于搜索的解空間結(jié)構(gòu);

；以深度優(yōu)先方式搜索解空間，在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索;

；針對(duì)所給問(wèn)題，定義問(wèn)題的解空間;

四色定理是第一個(gè)主要由計(jì)算機(jī)證明的理論（）

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

答案:對(duì)

第六章單元測(cè)試

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

A:回溯法求解子集樹(shù)問(wèn)題B:回溯法C:回溯法和分支限界法

D:分支限界法

答案:分支限界法分支限界法與回溯