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

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

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

A:錯(cuò)B:對

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

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

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

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

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

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

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

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

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

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

B:使用何種計(jì)算機(jī)語言設(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問題的意義:一旦某個(gè)NPC問題找到了多項(xiàng)式時(shí)間復(fù)雜性的算法，那么所有的NP問題都找到了多項(xiàng)式時(shí)間算法。()

A:錯(cuò)B:對

答案:對

第二章單元測試

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

A:遞歸算法

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

C:貪心算法

D:迭代算法

答案:遞歸算法

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

A:

B:

C:

D:

答案:

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

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

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

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

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

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

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

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

答案:O(logn)二分搜索算法只適用（）存儲結(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）利用快速排序，對數(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}

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

A:錯(cuò)B:對

答案:對

第三章單元測試

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

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

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

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

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

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

當(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)于動態(tài)規(guī)劃解題的步驟內(nèi)容描述正確的是哪些？（）

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

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

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

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

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

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

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

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

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

答案:子問題重疊性質(zhì)對0-1背包問題，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）

一般來說解同一個(gè)問題，動態(tài)規(guī)劃法的效率高于分治算法（）

A:錯(cuò)B:對

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

A:錯(cuò)B:對

答案:對

第四章單元測試

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

A:0B:.111C:1100

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

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

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

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

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

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

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

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

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

；適用三種方法所解的問題都是可分解成子問題的；

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

下列哪些問題能適用貪心法高效求解？（）

A:最小生成樹問題

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

答案:最小生成樹問題

；哈夫曼編碼問題；單源最短路徑問題

第五章單元測試

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

A:錯(cuò)B:對

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

A:錯(cuò)B:對

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

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

B:解空間樹有子集樹與排列樹兩種;

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

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

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

；解空間樹有子集樹與排列樹兩種;

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

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

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

B:約束函數(shù)

C:限界函數(shù)

D:遞歸函數(shù)

答案:約束函數(shù)

；限界函數(shù)

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

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

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

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

D:針對所給問題，定義問題的解空間;

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

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

；針對所給問題，定義問題的解空間;

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

A:對B:錯(cuò)

答案:對

第六章單元測試

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

A:回溯法求解子集樹問題B:回溯法C:回溯法和分支限界法

D:分支限界法

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