算法分析與設(shè)計20級學(xué)習(xí)通超星課后章節(jié)答案期末考試題庫2023年

算法分析與設(shè)計20級學(xué)習(xí)通超星課后章節(jié)答案期末考試題庫2023年Hanoi塔問題:要求將塔座A上的的所有n圓盤移到塔座B上,借助塔座C，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。由此設(shè)計出解Hanoi塔問題的遞歸算法正確的為：

參考答案:

voidhanoi(intn,intA,intB,intC){if(n>0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}

O(f(n))+O(g(n))=O(min{f(n),g(n)})

參考答案:

F###錯誤

T(n)表示當(dāng)輸入規(guī)模為n時的算法效率，以下算法效率最優(yōu)的是（）。

參考答案:

T(n)=T(n/2)+1，T(1)=1

下列關(guān)于算法的說法中正確的有（）。Ⅰ.求解某一類問題的算法是唯一的Ⅱ.算法必須在有限步操作之后停止Ⅲ.算法的每一步操作必須是明確的，不能有歧義或含義模糊Ⅳ.算法執(zhí)行后一定產(chǎn)生確定的結(jié)果

參考答案:

算法的確定性是指指令不能有二義性。

下面（）函數(shù)是回溯法中為避免無效搜索采取的策略

參考答案:

剪枝函數(shù)

下面程序的時間復(fù)雜度是（）i=1while(i<=n)do

i=i*5

參考答案:

3344

以下不可以使用分治法求解的是（

）

參考答案:

0/1背包問題

優(yōu)先隊列式分枝限界法求解單源最短路徑問題時，活結(jié)點表的組織形式是（

）

參考答案:

結(jié)點的優(yōu)先級

優(yōu)先隊列式分枝限界法選取擴展結(jié)點的原則是（

）

參考答案:

結(jié)點的優(yōu)先級

優(yōu)先隊列的分支限界法將活結(jié)點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴展結(jié)點。優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級常用一個與該結(jié)點相關(guān)的數(shù)值p來表示。結(jié)點優(yōu)先級的高低與p值大小相關(guān)，根據(jù)問題的不同情況，采用（）來描述優(yōu)先隊列。

參考答案:

先進先出隊列

關(guān)于回溯法以下敘述中不正確的是（）

參考答案:

回溯算法需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當(dāng)前擴展結(jié)點的路徑

出于“平衡子問題”的思想，通常分治法在分解原問題時，形成若干子問題，這些子問題的規(guī)模都大致相同。

參考答案:

T###正確

分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解，二者（）。

參考答案:

求解目標不同搜索方式也不同

分支限界法的搜索策略是：在擴展結(jié)點處，先生成其（）兒子結(jié)點（分支），然后再從當(dāng)前的活結(jié)點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。

參考答案:

二個

分枝限界法在問題的解空間樹中，按（）策略，從根結(jié)點出發(fā)搜索解空間樹。

參考答案:

廣度優(yōu)先

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

）。

參考答案:

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

動態(tài)規(guī)劃使包含同一個子問題的所有問題共用一個子問題解，所以并不需要很大的空間以存儲中間產(chǎn)生的結(jié)果，從而體現(xiàn)動態(tài)規(guī)劃的優(yōu)越性。

參考答案:

F###錯誤

動態(tài)規(guī)劃算法中存儲子問題的解是為了避免重復(fù)求解子問題

參考答案:

對

動態(tài)規(guī)劃算法每步所做的選擇往往依賴于相關(guān)子問題的解，而貪心算法做貪心選擇時不依賴于子問題的解（）

參考答案:

對

動態(tài)規(guī)劃算法的基本要素為()

參考答案:

對

回溯法在問題的解空間樹中，按（）策略，從根結(jié)點出發(fā)搜索解空間樹

參考答案:

深度優(yōu)先

回溯法的效率不依賴于下列哪些因素（）

參考答案:

確定解空間的時間

在一般情況下，一個算法的時間復(fù)雜度是問題規(guī)模的函數(shù)。

參考答案:

F###錯誤

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

參考答案:

分支限界法

在尋找n個元素中第k小元素問題中，如快速排序算法思想，運用分治算法對n個元素進行劃分，如何選擇劃分基準？下面（

）答案解釋最合理。

參考答案:

以上皆可行。但不同方法，算法復(fù)雜度上界可能不同

對于下列二分查找算法，以下正確的是（）。

參考答案:

int

binarySearch(int

a[],

int

n,

int

x)

{

if(n

>

0

&&

x

>=

a[0])

{

int

low

=

0,

high

=

n-1;

while(low

<

high)

{

int

mid=(low+high+1)/2;

if(x

<

a[mid])

high=mid-1;

else

low=mid;

}

if(x==a[low])

return

low;

}

return

–1;

}

常見的兩種分枝限界法為（）

參考答案:

隊列式（FIFO）分枝限界法與優(yōu)先隊列式分枝限界法

當(dāng)輸入規(guī)模為n時，下列算法漸進復(fù)雜性中最低的是(

)

參考答案:

A.5n

快速排序算法在最好情況下的時間復(fù)雜度為（

）

參考答案:

√

快速排序算法是基于分治策略的一種排序算法

參考答案:

T###正確

算法分析的目的是（?）

參考答案:

分析算法的效率以求改進

設(shè)f（N）、g（N）是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時有f（N）≥Cg（