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

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

程序運行結果往往與輸入相關，所以程序可以不滿足確定性（）

A:錯B:對

答案:錯有關算法分析的事后統(tǒng)計法正確的是（）。

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

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

C:結果與測試的樣本數(shù)據(jù)有關

D:結果是面向機器，面向程序員，面向語言的

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

；結果與測試的樣本數(shù)據(jù)有關

；結果是面向機器，面向程序員，面向語言的

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

A:確定合適的數(shù)據(jù)結構

B:使用何種計算機語言設計程序

C:證明算法的正確性。

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

答案:確定合適的數(shù)據(jù)結構

；是求精確解還是近似解

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

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問題的意義:一旦某個NPC問題找到了多項式時間復雜性的算法，那么所有的NP問題都找到了多項式時間算法。()

A:錯B:對

答案:對

第二章單元測試

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

A:遞歸算法

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

C:貪心算法

D:迭代算法

答案:遞歸算法

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

A:

B:

C:

D:

答案:

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

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

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

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

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

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

利用二分搜索，最壞情況下的計算時間復雜性為（）。

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

答案:O(logn)二分搜索算法只適用（）存儲結構。

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

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

A:1000

B:500C:11D:10

答案:10線性時間選擇的時間復雜度為（）。

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}，選擇基準16，進行一次劃分，結果為（）：

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}

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

A:錯B:對

答案:對

第三章單元測試

設序列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的最長公共子序列。

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

A:10B:6C:9

D:7

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

A:87500

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

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

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

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

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

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

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

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

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

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

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

答案:子問題重疊性質對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）

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

A:錯B:對

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

A:錯B:對

答案:對

第四章單元測試

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

A:0B:.111C:1100

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

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

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

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

A:對B:錯

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

A:錯B:對

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

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

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

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

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

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

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

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

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

A:最小生成樹問題

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

答案:最小生成樹問題

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

第五章單元測試

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

A:錯B:對

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

A:錯B:對

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

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

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

C:顯式地存儲整個解空間；

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

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

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

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

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

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

B:約束函數(shù)

C:限界函數(shù)

D:遞歸函數(shù)

答案:約束函數(shù)

；限界函數(shù)

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

A:確定易于搜索的解空間結構;

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

C:確定最優(yōu)子結構的性質;

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

答案:確定易于搜索的解空間結構;

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

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

四色定理是第一個主要由計算機證明的理論（）

A:對B:錯

答案:對

第六章單元測試

在對問題的解空間樹進行搜索的方法中，一個活結點最多有一次機會成為活結點的是()。

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

D:分支限界法

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