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

試卷總分:100  得分:100

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

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

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）

2.在下列算法中有時找不到問題解的是

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

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

3.最長公共子序列算法利用的算法是

A.分支界限法

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

C.貪心法

D.回溯法

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

A.備忘錄法

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

C.貪心法

D.回溯法

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

A.分治策略

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

C.貪心法

D.回溯法

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

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

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

A.貪心法

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

C.回溯法

D.分支限界法

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

A.分治法

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

C.貪心法

D.回溯法

9.下面關于NP問題說法正確的是

A.NP問題都是不可能解決的問題

B.P類問題包含在NP類問題中

C.NP完全問題是P類問題的子集

D.NP類問題包含在P類問題中

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

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

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

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

12.設計動態(tài)規(guī)劃算法的主要步驟有5步

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

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

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

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

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

18.舍伍德算法總能求得問題的一個解。

19.快速排序算法的性能取決于劃分的對稱性

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

奧鵬，國開，廣開，電大在線，各省平臺，新疆一體化等平臺學習
詳情請咨詢QQ : 3230981406或微信:aopopenfd777