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

試卷總分:100  得分:100

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

1.用分支限界法設計算法的第二步是

A.針對所給問題，定義問題的解空間（對解進行編碼

B.確定易于搜索的解空間結(jié)構（按樹或圖組織解）

C.以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間

D.在搜索過程中用剪枝函數(shù)避免無效搜索

2.蒙特卡羅算法是以下的哪種

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

3.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征是問題的

A.重疊子問題

B.最優(yōu)子結(jié)構性質(zhì)

C.貪心選擇性質(zhì)

D.定義最優(yōu)解

4.實現(xiàn)合并排序利用的算法是

A.分治策略

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

C.貪心法

D.回溯法

5.實現(xiàn)最大子段和利用的算法是

A.分治策略

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

C.貪心法

D.回溯法

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

A.遞歸函數(shù)

B..剪枝函數(shù)

C.。隨機數(shù)函數(shù)

D..搜索函數(shù)

7.哈弗曼編碼的貪心算法所需的計算時間為

A.O（n2n）

B.O（nlogn）

C.O（2n）

D.O（n）

8.實現(xiàn)棋盤覆蓋算法利用的算法是

A.分治法

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

C.貪心法

D.回溯法

9.合并排序算法是利用

A.分治策略

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

C.貪心法

D.回溯法

10.下面是貪心算法的基本要素的是

A.重疊子問題

B.構造最優(yōu)解

C.貪心選擇性質(zhì)

D.定義最優(yōu)解

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

11.矩陣連乘問題的算法可由動態(tài)規(guī)劃設計實現(xiàn)。

12.分支限界法是一種只帶有系統(tǒng)性的搜索算法。

13.矩陣連乘問題的算法可由動態(tài)規(guī)劃設計實現(xiàn)

14.拉斯維加斯算法找到的解不一定是正確解。

15.動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

16.程序是算法用某種程序設計語言的具體實現(xiàn)

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

18.計算一個算法時間復雜度通常可以計算循環(huán)次數(shù)、基本操作的頻率或計算步。

19.分支限界法與回溯法的求解目標相同

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

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