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

試卷總分:100  得分:100

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

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

A.重疊子問題

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

C.貪心選擇性質

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

2.最大效益優(yōu)先是下列哪項的一種搜索方式

A.分支界限法

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

C.貪心法

D.回溯法

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

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

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

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

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

4.下列算法中通常以自底向上的方式求解最優(yōu)解的是

A.備忘錄法

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

C.貪心法

D.回溯法

5.分支限界法與回溯法的相同點是

A.求解目標相同

B.搜索方式相同

C.對擴展結點的擴展方式相同

D.都是一種在問題的解空間樹T中搜索問題解的算法

6.實現(xiàn)大整數(shù)的乘法是利用的算法

A.貪心法

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

C.分治策略

D.回溯法

7.矩陣連乘問題的算法可由什么設計實現(xiàn)

A.分支界限算法

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

C.貪心算法

D.回溯算法

8.分支限界法解最大團問題時，活結點表的組織形式是

A.最小堆

B.最大堆

C.棧

D.數(shù)組

9.回溯法搜索狀態(tài)空間樹是按照什么的順序

A.中序遍歷

B.廣度優(yōu)先遍歷

C.深度優(yōu)先遍歷

D.層次優(yōu)先遍歷

10.廣度優(yōu)先是什么的一種搜索方式

A.分支界限法

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

C.貪心法

D.回溯法

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

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

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

13.分治法的基本思想時將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解

14.任何可用計算機求解的問題所需的時間都與其規(guī)模無關。

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

16.分支限界法主要有隊列式（FIFO）分支限界法和優(yōu)先隊列式分支限界法。

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

18.問題的最優(yōu)子結構性質是該問題不可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。

19.解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動態(tài)規(guī)劃，需要排序的是回溯法，分支限界法

20.利用概率的性質計算近似值的隨機算法是數(shù)值概率算法，運行時以一定的概率得到正確解的隨機算法是蒙特卡羅算法

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