23秋《算法與數(shù)據(jù)分析》作業(yè)2

試卷總分:100  得分:100

一、單選題 (共 10 道試題,共 50 分)

1.采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）

2.在下列算法中有時(shí)找不到問(wèn)題解的是

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

D.數(shù)值概率算法

3.最長(zhǎng)公共子序列算法利用的算法是

A.分支界限法

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

C.貪心法

D.回溯法

4.下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是

A.備忘錄法

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

C.貪心法

D.回溯法

5.Strassen矩陣乘法是利用什么實(shí)現(xiàn)的算法

A.分治策略

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

C.貪心法

D.回溯法

6.以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

7.下列算法中不能解決0/1背包問(wèn)題的是

A.貪心法

B.動(dòng)態(tài)規(guī)劃

C.回溯法

D.分支限界法

8.備忘錄方法是那種算法的變形

A.分治法

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

C.貪心法

D.回溯法

9.下面關(guān)于NP問(wèn)題說(shuō)法正確的是

A.NP問(wèn)題都是不可能解決的問(wèn)題

B.P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中

C.NP完全問(wèn)題是P類(lèi)問(wèn)題的子集

D.NP類(lèi)問(wèn)題包含在P類(lèi)問(wèn)題中

10.舍伍德算法是以下的哪一種

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

二、判斷題 (共 10 道試題,共 50 分)

11.貪心算法的基本要素是貪心選擇質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)

12.設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟有5步

13.貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，但不是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別

14.回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。

15.從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是遞歸算法。

16.算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。

17.分治法與動(dòng)態(tài)規(guī)劃法的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。而用分治法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往是互相獨(dú)立的

18.舍伍德算法總能求得問(wèn)題的一個(gè)解。

19.快速排序算法的性能取決于劃分的對(duì)稱(chēng)性

20.回溯法搜索解空間樹(shù)時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。

奧鵬，國(guó)開(kāi)，廣開(kāi)，電大在線，各省平臺(tái)，新疆一體化等平臺(tái)學(xué)習(xí)
詳情請(qǐng)咨詢(xún)QQ : 3230981406或微信:aopopenfd777