算法設(shè)計與分析知到章節(jié)答案智慧樹2023年山東科技大學(xué)

算法設(shè)計與分析知到章節(jié)測試答案智慧樹2023年最新山東科技大學(xué)第一章測試

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

參考答案:

錯

有關(guān)算法分析的事后統(tǒng)計法正確的是（）。

參考答案:

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

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

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

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

參考答案:

是求精確解還是近似解

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

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

參考答案:

O(logn)

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

參考答案:

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

研究NPC問題的意義:一旦某個NPC問題找到了多項式時間復(fù)雜性的算法，那么所有的NP問題都找到了多項式時間算法。()

參考答案:

對

第二章測試

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

參考答案:

遞歸算法

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

參考答案:

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

參考答案:

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

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

參考答案:

O(logn)

二分搜索算法只適用（）存儲結(jié)構(gòu)。

參考答案:

順序

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

參考答案:

10

線性時間選擇的時間復(fù)雜度為（）。

參考答案:

O(n)

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

參考答案:

O（n）

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

參考答案:

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

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

參考答案:

對

第三章測試

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

參考答案:

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)時，最大子段和為().

參考答案:

6

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

參考答案:

10500,

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

參考答案:

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

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

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

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

參考答案:

子問題重疊性質(zhì)

對0-1背包問題，n=5，c=12，w={3,7,5,4，4}，v={6,3,5,4，6}，則其最優(yōu)解為（）

參考答案:

（1，0，1，0，1）

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

參考答案:

錯

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

參考答案:

對

第四章測試

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

參考答案:

0

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

參考答案:

O(nlogn)

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

參考答案:

對

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

參考答案:

錯

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

參考答案:

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

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

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

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

參考答案:

單源最短路徑問題

;最小生成樹問題

;哈夫曼編碼問題

第五章測試

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

參考答案:

對

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

參考答案:

錯

下面關(guān)于用回溯法解題說法，正確的是().

參考答案:

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

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

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

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

參考答案:

限界函數(shù)

;約束函數(shù)

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

參考答案:

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

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

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

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

參考答案:

對

第六章測試

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

參考答案:

分支限界法

分支限界法與回溯法的相同點是：都是一種在問題的（）中搜索問題解的算法。